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

Question

我在代码中使用Boost 的r-tree 实现。我有一个带有坐标的对象列表（比如地图上的城市，如果重要的话），我希望在 r 树中索引，以执行快速 NN 搜索等。我遵循了他们的迭代查询示例，其中树正在存储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

你可以在 a 中存储任何类型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; }
};

point然后您可以在声明时使用您的类型代替rtree：

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