如何在r-tree的内部节点存储一些信息？

Question

我是新手boost和c++。我正在尝试使用boost库编写r树。在我的代码中，我希望在每个内部节点上存储一些信息x。我现在有两个问题。

1)如何在r星树中进行遍历(深度优先)？

2)假设我可以遍历树的节点。需要为Box(内部节点)类定义一些成员变量，我可以在其中存储每个节点上的x。对于它，什么是合适和有效的方法？

Answer 1

通过阅读您的评论，我得到的印象是，您只想在R-tree中存储的点中存储额外的数据，而不是在R-tree的内部节点中存储额外的数据。因此，这里有一个示例，展示了如何存储带有附加数据的点，以及如何执行查询以获取其中的一些点。在这个例子中，我还展示了如何使用std::pair来实现相同的功能，它包含一个点和一些额外的数据，这些数据在默认情况下是有效的，并且您不必注册自己的点类型。

包括：

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

方便起见的命名空间：

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

使用二维坐标和其他数据(颜色)定义您自己的点类型：

enum color {red, green, blue};

struct my_point
{
    double x, y;
    color c;
};

使用宏使my_point适应Boost.Geometry点的概念，以便库知道此结构是二维点以及如何获取坐标：

BOOST_GEOMETRY_REGISTER_POINT_2D(my_point, double, bg::cs::cartesian, x, y)

还将使用的一些Boost.Geometry模型：

typedef bg::model::point<double, 2, bg::cs::cartesian> bg_point;
typedef bg::model::box<bg_point> bg_box;

Main：

int main()
{
    {

创建R树并插入几个点：

        bgi::rtree<my_point, bgi::rstar<4> > rtree;
        rtree.insert(my_point{ 0, 0, red });
        rtree.insert(my_point{ 1, 1, green });
        rtree.insert(my_point{ 2, 5, blue });
        rtree.insert(my_point{ 7, 3, red });
        rtree.insert(my_point{ 8, 8, green });
        rtree.insert(my_point{ 1, 9, blue });

查询与以下框相交且为红色的点：

        std::vector<my_point> res;
        rtree.query(bgi::intersects(bg_box{ {1, 1}, {8, 8} })
                 && bgi::satisfies([](my_point const& p) {
                        return p.c == red;
                    }),
                    std::back_inserter(res));

打印结果：

        for (my_point const& p : res)
            std::cout << bg::wkt(p) << std::endl;
    }

相同的，但使用std::pair<bg_point, color>而不是my_point，因此不需要注册：

    {
        bgi::rtree<std::pair<bg_point, color>, bgi::rstar<4> > rtree;
        rtree.insert(std::pair<bg_point, color>{ {0, 0}, red });
        rtree.insert(std::pair<bg_point, color>{ {1, 1}, green });
        rtree.insert(std::pair<bg_point, color>{ {2, 5}, blue });
        rtree.insert(std::pair<bg_point, color>{ {7, 3}, red });
        rtree.insert(std::pair<bg_point, color>{ {8, 8}, green });
        rtree.insert(std::pair<bg_point, color>{ {1, 9}, blue });

        std::vector<std::pair<bg_point, color> > res;
        rtree.query(bgi::intersects(bg_box{ { 1, 1 },{ 8, 8 } })
                 && bgi::satisfies([](std::pair<bg_point, color> const& p) {
                        return p.second == red;
                    }),
                    std::back_inserter(res));

        for (std::pair<bg_point, color> const& p : res)
            std::cout << bg::wkt(p.first) << std::endl;
    }
}

上面的程序打印以下行两次：

POINT(7 3)

这是唯一一个与长方体相交的红色点。

原始答案(如果您确实想修改R-tree的内部结构)：

公共R-tree接口不支持您想要执行的操作。你将不得不玩弄内部结构，这些内部结构在未来可能会改变。

1. Here是一个线程，它解释了如何编写一个访问者来遍历R树节点。
2. 使用你自己的节点类型比较困难。你必须这样做：

1. add new node tag [like this](https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/options.hpp#L39)
2. specialize internal and leaf nodes (adding members you like in nodes) and all other required classes for this tag [like in this file](https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/node/variant_static.hpp)
3. implement your own R-tree parameters type, e.g. based on `bgi::rstar`, [like this](https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/parameters.hpp#L130)
4. specialize `bgi::detail::rtree::options_type` in order to tell the R-tree what nodes should be used for your parameters type [like this](https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/options.hpp#L87)

另请参阅用于R树测试的this node implementation。这是一个可以在构造时抛出异常的节点。它用于测试异常安全性。