3

境界矩形に含まれる一連の幾何学的オブジェクトを「選択」するために使用される R ツリーを実装する方法を理解しようとしています。データ レイアウトの例をB-Treeとして示している Wikipedia の記事を調べました。

B ツリーを作成し、それを使用して R ツリーを作成することもできますが、これらは 2 つの複雑なデータ構造であり、デバッグやテストなどを行う必要があります。既存のツリー実装 (std::set/ multiset) を使用し、並べ替え操作を提供します。

シェイプに次のインターフェイスがあると仮定します。

class Shape
{
    public:
        Shape();
        virtual ~Shape();
        const AABB & bounding_box() const = 0;
};

そして、形状を注文するためにこのファンクターを提供します:

struct OrderShapes
{
    bool operator()(Shape * const & left, Shape * const & right) const
    {
        return right->bounding_box().contains(left->bounding_box());
    }
};

std::set<Shape *, OrderShapes>は有効な R-Tree として動作しますか? そうでない場合、車輪を再発明せずにこの問題を解決するにはどうすればよいですか?

4

3 に答える 3

3

R ツリーはB ツリーではありません。それらにはいくつかの共通点がありますが、おそらく他のブロック指向 (= ディスク最適化) ツリー データ構造よりも多くはありません。

私見ですが、最初に B ツリーを実装することは、A) 経験と、B) 高速ブロック I/O 用の安定した API を取得するという 2 つの点で優れています。

R ツリーの主な問題は、クエリではありません。それらはクエリに対して非常に簡単です。課題は、ツリーのバランスを保ちながら、ツリーを効率的に変更する方法、つまり要素を削除して要素を追加する方法です。1 次元のデータ セット (つまり B+ ツリー) では、バランシングに使用できる一意の近傍があるため、これはかなり簡単です。これは、高次元データでは機能しなくなりました。

しかしもちろん、次のような既存の R ツリー ライブラリを探すこともできます。libspatialindex

overlapsPS R ツリーをクエリするには、 ではなくが必要ですcontains。

于 2013-01-08T07:38:41.993 に答える
2

std::set は有効な R ツリーとして動作しますか?

間違いなくいいえ。STL には B ツリーの実装さえ含まれていません。std::set は単なる赤黒ツリーであり、B ツリーではありません。

車輪を再発明せずにこの問題を解決するにはどうすればよいですか?

この答えを見ましたか？

于 2013-01-07T11:46:27.463 に答える