Boost R树节点删除

Question

我想移除最近的点节点。这应该满足距离的限制。但我认为我的代码效率不高。我该如何修改它？

    for (int j = 0; j < 3; j++) {
    bgi::rtree< value, bgi::quadratic<16> > nextRT;

    // search for nearest neighbours
    std::vector<value> matchPoints;
    vector<pair<float, float>> pointList;

    for (unsigned i = 0; i < keypoints[j + 1].size(); ++i) {
        point p = point(keypoints[j + 1][i].pt.x, keypoints[j + 1][i].pt.y);
        nextRT.insert(std::make_pair(p, i));
        RT.query(bgi::nearest(p, 1), std::back_inserter(matchPoints));

        if (bg::distance(p, matchPoints.back().first) > 3) matchPoints.pop_back();
        else {
            pointList.push_back(make_pair(keypoints[j + 1][i].pt.x, keypoints[j + 1][i].pt.y));
            RT.remove(matchPoints.back());
        }
    }

我也很好奇 matchPoints 的结果。查询函数运行后，matchPoints 中有值。第一个是点，第二个看起来像一些索引号。不知道第二个是什么意思

Answer 1

Q. and I also curious about result of matchPoints. After query function works, there are values in matchPoints. first one is point, and second one looks like some indexing number. I don't know what second one means.

嗯，这必须是您 value 类型中的数据成员。其中的内容完全取决于您在 rtree 中插入的内容。如果它是描述几何的 ID，我不会感到惊讶。

由于您甚至没有显示 RT 的类型，我们只能假设它与 nextRT 相同。如果是这样，我们可以假设 value 可能是一对像 pair<box, unsigned> （因为你插入的内容）。所以，看看在 RT...

中为 unsigned 值插入了什么

Q.

    if (bg::distance(p, matchPoints.back().first) > 3) matchPoints.pop_back();
    else {
        pointList.push_back(make_pair(keypoints[j + 1][i].pt.x, keypoints[j + 1][i].pt.y));
        rtree.remove(matchPoints.back());
    }

简化您的代码！提炼需求：

在我看来，对于 4 组 "key points"，您想要创建 4 个包含所有这些关键点的 rtree，并按顺序增加 ID。
同样对于那 4 组 "key points"，您想要创建一个关键点列表，可以找到半径为 3 的几何图形。

作为副作用，从原始 rtree RT.

DECISION: Because these tasks are independent, let's do them separate:

// making up types that match the usage in your code:
struct keypoint_t { point pt; };
std::array<std::vector<keypoint_t>, 4> keypoints;

现在，让我们完成任务：

注意这里没有使用RT:

for (auto const& current_key_set : keypoints) {
    bgi::rtree< value, bgi::quadratic<16> > nextRT; // use a better name...

    int i = 0;
    for (auto const& kpd : current_key_set)
        nextRT.insert(std::make_pair(kpd.pt, i++));
}

创建包含匹配关键点的向量（那些在 RT 中具有接近几何形状的向量）：

for (auto const& current_key_set : keypoints) {
    std::vector<point> matched_key_points;

    for (auto const& kpd : current_key_set) {
        point p = kpd.pt;

        value match;
        if (!RT.query(bgi::nearest(p, 1), &match))
            continue;

        if (bg::distance(p, match.first) <= 3) {
            matched_key_points.push_back(p);
            RT.remove(match);
        }
    }
}

具有讽刺意味的是，从 RT 中删除匹配的几何图形成为了一个小问题：您可以通过迭代器或值删除。在这种情况下，我们使用带有 value.

的重载

总结

很难完全理解代码以了解它的作用。我已经展示了如何清理代码并使其工作。也许这些不是您需要的东西，但希望使用更好的分离代码，您应该能够走得更远。

请注意，算法有副作用。这让人很难理解到底会发生什么。例如：

从原始 RT 中删除点会影响后续关键点（甚至来自后续集合（下一个 j））可以匹配的内容
如果你有多次相同的关键点，它们可能会匹配多个源RT点（因为在删除第一个匹配后，半径3内可能会有第二个匹配）
关键点严格按顺序检查。这意味着如果第一个关键点与点 X 大致匹配，这可能会导致稍后的关键点 fail 匹配，即使点 X 可能更接近该关键点...

我建议您在实施具有这些副作用的事物之前，认真考虑这些要求。 **Study the sample cases in the live demo below。如果所有这些副作用正是您想要的，请务必使用更好的命名和适当的注释来描述代码的作用。

现场演示

Live On Coliru

#include <boost/geometry.hpp>
#include <boost/geometry/io/io.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <iostream>

namespace bg  = boost::geometry;
namespace bgi = bg::index;

typedef bg::model::point<float, 2, bg::cs::cartesian> point;

typedef std::pair<point, unsigned> pvalue;
typedef pvalue value;

int main() {
    bgi::rtree< value, bgi::quadratic<16> > RT;

    {
        int i = 0;
        for (auto p : { point(2.0f, 2.0f), point(2.5f, 2.5f) })
            RT.insert(std::make_pair(p, i++));
    }

    struct keypoint_t { point pt; };
    using keypoints_t = std::vector<keypoint_t>;

    keypoints_t const keypoints[] = {
        keypoints_t{ keypoint_t { point(-2, 2)  } },  // should not match anything
        keypoints_t{ keypoint_t { point(-1, 2)  } },  // should match (2,2)
        keypoints_t{ keypoint_t { point(2.0, 2.0) },  // matches (2.5,2.5)
                                { point(2.5, 2.5) },  // nothing anymore...
                   },
    };

    for (auto const& current_key_set : keypoints) {
        bgi::rtree< pvalue, bgi::quadratic<16> > nextRT; // use a better name...

        int i = 0;
        for (auto const& kpd : current_key_set)
            nextRT.insert(std::make_pair(kpd.pt, i++));
    }

    for (auto const& current_key_set : keypoints) {
        std::cout << "-----------\n";
        std::vector<point> matched_key_points;

        for (auto const& kpd : current_key_set) {
            point p = kpd.pt;
            std::cout << "Key: " << bg::wkt(p) << "\n";

            value match;
            if (!RT.query(bgi::nearest(p, 1), &match))
                continue;

            if (bg::distance(p, match.first) <= 3) {
                matched_key_points.push_back(p);
                std::cout << "\tRemoving close point: " << bg::wkt(match.first) << "\n";
                RT.remove(match);
            }
        }

        std::cout << "\nMatched keys: ";
        for (auto& p : matched_key_points)
            std::cout << bg::wkt(p) << " ";
        std::cout << "\n\tElements remaining: " << RT.size() << "\n";
    }

}

版画

-----------
Key: POINT(-2 2)

Matched keys: 
    Elements remaining: 2
-----------
Key: POINT(-1 2)
    Removing close point: POINT(2 2)

Matched keys: POINT(-1 2) 
    Elements remaining: 1
-----------
Key: POINT(2 2)
    Removing close point: POINT(2.5 2.5)
Key: POINT(2.5 2.5)

Matched keys: POINT(2 2) 
    Elements remaining: 0

Boost R树节点删除

Boost R tree node remove

boost

r-tree

总结

现场演示