26

本番コードのR-tree実装で使用するのが簡単で良いことを知っている人はいますか? (実際には、任意の実装 -R*, R+またはPR-tree素晴らしいでしょう)

それがテンプレートまたはライブラリの実装であるかどうかは関係ありませんが、Google が見つけたいくつかの実装は非常に残念に見えます...

4

4 に答える 4

27

Boost.Geometry ライブラリによって提供される rtree バリアントを確認することもできます。

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

Boost.Geometry rtree の実装により、空間インデックスに任意の型の値を格納し、複雑なクエリを実行できます。最大ノード要素などのパラメーターは、コンパイル時パラメーターまたは実行時パラメーターとして渡すことができます。Boost.Move のおかげで、C++11 より前のコンパイラでもエミュレートされた 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;
}
于 2013-08-21T22:44:29.137 に答える
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/

于 2010-04-25T18:27:06.777 に答える
9

http://www.superliminal.com/sources/sources.htmにある実装を更新して、より広範なデータ型をサポートしました。

私のバージョンは github で見つけることができます: https://github.com/nushoin/RTree

元のバージョンは、私のものと同様にパブリック ドメインです。

于 2011-09-14T18:10:47.207 に答える
5

spatialindex は、 http://libspatialindex.github.com/の R、R*、TPR ツリーなど、さまざまなタイプの空間 (および時空間) インデックス構造への優れたインターフェイスを提供します。

于 2012-11-06T14:26:42.327 に答える