問題タブ [quadtree]

四分木の前方反復子を実装しようとしています。残念ながら、四分木のトラバーサルに関するリソースを見つけることができないようです。

誰かが私を正しい方向に向けることができますか?

空間データ構造に関する本をアドバイスしてください。興味がありQuadtrees and Octreesます。

しばらく前に四分木を使ったパスファインディングでプロジェクトを行いましたが、そのパフォーマンスを改善したいと思います。ノードの隣接関係を決定するためにテッセラル演算を使用すること（このページのように、ブリティッシュコロンビア大学の地理学部の厚意により）は、現在使用しているブルートフォース方式よりもはるかに高速であるようです（私はチェックしています共有エッジ。静的なクワッドツリーでは正常に機能しますが、マップが変更された場合はオーバーヘッドが大きくなりすぎます）。

隣接アルゴリズムのセクションで何が言われているのかは多かれ少なかれ理解していますが、どのように始めればよいのかよくわかりません。私は主にC＃に興味がありますが、言語に関係なく、私が見ることができるテッセラル算術を操作するためのソースがすでに浮かんでいるとしたら、それは素晴らしいことです。そうでなければ、誰かが私に足し算/引き算のキャリーに対処するためのいくつかの指針を与えることができますか？

四分木のスタイルで完全な n 分木を操作する Java ライブラリを探しています。実際には、n = 9 の場合に必要なだけですが、他の人にとっては余分な一般性が価値があると思います。これは、私が開発している GIS 用であり、2D 領域が 3^kx 3^k グリッド上の要素に分割されます (四分木を使用する場合は 2^kx 2^k グリッドではなく)。特に、ノードの追加、ツリーのトラバース、および範囲検索を実行するための効率的なメソッドをライブラリに持たせたいと考えています。あなたはそのような図書館を知っていますか？

Google 検索では見つかりませんでしたが、自分で作成する前に、その存在を再確認したいと思います。

ありがとう。

私はこれを研究してきました：

https://github.com/mikechambers/ExamplesByMesh/blob/master/JavaScript/QuadTree/src/QuadTree.js

四分木についての一般的な考え方は理解していると思いますが、四分木がどのように機能するか、および上記の実装について 2 つの質問があります。

1. 数ミリ秒ごとにツリー全体を再構築する必要はありませんか? Javascript では、これを行うのは非常に遅くありませんか?

2. http://davzy.com/screenshots/skitched-20120318-180324.pngのようなものがある場合、同じクワッド内の他のドットを見つけるのは簡単ですが、3 つの異なるクワッドに当たる長方形があります。これらのクワッドの 3 つすべての子として表示する方法はありますか?

3. 上記の例の 144 では、この Node.prototype._classConstructor = Node; と表示されています。何が起こっているのか興味があります。プロトタイプは、クラス内で将来使用する関数または変数を定義する方法だと思っていたので、この行が何をするのかわかりません。

LIDAR ファイルから大量のポイント クラウド データを表示および変更するために使用するアプリケーションがあります (それぞれ最大数ギガバイトで、同時に読み込まれることもあります)。アプリでは、ユーザーはロードされたポイントの 2D 画像を (上から) 表示し、プロファイルを選択して別のウィンドウで (横から) 表示することができます。繰り返しますが、これには数百万のポイントが含まれ、それらは OpenGL を使用して表示されます。

データを処理するために、四分木ライブラリもあり、機能しますが、非常に低速です。しばらく使用されていましたが、最近、LIDAR ポイントの形式が変更され、LidarPoint オブジェクトに多数の属性 (クラス メンバー) を追加する必要がありました。これにより、サイズが大きくなり、パフォーマンスがほとんど使用できないレベルにまで影響しました (5 分と考えてください)。単一の 2GB ファイルをロードする場合)。

四分木は現在、指定された容量と定義された境界 (空間クエリ用) を持つ LidarPoint オブジェクトの単純な配列である PointBucket オブジェクトへのポインターで構成されています。バケット容量を超えると、4 つのバケットに分割されます。また、ポイント データが大量のメモリを消費している場合に、ポイント バケットがディスクにダンプされるようにする、一種のキャッシュ システムも用意されています。これらは、必要に応じてメモリにロードされます。最後に、すべての PointBucket には、元のデータの n 番目ごとのポイントを保持し、ズーム レベルに応じてデータを表示するときに使用されるサブバケット/解像度レベルが含まれます。これは、一度に数百万のポイントを表示するのは、そのレベルの詳細は必要ありませんが、非常に遅いためです。

そこからイメージしていただければ幸いです。そうでない場合は、お問い合わせください。詳細を提供するか、さらにコードをアップロードできます。たとえば、現在の（そして遅い）挿入方法は次のとおりです。

私の質問は、このデザインを改善する方法を考えられるかどうかです。メモリに収まらない大量のデータを処理するときの一般的な戦略は何ですか? 四分木をより効率的にするにはどうすればよいですか? ポイントのレンダリングを高速化する方法はありますか?

Quad-Tree を使用して 2-D 高速衝突検出を実装しようとしています。

私の知る限り、Quad-Treeはリージョンを北西、北東、南東、南西の4つのサブリージョンに分割します。この分割は正方形で完全に機能します。しかし、領域が正方形ではない長方形の場合はどうなるでしょうか? その場合、長辺と短辺を均等に分割することはできず、短辺がどこまで分割できるかを決定します。

私はこれで正しいですか？ということですか？

「通常の」方法で画像（正方形）を四分木に変換する必要があります-4つにスライスし、各ピースに1色しかないかどうかを確認します。はいの場合: ノードを閉じます。そうでない場合: 繰り返します。

オープンソース プログラムを知っている人はいますか?

できれば Java ですが、どの言語でも使用できます。

ありがとう。

Quadtree 構造を実装する Java (Eclipse) でクラスを作成しています。この構造に慣れていない方のために説明すると、下の図に示すように、再帰的に他の 4 つの正方形に分割される単純な正方形です。

以下のようなデータ構造を表示したい。簡単な実装のための良いアイデアを持っている人はいますか?

ありがとう