C++ R - 想要树实现
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/2709339/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++ R - tree implementation wanted
提问by M. Williams
Does anyone know a good and simple to use in production code R-treeimplementation? (actually, any implementations - R*, R+or PR-treewould be great)
有谁知道在生产代码R-tree实现中使用的好和简单的方法？（实际上，任何实现 -R*, R+或者PR-tree会很棒）
It doesn't matter if it is a template or library implementation, but some implementations that Google found look very disappointing...
是模板实现还是库实现都没有关系，但是谷歌发现的一些实现看起来非常令人失望......
采纳答案by Lior Kogan
Check R-Trees code on http://www.superliminal.com/sources/sources.htm
检查http://www.superliminal.com/sources/sources.htm上的 R-Trees 代码
also check
还检查
http://www.virtualroadside.com/blog/index.php/2008/10/04/r-tree-implementation-for-cpp/
http://www.virtualroadside.com/blog/index.php/2008/10/04/r-tree-implementation-for-cpp/
回答by Adam Wulkiewicz
You may also check out the rtree variants provided by the Boost.Geometry library:
您还可以查看 Boost.Geometry 库提供的 rtree 变体：
http://www.boost.org/doc/libs/release/libs/geometry/doc/html/geometry/spatial_indexes.html
http://www.boost.org/doc/libs/release/libs/geometry/doc/html/geometry/spatial_indexes.html
Boost.Geometry rtree implementation allows storing values of arbitrary type in the spatial index and performing complex queries. Parameters like maximum node elements may be passed as compile- or run-time parameters. It supports C++11 move semantics also emulated on pre-C++11 compilers thanks to Boost.Move. It also supports stateful allocators which allows e.g. to store the rtree in a shared memory using Boost.Interprocess. And it's fast.
Boost.Geometry rtree 实现允许在空间索引中存储任意类型的值并执行复杂查询。像最大节点元素这样的参数可以作为编译或运行时参数传递。由于 Boost.Move，它支持 C++11 移动语义，也可以在 C++11 之前的编译器上模拟。它还支持状态分配器，例如允许使用 Boost.Interprocess 将 rtree 存储在共享内存中。而且速度很快。
On the down-side, currently persistent storage isn't yet supported so if you need more than in-memory spatial index you should probably check one of the other mentioned libraries.
不利的一面是，目前尚不支持持久存储，因此如果您需要的不仅仅是内存空间索引，您可能应该检查其他提到的库之一。
Quick example:
快速示例：
Probably the most common use case is when you store some geometric objects in a container and their bounding boxes with some ids in the spatial index. In case of Boost.Geometry rtree this could look like this:
最常见的用例可能是将一些几何对象存储在容器中，并将它们的边界框与空间索引中的一些 id 存储在一起。在 Boost.Geometry rtree 的情况下，这可能如下所示：
#include <boost/geometry.hpp>
#include <boost/geometry/index/rtree.hpp>
#include <vector>
namespace bg = boost::geometry;
namespace bgi = boost::geometry::index;
/* The definition of my_object type goes here */
int main()
{
typedef bg::model::point<float, 2, bg::cs::cartesian> point;
typedef bg::model::box<point> box;
typedef std::pair<box, size_t> value;
std::vector<my_object> objects;
/* Fill objects */
// create the R* variant of the rtree
bgi::rtree< value, bgi::rstar<16> > rtree;
// insert some values to the rtree
for ( size_t i = 0 ; i < objects.size() ; ++i )
{
// create a box
box b = objects[i].calculate_bounding_box();
// insert new value
rtree.insert(std::make_pair(b, i));
}
// find values intersecting some area defined by a box
box query_box(point(0, 0), point(5, 5));
std::vector<value> result_s;
rtree.query(bgi::intersects(query_box), std::back_inserter(result_s));
// find 5 nearest values to a point
std::vector<value> result_n;
rtree.query(bgi::nearest(point(0, 0), 5), std::back_inserter(result_n));
return 0;
}
回答by Yariv
I updated the implementation found in http://www.superliminal.com/sources/sources.htmto support a broader range of data types.
我更新了http://www.superliminal.com/sources/sources.htm 中的实现以支持更广泛的数据类型。
You can find my version on github: https://github.com/nushoin/RTree
你可以在 github 上找到我的版本：https: //github.com/nushoin/RTree
The original version is public domain, as is mine.
原始版本是公共领域，我的也是。
回答by arthur
spatialindex provides a nice interface to different types of spatial (and spatio-temporal) index structures including R, R*, TPR trees at http://libspatialindex.github.com/
空间索引为不同类型的空间（和时空）索引结构提供了一个很好的接口，包括http://libspatialindex.github.com/ 上的R、R*、TPR 树
