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

Question

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

1）如何在r星树中执行遍历（深度优先）？

2）假设我可以遍历树的节点。需要为Box（INTERNAL节点）类定义一些成员变量，我可以在每个节点存储x。什么是适当和有效的方法呢？

Answer 1

通过阅读您的评论，我得到的印象是您只想在存储在R树中的点中存储其他数据，而不是将其他数据存储在R树的内部节点中。因此，这里有一个示例，说明如何使用其他数据存储点以及如何执行查询以获取其中一些数据。在示例中，我还展示了如何实现相同的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 Point概念，因此库知道这个结构是一个二维点以及如何获得坐标：

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;

主要：

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树的内部结构）：

公共R树接口不支持您要执行的操作。您必须使用可能在将来发生变化的内部组件。

1. Here是一个解释如何编写访问者来遍历R树节点的线程。
2. 使用自己的节点类型更难。你必须： 添加新节点标签like this 专门化内部和叶节点（在节点中添加您喜欢的成员）以及此标记like in this file的所有其他必需类 实现自己的R树参数类型，例如基于bgi::rstar，like this 专门化bgi::detail::rtree::options_type以告诉R-tree应该使用哪些节点作为参数类型like this 另请参阅用于R树测试的this node implementation。这是一个可以在构造上抛出异常的节点。它用于测试异常安全性。