c++ - 在几何中使用 boost rtree 查找结果点

Question

我正在尝试在我的一个项目中使用 boost::geometry 的 rtree DS，但我发现很难浏览文档。某些方法的文档很少，我找不到足够的例子。现在，我正在尝试构建示例程序，以便进一步构建它。

因此，在下面的示例中，我有一个由点和一个框组成的 rtree，我需要找到位于该框内的所有点。我想问的另一件事是，我找不到 packing algorithm 构造函数或方法，所以如何使用它。这是我到目前为止所做的 -

#include <iostream>
#include <vector>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/register/point.hpp>
#include <boost/geometry/geometries/register/box.hpp>
#include <boost/geometry/index/rtree.hpp>


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


struct my_point
{
    float x, y;
    my_point(float _x, float _y) : x(_x), y(_y) {}
};

struct my_box
{
    my_point ll, ur;
    my_box(float x1, float y1, float x2, float y2) : ll(x1,y1), ur(x2,y2) {}
};

// Register the point type
BOOST_GEOMETRY_REGISTER_POINT_2D(my_point, float, cs::cartesian, x, y)

// Register the box type, also notifying that it is based on "my_point"
BOOST_GEOMETRY_REGISTER_BOX(my_box, my_point, ll, ur)



int main()
{
    std::vector<std::pair<my_point, int>> pts;
    pts.emplace_back(std::make_pair(my_point(2,2), 5));
    pts.emplace_back(std::make_pair(my_point(3,3), 1));
    pts.emplace_back(std::make_pair(my_point(4,5), 3));
    pts.emplace_back(std::make_pair(my_point(4,4), 12));
    pts.emplace_back(std::make_pair(my_point(1,2), 50));
    // ....

    bgi::rtree<std::pair<my_point, int>, bgi::dynamic_rstar> rT(bgi::dynamic_rstar(pts.size()));
    rT.insert(pts.begin(), pts.end());

    my_box box1(1,1,4,4);
    // how to retrieve all points or their .second inside this box?

    return 0;
}

Answer 1

如果将范围传递给 R 树的构造函数，则使用打包算法:

• rtree(Iterator, Iterator)
• rtree(Range)

可以使用 query 从 R 树中检索值方法或查询迭代器:

• R-tree queries
• query(Predicates, OutputIterator)

另见 R-tree Quick Start example .

最后一点。在您的代码中，您将点数传递给 bgi::dynamic_rstar . bgi::dynamic_rstar 的参数不是包含值的数量。它是存储在 R 树单个节点中的最大值数(对应于持久性/基于磁盘的 R 树的页面大小)。所以如果你通过 bgi::dynamic_rstar(pts.size()) R 树只包含一个包含所有点的节点，这意味着没有节点的层次结构，没有空间分区，实际上 rtree 的行为就像一个 vector 。而是使用例如bgi::rstar<4>如果值重叠很大，或者更大的数字，但在你的情况下它不应该，因为你正在存储点。这就足够了:

bgi::rtree<std::pair<my_point, int>, bgi::rstar<4> > rT(pts);