問題タブ [quadtree]

私は最近、バイナリ スペース パーティショニング ツリーと、その 3D グラフィックスおよび衝突検出への応用について学びました。また、四分木と八分木に関連する資料を簡単に調べました。bsp ツリーではなくクワッドツリーを使用するのはいつですか、またはその逆ですか? それらは交換可能ですか？次のような表に記入するのに十分な情報があれば満足です。

A、B、Cとは？

特定の長方形または円内のすべてのオブジェクトをすばやく取得できるように、それぞれが x 座標値と y 座標値を持つ一連のオブジェクトを格納する高速な方法を決定しようとしています。オブジェクトの小さなセット (~100) の場合、単にそれらをリストに格納し、それを反復処理する単純なアプローチは比較的迅速です。ただし、はるかに大きなグループの場合、これは遅くなると予想されます。次のコードを使用して、x座標でソートされたツリーマップとy座標でソートされたツリーマップのペアにもそれらを格納しようとしました。

これも機能し、より大きなオブジェクトのセットの方が高速ですが、それでも思ったより遅くなります。問題の一部は、これらのオブジェクトが移動し、このストレージに挿入し直す必要があることです。これは、ツリー/リストからオブジェクトを削除して再度追加することを意味します。そこにはもっと良い解決策があるはずだと思わずにはいられません。私はこれをJavaで実装していますが、違いがあれば、解決策はより有用なパターン/アルゴリズムの形になると思います。

私は何年もの間、ネット上で quadtree/quadtree ノードの実装を探していました。基本的なものはいくつかありますが、実際にゲームで使用できるものはありません。

私の目的は、衝突検出などを処理するためにオブジェクトをゲームに格納することです。四分木が使用するのに最適なデータ構造であると 100% 確信しているわけではありませんが、私が読んだ限りではそうです。私はすでに赤黒木をコーディングしましたが、パフォーマンスが自分のゲーム (Ankh のようなアドベンチャー 3 人称ゲーム) にとって十分であるかどうかはよくわかりません。

C++ で基本的だが完全な quadtree クラス (または octree) を作成するにはどうすればよいですか? 衝突に四分木をどのように使用しますか?

「[この座標] から 'n' メートル以内にあるすべての座標を返す」と言ってクエリできる GPS 座標の大規模なデータベースを作成したいと考えています。

Sqlserver2008 で Quadtree Indexing を実装する方法を知りたいですか?

オブジェクトをすばやく取得できるように、四分木を使用するクエリを呼び出す .net モジュールを作成したいと考えています。

上記の機能を実装するにはどうすればよいですか?

前もって感謝します

i は次の四分木のような構造を持ち、各セルは内部ノードまたはリーフのいずれかになります。葉であれば、色を保存できます。内部ノードの場合は、4 つの子 (リーフまたは内部ノードのいずれか) へのポインターを格納します。

セルが内部ノードの場合、色を保存する必要はありません。葉の場合、子へのポインターを格納する必要はありません。したがって、色と子は同じメモリ (結合) を共有する必要があります。

葉を内部ノードに変換し、現在のセルが現在持っているのと同じ色で子 (葉) を作成する関数 split() があります。

今、関数 split() をデバッグしています。私は行にデバッグポイントを設定します

だから今：デバッガーはこの行で停止し、メンバー値を観察します。行が実行されるように手順ステップを実行します（命令カーソルは次の行にあります）。行が実行された後、children[0] のポインター値は同じままです。代わりに、children[2] のポインタ値が (float 値 b とともに) 変更されました。

誰かが私にこの振る舞いを説明できますか?? 私は何を間違っていますか？

ありがとう！

衝突検出に使用する (点ではなく) 四角形の四分木を実装しようとしています。

何らかの理由で、重なり/交差/衝突が常に検出されるとは限りません。これは、挿入されたコライダーが近くのコライダーを探す方法と関係があると思われます (Quadtree.as の「COLLISION A」および「COLLISION B」セクションを参照)。なぜこれが起こるのか誰でも特定できますか？

以下は、四分木と他のいくつかのクラスの私のコードであり、一緒にコンパイルすると、「四分木」が「不正確」であると私が言うときに私が何を意味するかを示します。実際には Quadtree.as を見る必要があるだけですが、他のクラスと一緒にコンパイルすると、私の問題を理解するのに役立ちます。

ありがとう！

Quadtree.as:

Main.as:

TestObject.as:

Collider.as:

TestCollider.as:

2D空間インデックスの質問：

ノードに絶対座標も絶対スケールも含まれていない、本質的に無限*の四分木であるデータ構造を何と呼びますか？各ノードの座標系は単位正方形（0,0）-（1,1 ）、そしてトップレベルのノードが完全に固定されていないのはどれですか？

