問題タブ [r-tree]

Windows 7 64 ビットで Python の Canopy インストールを使用しています。Rtree は正しくインストールされているようです。

ただし、rtree をインポートしようとすると、次のエラーが発生します。

Ubuntuでも、同じではないにしても、同様の問題がありました。Software Managerを介してlibspatialindexを直接インストールすることで解決しました。これは Windows では不可能であり、インストールする明確な方法が見つかりません。

OSGeo4W スイート全体をダウンロードしてインストールし、Rtree を Canopy に再インストールしました。libspatialindex がバンドルに含まれていることを願っています。それはうまくいきませんでした。

この問題を解決する方法はありますか?

現在、「データモデリング」コースに参加しています。私の最後のプロジェクトでは、「空間検索用の R ツリー インデックス」について調査する必要があります。しかし、私は主題に関する多くの概念 (空間データ、多次元データなど) にまったく精通していません。そのため、wikiを読み、新しい概念に遭遇したので、それらを Web サイトで学ぼうとしました。仕方。
しかし、このトップダウンのアプローチは、これを行う上で非常に効率的な方法だとは思いません。したがって、R ツリーを理解し、できればそれから何らかの実装を行うために、事前に読む必要がある方法/リストを誰かが提案できれば、本当に感謝しています。

ブースト R ツリー ( boost::geometry::index::rtree)を反復処理する効率的な方法が見つからないようです。これまでに思いついた唯一の方法は、非常に大きな境界ボックスを使用してクエリを実行し、すべての要素のコピーがベクトルで返されるようにすることですが、これは明らかにスペース効率も時間効率もありません。理想的には、STL スタイルの反復子を使用して、通常の方法でツリーを反復処理したいのですが、これは可能ではないようです。

私は現在、3D 環境内でプレイヤーに最も近い 30 個の最も近いプロセスのキューを構築するスレッドを必要とするプロジェクトに取り組んでいます。

これらのプロセスはすべて、環境内を動き回ることができ、配置された開始ノードを離れることもできます。R ツリーの使用を検討しましたが、挿入時間が非常に長いため、あまり実用的ではないようです。

KD ツリーは、静的な環境でのみ機能する傾向があるため、機能しません。

また、これはメインの更新スレッドとは非同期で実行されるため、アトミックなアプローチが最適です。

誰かがアプローチを提案できますか？

ツリー検索アルゴリズム、特にクワッド ツリーと r ツリーに関して、最近傍を見つける際にエッジ エラーをどのように説明しますか。言葉で説明するのが苦手なので、絵を描いてみました。

画像の場合、最も近い隣人を見つけるための入力座標は緑で、「見つかった」最も近い隣人は赤です。実際の最近傍は青色です。

このクワッド ツリーでは、青色の右下の象限がその 1 つの赤い点のみで検索されますが、実際には、入力座標 (緑) はエッジに非常に近く、実際には青色の点により近くなっています。

座標が 1 つの四角形内にあるがエッジに非常に近い場合、R ツリーと同様に、次のように別の四角形のポイントに近くなります。ここで、白い点は座標が指定されています。

完全に赤いボックス内にありますが、マゼンタ ボックス内のポイントに近くなっています。

kd-tree、Range tree、quad-treeなどの範囲検索データ構造の一部を知っています。しかし、すべての実装はメモリ内にあります。パフォーマンスの高い I/O 効率でセカンダリ メモリに実装するにはどうすればよいでしょうか?

条件は次のとおりです。

1): 2 次元上の点の静的セット。

2): クエリのみで、インセットや削除はありません。

3): 二次記憶に適応します。

ありがとう。

2D ポイントを rtree (ver. 0.8.2) に保存し、Python を使用して削除しようとしています。rtree が長方形 (または 3D のボックス) で機能することは理解していますが、ポイントは長方形のサブセットであると思います。

rtree から項目を削除しているときに、奇妙な動作が発生します。以下のスクリプトは、動作を示しています。

出力は次のとおりです。

ドキュメントから ( http://toblerity.org/rtree/class.html ):

指定された座標内の指定された「id」を持つインデックスから項目を削除します。

パラメーター：

id – long integer このインデックス エントリの識別子である long integer。インデックスに挿入する ID は一意である必要はありません。ID が一意である必要がある場合は、ユーザーが一意であることを確認する必要があります。

座標– シーケンスまたは配列 ディメンション * インデックスから削除する項目の各次元の最小座標と最大座標を表す 2 つの座標ペア。それらの順序は、インデックスのインターリーブ データ メンバーによって異なります。これらは、アイテムを含む空間の座標ではなく、アイテム自体の座標です。id パラメータとともに、削除する項目を決定します。これは、numpy 配列プロトコルを満たすオブジェクトである可能性があります。

idしかし、ご覧のとおり、指定されたが指定された座標内にないポイントが、出力の 4 行目で削除されています。

idドキュメントはまた、挿入または削除のいずれにおいても s が一意である必要がないことを明確に指定しています。(この例で繰り返さ0 == idれているのは、私のアプリケーションでは重複したids が必要なため、意図的なものです。同じ「もの」に対して複数のポイントが必要です。)

xmin == xmaxまた、とを使用して点をインデックスできることも確認しましたymin == ymax。

ライブラリの使い方が間違っているのでしょうか、それとも libspatialindex (Python rtree の背後にあるバイナリ ライブラリ) の動作が rtree ドキュメントの状態と異なるのでしょうか?

おそらく長期保存のために、3D R* ツリーを作成する必要がありますが、パフォーマンスも問題になります。ツリーを作成するために、Boost の spacialindex を使用することにし、基本的に 2 つの可能な方法を見つけました。

ここにあるオブジェクトを使用して直接作成します: Index of polygons stored in vectorですが、R* ツリーを再度作成せずに格納してロードすることはできません。

または、ここで説明されているように、マップされたファイルを使用することもできます: Boost.Interprocess を使用してマップされたファイルに格納されたインデックス、ただし、この場合、クエリのパフォーマンスが十分に優れているかどうかはわかりません。

私の r ツリーには数千のエントリが含まれますが、おそらく約 100,000 未満です。ここで私の質問は、標準オブジェクトを使用する場合と比較して、マップされたファイルを使用することで大きなパフォーマンス上の問題はありますか? また、約 100,000 の値の R* ツリーの作成にそれほど時間がかからない場合 (すべてのバウンディング ボックスと対応するキー/データをファイルに保存できます)、マップされたファイルを作成し、プログラムを実行するたびにツリーを作成するだけですか?

ドキュメンテーションは実際には多くの情報を提供していないので、誰かが私をここで助けてくれることを願っています (それでも、libspacialindex のドキュメンテーションよりは優れています)。