在 boost r-tree 中存储或访问对象

Question

我正在使用 Boost's r-tree implementation in my code. I have a list of objects with coordinates (say cities on a map, if it matters), which I wish to index in the r-tree, to perform fast NN search, etc. I have followed their iterative query example，其中树存储 boost::geometry::model::point 个对象。

我的问题：是否有存储对象（即城市本身）而不仅仅是它们在树中的坐标？我想到的一种解决方案是使用我自己的索引。如果这确实是我应该做的 - 无论如何可以按照对象插入树的顺序找到对象的索引？

因此，例如，当我寻找一些城市的 KNN 时 - 我想不仅提取它们的坐标（或距离），就像它们在示例中所做的那样：

for ( rtree_t::const_query_iterator
        it = rtree.qbegin(bgi::nearest(pt, N));
        it != rtree.qend() ;
        ++it ) {

    std::cout << bg::wkt(*it) << ", distance= " << bg::distance(pt, *it) << std::endl;
}

还有它们被插入到树中的顺序，所以我可以访问它们例如从一个包含按插入顺序的对象的向量。

Answer 1

您可以在 rtree 中存储任何类型，您只需告诉 Boost 如何获取坐标。

所以第一步是创建一个同时具有索引和点的类型：

struct CityRef {
    size_t index;
    point location;
};

您可以专门化 boost::geometry::index::indexable 来让 Boost 找到您放置在那里的点：

template <>
struct bgi::indexable<CityRef>
{
    typedef point result_type;
    point operator()(const CityRef& c) const { return c.location; }
};

然后您可以在声明 rtree:

时使用您的类型代替 point

typedef bgi::rtree< CityRef, bgi::linear<16> > rtree_t;

并且当你迭代时，迭代器将引用你的类型而不是 point:

for ( rtree_t::const_query_iterator
      it = rtree.qbegin(bgi::nearest(pt, 100)) ;
      it != rtree.qend() ;
      ++it )
{
    // *it is a CityRef, do whatever you want
}

这是一个使用该示例和另一种类型的演示： https://godbolt.org/z/zT3xcf

在 boost r-tree 中存储或访问对象

Storing or accessing objects in boost r-tree

c++

boost

r-tree