もちろん、これは四分木ですが、どのような種類の四分木ですか？（一般的な名前はありますか？文献で名前が付けられ定義されている数十種類の四分木を見てきましたが、この特定のものは見ていません。）

シーンをレンダリングするために、いくつかの開始ノード（必ずしもルートである必要はありません）、ピクセル単位のサイズ、および画面上の位置が与えられます。次に、現在の変換行列を使用して座標をスケーリングすることにより、ノード内のすべてのオブジェクトを描画します。これをスタックにプッシュし、ツリーを下るときに半分にします。したがって、ノードの絶対座標は、レンダリング中の一時的な作業変数を介してのみ使用可能であり、データ構造自体には含まれていません。

ノード内のオブジェクトがノードの外側（たとえば、単位正方形の外側）に移動した場合、別のノードに再割り当てするためにそのオブジェクトを親に渡します。オブジェクトが断片化した場合（たとえば、小惑星が弾丸に当たった場合）、小さい部分は子ノードに渡されます。子ノードは、各ノード内の単位正方形の正規化を維持するために座標を適切にスケーリングする必要があります。

ここでの空間インデックスで使用される従来のクアッドツリー実装との主な違いは、オブジェクトの座標が、オブジェクトが含まれているノードの座標系に常に相対的であるということです。この相対主義は、位置だけでなくスケールにも当てはまります。

*絶対座標がない場合は無限大。倍精度浮動小数点座標でさえ、絶対測位に使用すると位置とサイズに制限があります。

多数の円 (Ellipse2D) で満たされたパネルがあります。円は 2 次元配列 (行と列) に格納されます。

私の目標は、マウスを円の上にドラッグするときに円を「ペイント」できるようにすることです。最終的には、選択図形に含まれるすべての円の色を変更する選択図形を使用したいと考えています。

2次元配列全体を継続的にスキャンし、現在の点が円の内側にあるかどうかを確認するマウスドラッグリスナーを使用しています。そのようです：

上記のコードは機能しますが、すべてのオブジェクトをチェックしているため、非常に低速です (1000 円以上)。

もっと良い方法があるはずです。四分木について少し読んだことがありますが、四分木が必要以上の馬力を持っているかどうかはわかりません。

ありがとう

以下のコメントのいくつかに基づいて、次の変更を加えました。Circles は線形の ArrayList になりました。draw メソッドは単純に円を塗りつぶします。この変更により、速度が 2 桁向上しました。今でははるかにうまく機能します。ただし、パネルを適度な速度でスイープして、いくつかの円を逃すことはできます。したがって、さらに最適化する必要があるかもしれません。

私の特定のプロジェクトでは、これまで使用したことのない四分木を使用する必要があるようです。私が読んだことから、問題に対するブルートフォース攻撃がもたらすよりも大幅なパフォーマンスの向上が可能になるはずです。これらのPythonモジュールのいずれかが良いですか？

• Quadtree 0.1.2 <=いいえ： Python3.1で実行できません
• QuadTree <=はい：長方形での作業中は簡単
• quadtree.py <=いいえ：必要な操作はサポートされていません

編集1： pygame wikiで提示されているものよりも優れた実装を知っている人はいますか？

編集2： Pythonでのパスファインディング手法に他の人が役立つと思われるリソースをいくつか示します。

• ゲームエンティティナビゲーション
• クーティを捕まえる

四分木 (4 分木) を使用して、特定の BMP に情報を保持しようとしています。
BMP を指定してツリーを構築する方法を理解するのに苦労しています。

基本的に、すべての葉がピクセルを表すような構造になっています。各ノードには 4 つのポインターがあり、それぞれが画像内の残りの 4 つの象限の 1 つを指しています。したがって、各ノードは現在の画像を 4 つの部分に分割します。リーフに到達するまでに、1 つの特定のピクセルに到達します。

特定の画像をマッピングするためにツリーを構築する方法がわかりません。画像の次元が 2 のべき乗であると仮定すると、どうすればよいでしょうか。再帰関数がおそらくこれを最もエレガントに実行できることは理解していますが、画像のどこにいるのかを追跡する方法を理解するのに苦労しています。

これは C++ であり、現在私の quadtree.h ファイルには Node* ルートが含まれており、ノードはピクセル要素と他のノードへの 4 つのポインターを持つ構造として定義されています。各内部ノード (非リーフ ノード) は、それが導く 4 つの RGB 値すべての平均値を保持する必要があります。

アルゴリズムを作成しようとしていますが、.h ファイルに 1 つまたは 2 つの構造体を含める必要があると思います。この問題を解決するためのより良い/よりクリーンな方法はありますか?