問題タブ [r-tree]

Guttman の元の論文に基づいて R ツリーの実装を書いています。マウスで移動/サイズ変更できる画面上の多くの長方形を含む、私が書いているプログラムにRツリーを使用することを考えていました。

特定の四角形にある四角形のみを効率的に選択して描画したい (100 以上のアイテムを反復して境界が交差するかどうかを確認する代わりに)。Guttman の論文を数回読んだ後に私が見つけた問題は、2D オブジェクトの z オーダーを維持できないことです。

たとえば、オブジェクトを移動すると、削除されてから再挿入されます。再挿入すると、挿入先のノードは適切な順序を追跡できなくなります。私が見た R ツリーのほとんどの実装では、配列を使用し、空の位置を見つけるだけです。再挿入すると、基本的に z オーダーの配置が破棄されます。

したがって、長方形と交差するすべての長方形を描画しようとすると、それらが返される順序は必ずしも正しいとは限りません。

この仮定は間違っていますか？配列を使用する代わりに、AVL または Red-Black ツリーを使用し、Comparerz-index で比較する a を使用してツリーに挿入できると考えていました。このように、z オーダーは常に維持されます (これが最も重要な要素です)。

返却時に仕分けも考えていたのですが、こちらの方が高くつくのではないかと思っています。

Perl で RTree を操作するための良いヒントはありますか? パフォーマンスの高い純粋な RTree 実装か、GIS プロジェクトからハイジャックできるものか? それとも、SQLite の空間インデックス サポートのようなものを使用する方が簡単でしょうか?

乾杯

KD-tree と R-tree の定義を見てみました。それらはほとんど同じであるように私には思えます。

KD ツリーと R ツリーの違いは何ですか?

R*-Treeを実装するのに十分なドキュメントはどこにありますか? 具体的には、次のことができる必要があります。

• ノードを挿入
• ノードを削除
• K 個の最近傍を検索する
• 距離 x 内にある最近傍をすべて見つけます。

このアルゴリズムが明確に文書化されている単一の場所はありますか? または、私が研究できるクリーンでオープンソースの実装はありますか? さらに良いことに、JavaScript の実装を教えていただければ、私の作業は完了です。

Rツリーを使用してDBSCANを実装しようとしています.Rツリーの形式でデータを保存できます.だから私の質問は、Rツリーにリアルタイムデータを保存する方法と、それを使用してポイントの近傍を見つけるための領域クエリをどのように実装する必要があるかです. ?

長方形バウンディングボックスのSort Tile Recursion Methodに基づいてRツリーを構築し、単独で検索する方法は? (minx, miny) と (maxx , maxy) を含む合計 12 のバウンディング ボックス

ノードを削除または更新する必要はありません。

重複の可能性:
C++ R - ツリーの実装が必要

私はほぼ一晩中狩りをしていました...

最新の C コンパイラで構築された R*-Tree 実装を知っている人はいますか?

ありがとう、チェンツ

指定されたデータ ポイントを使用してR ツリーを構築する必要があります。コードは、これらのデータ ポイントを囲む長方形を作成し、r ツリーを構築する必要があります。

Berkeley DB には R-tree などの空間インデックスがありますか?

http://www.sqlite.org/rtree.htmlは、r*tree は「合併の一部として含まれていますが、デフォルトでは無効になっています」と述べており、それを有効にするには「SQLITE_ENABLE_RTREE C プリプロセッサ マクロを定義してコンパイルするだけです」

AndroidアプリでRツリーを使用したいのですが、明らかにSQLiteはすべてプリインストールされています。ユーザーの電話/デバイスで有効にする方法はありますか?

または、NDK と自由に利用できる SQLite のソース コードを使用することは可能ですか?