C ++ R-ツリーの実装が望ましい[閉じ

StackOverflow https://stackoverflow.com/questions/2709339

  •  01-10-2019
  •  | 
  •  

質問

誰もが生産コードでの使用が良いと簡単に使用できることを知っていますか R-tree 実装？ （実際、実装 - R*, R+ また PR-tree 素晴らしいことだ）

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

役に立ちましたか？

解決

R-Treesコードを確認してください http://www.superliminal.com/sources/sources.htm

また、確認してください

http://www.virtualroadside.com/blog/index.php/2008/10/04/r-tree-implementation-for-cpp/

他のヒント

また、Boost.Geometryライブラリが提供するRTreeバリエーションを確認することもできます。

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

Boost.Geometry RTree実装により、空間インデックスに任意のタイプの値を保存し、複雑なクエリを実行できます。最大ノード要素などのパラメーターは、コンパイルまたはランタイムパラメーターとして渡される場合があります。 boost.moveのおかげで、Pre-c ++ 11のコンパイラでもエミュレートされたC ++ 11の移動セマンティクスをサポートします。また、boost.interprocessを使用して、rtreeを共有メモリに保存できるステートフルアロケーターもサポートします。そして、それは速いです。

ダウンサイドでは、現在永続的なストレージはまだサポートされていないため、メモリ内の空間インデックスが必要な場合は、おそらく他の1つのライブラリを確認する必要があります。

簡単な例：

おそらく最も一般的なユースケースは、いくつかの幾何学的オブジェクトをコンテナに、およびその境界ボックスに空間インデックスにいくつかの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;
}

で見つかった実装を更新しました http://www.superliminal.com/sources/sources.htm より広範なデータ型をサポートします。

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

元のバージョンは私のようにパブリックドメインです。

SpatialIndexは、R、R*、TPRツリーを含むさまざまなタイプの空間（および時空間）インデックス構造に優れたインターフェイスを提供します http://libspatialindex.github.com/

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top