問題タブ [r-tree]

次の方法で、spatialindex ライブラリを使用してメイン メモリの R* インデックスを作成しました (DBStream は、bulkLoading のインターフェイスを実装しています)。

私のデータは読み取り専用です。つまり、ツリーを 1 回だけ作成して保存し、プログラムを使用するたびに永続ストレージから再ロードしたいと考えています。明らかに、memStorage を自分で保存してロードすることはできますが、そこから RTree を再作成するにはどうすればよいでしょうか?

私はspatialindex（http://libspatialindex.github.com/）ライブラリを使用してRツリーをバルクロードしています：

構築されたツリーに関する情報で、以下が出力されます。

今、私はディスクに保存したものをロードしようとしています：

ツリーにはノードが1つだけあります（ツリーの出力は次のとおりです）。

私は何を間違えますか？ツリー全体をディスクからロードしないのはなぜですか？

R* Tree を永続的な (ディスクベースの) ものとして実装するにはどうすればよいですか? R* ツリー インデックスまたはリーフ値を保存するためのファイルのアーキテクチャは何ですか?

注: さらに、そのような永続的な R* ツリーで挿入、更新、および削除操作を実行するにはどうすればよいですか?

メモ II: バルク ロード機能を備えたインメモリ R ツリーを実装しました。しかし、ディスクベースのものについて話すとき、それはまったく無関係だと思います.

R *ツリーの挿入アルゴリズムの手順は何ですか？

注：挿入によってツリーを構築できるようにしたいです。最適な葉を選択するためにどの条件を選択しても、常に最大のオーバーラップと最大の面積をカバーするクラップツリーを提供します（ツリーの各レベルで追加した後の最小のオーバーラップ領域、ツリーの各レベルでの最小の拡張率などをテストします） 。

さて、このR *ツリーが非常に美しく挿入されることによってどのように構築されるか（ウィキペディアから）：

PyPIからRtree0.7.0をインストールしよImportError: No module named indexうとしましたが、使用しようとすると取得し続けます。ダウンロードページからRtree-0.7.0.win32.exeをダウンロードして実行しましたが、すべてが正しくインストールされているようです。

これが私が（Python 3.2.2シェルから）受け取る完全なエラーメッセージです：

エラーメッセージは、「index」という名前のモジュールがないことを示していますが、C:\Python32\lib\site-packages\rtree\ディレクトリを見ると、そこにあることがわかります。

それでもImportError: No module named indexエラーメッセージが表示される原因は何でしょうか。また、RTreeモジュールを使用できるように修正するにはどうすればよいですか。

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

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

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

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

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

ポイントとして保存されている長方形のリストがあります。現在、データは次のようになっています。

長方形が別の長方形に含まれているかどうかをテストする基本的な関数もあります。

長方形のセットとその子を作成したいのですが、どのように保存すればよいかわかりません。私はこのようなことを考えています：

これのコンテキストは、ボックスがWebページ上の要素を表すということです。データ構造は基本的なマークアップを生成することを目的としているため、上記の構造は次のようになります。

1. ソース/ゴールのデータ構造はこれに適していますか？そうでない場合は、何ですか？
2. ソースからゴールに到達するにはどうすればよいですか？
3. 友人がr-treeの使用を提案しました。それはここで意味がありますか？

この論文に基づいて R* ツリーの実装に取り​​組んでいます。分割軸の選択アルゴリズムについていくつか質問があります。

R* ツリーは、適切な分割を見つけるために followmg メソッドを使用します。各軸に沿って、エントリは最初に低い値で並べ替えられ、次に長方形の高い値で並べ替えられます。

長方形の下限値/上限値とはどういう意味ですか?

各分布について、良さの値が決定されます。これらの良さの値に応じて、エントリの最終的な分布が決定されます。3 つの異なる Goodness 値と、それらをさまざまな組み合わせで使用するさまざまなアプローチが実験的にテストされています。

(I) 面積値 面積[bb(第1グループ)] + 面積[bb(第2グループ)]

(II) margin-value margin[bb(第 1 グループ)] + margin[bb(第 2 グループ)]

(III) 重複値領域 [bb(第 1 グループ) + bb(第 2 グループ)]

ここで、bb は一連の長方形のバウンディング ボックスを示します。

とはどういう意味margin-valueですか? この値を計算するにはどうすればよいですか?

このR*ツリーの実装を読んでいたところ、紙で定義されている方法とは異なる方法でオーバーラップを計算していることに気付きました。

この論文では、オーバーラップは次のように定義されています。

与えられたノード/rectkについて、 kとkの各兄弟（ kを含まない）の間の交点の面積の合計を計算します。

オーバーラップ拡大は、この値のデルタであり、アイテムrがkに追加された場合のノードkのオーバーラップは何ですか。

このようなもの：

他の実装では、挿入されているアイテムと特定のノードの交差領域で並べ替えます。このようなもの：

明らかに、それらの実装は、論文の定義よりも計算量が少なくて済みます。ただし、2つの計算が等しくなければならない理由は明らかではありません。

だから私の質問は：

1. 2つの計算は常に同じサブツリーが選択されることになりますか？なんで？
2. 異なるサブツリーが選択される結果になる場合、結果は論文の定義と同じくらい良いですか、それとも近いですか？それとも誤った選択でしたか？

編集：それらの実装を読み直して、2人の兄弟の交差点を比較しているのではなく、それぞれの潜在的な葉と挿入されているアイテムの交差点を比較していることに気付きました。不思議なことに、彼らは挿入されているアイテムと最も重ならない兄弟を選んでいます。挿入するアイテムと最も重なるノードに挿入しませんか？

opencv2.1.0 を使用していますが、opencv 経由で r-tree 構造を使用したいと考えています。私の考えは、r-tree を使用して、特定の線分 (すべて 2 次元) の近くの線分を見つけることです。このrツリー関数の使用方法が本当にわかりません。各線分の終点座標があります。opencv2.1.0 で 2D 線分に r-tree を使用する方法を誰かが知っている場合は、その方法といくつかの例を教えてください。明確にするために、写真も挿入しています。濃い線は指定された線、破線はその他の線です。だから私は暗い線に近いすべての破線が欲しい. 私はこのような機会がたくさんあります。だから私は効率的な方法が欲しいので、r-treeを探しています。