在Boost R树中存储或访问对象 [英] Storing or accessing objects in boost r-tree

问题描述

我正在使用我的代码中Boost的r-tree实现.我有一个带有坐标的对象列表(例如，如果需要的话，说地图上的城市)，我希望在r树中建立索引，以进行快速的NN搜索，等等.我遵循了它们的

I am using 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, in which trees are storing boost::geometry::model::point objects.

我的问题:是否仍然要存储对象(即城市本身)，而不只是存储它们在树中的坐标?我想到的一种解决方案是使用我自己的索引.如果确实是我应该做的-是否仍然可以通过将对象插入到树中的顺序来找到对象的索引?

My question: is there anyway to store objects (i.e. the cities themselves) instead of just their coordinates in the tree? One solution I thought about is to use indexing of my own. If this is indeed what I should do - is there anyway to find the index of the objects by the order in which they were inserted to the tree?

例如，当我寻找某些城市的KNN时，我不仅要像示例中那样提取它们的坐标(或距离):

So, for example, when I look for the KNNs of some cities - I would like to extract not only their coordinates (or distances), like they do in the example:

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;
}

还有它们插入到树中的顺序，因此我可以从包含按插入顺序包含对象的向量的例如中访问它们.

But also the order at which they were inserted into the tree, so I could access them e.g. from a vector that contains the objects by order of insertion.

推荐答案

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

You can store any type in a rtree, you just have to tell Boost how to get the coordinates out.

所以第一步就是要创建一个既有索引又有点的类型:

So the first step is to make a type with both a index and point:

struct CityRef {
    size_t index;
    point location;
};

您可以专门化 boost :: geometry :: index :: indexable 为Boost提供一种找到放置在此处的点的方法:

You can specialize boost::geometry::index::indexable to give Boost a way to find the point you've put in there:

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

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

Then you can use your type in place of point when declaring your rtree:

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

当您进行迭代时，迭代器将引用您的类型，而不是 point :

And when you iterate, the iterator will refer to your type instead of 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

Here is a demo using that example with another type: https://godbolt.org/z/zT3xcf

这篇关于在Boost R树中存储或访问对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！