C++ R-tree实现需求

Question

C++ R-tree实现需求

c++r-tree

27

有没有人知道一款好用且适合生产环境的 R-tree 实现？（实际上，任何实现——R*，R+ 或者 PR-tree 都很棒）

无论是模板还是库实现都可以，但是谷歌找到的一些实现看起来让人很失望...

- M. Williams

4个回答

17

请查看 http://www.superliminal.com/sources/sources.htm 上的R-Trees代码。

还可以查看http://www.virtualroadside.com/blog/index.php/2008/10/04/r-tree-implementation-for-cpp/

- Lior Kogan

我仍然认为这些版本缺乏灵活性，但是嗯，看起来可以使用。 - M. Williams

两个版本都需要在编译时选择数据维度，这使它们对我来说毫无用处。 - Michael Nett

5

所以你之所以对我的开源实现的提及进行下投票，是因为它们对你没有用处？ - Lior Kogan

@LiorKogan 这是确实的，但主要是因为我认为这在实现中是一个重大缺陷。 - Michael Nett

1

@MichaelNett 使用模板化的C++版本第一个（http://www.superliminal.com/sources/sources.htm），该版本除了存储数据类型外还需要一个维度参数。 - Melinda Green

10

我更新了在http://www.superliminal.com/sources/sources.htm找到的实现，以支持更广泛的数据类型。

你可以在github上找到我的版本：https://github.com/nushoin/RTree

原始版本是公共领域的，我的也是。

- Yariv

再次强调，数据维度的选择必须在编译时确定... - Michael Nett

5

spatialindex提供了一个很好的接口，可以使用不同类型的空间（和时空）索引结构，包括R、R*、TPR树，网址为http://libspatialindex.github.com/

- arthur

该库同时提供GPL和MIT两种许可证，这很酷。 - arthur

它几乎完美，除了不支持线程安全。 - Richard

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Adam Wulkiewicz · Accepted Answer

你也可以查看Boost.Geometry库提供的rtree变体：

http://www.boost.org/doc/libs/release/libs/geometry/doc/html/geometry/spatial_indexes.html

Boost.Geometry rtree实现允许在空间索引中存储任意类型的值并执行复杂查询。可以将诸如最大节点元素之类的参数作为编译时或运行时参数传递。它支持C++11移动语义，也通过Boost.Move在C++11之前的编译器上进行模拟。它还支持有状态分配器，例如使用Boost.Interprocess将rtree存储在共享内存中。而且速度很快。

不足之处在于，目前尚不支持持久存储，因此如果需要超过内存空间索引，则应该检查其他提到的库之一。

快速示例：

可能最常见的用例是将一些几何对象以及它们的边界框和某些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;
}