33

2D 衝突検出に四分木を使用しようとしていますが、実装方法に少し困惑しています。まず、4 つのサブツリー (各象限を表す 1 つ) と、1 つのサブツリーに収まらないオブジェクトのコレクションを含む 4 つ木があります。

ツリー内のオブジェクトの衝突をチェックするときは、次のようにします ( 2D 衝突検出のための QuadTree のおかげです)。

  1. 現在のノード内のオブジェクトとの衝突についてオブジェクトをチェックします。
  2. スペースがオブジェクトと重なっているサブツリーについては、再帰します。

四分木ツリー内のすべての衝突を見つけるには:

  1. 現在のノード内の各オブジェクトを、現在のノード内の他の各オブジェクトに対してチェックします。
  2. 各サブツリーに対して現在のノードの各オブジェクトをチェックします。

四分木に挿入するには:

  1. オブジェクトが複数のサブツリーに収まる場合は、現在のノードに追加して戻ります。
  2. それ以外の場合は、それを含むサブツリーに再帰します。

四分木を更新するには:

  1. 各サブツリーに再帰します。
  2. 現在のノードのいずれかの要素が現在のツリーに完全に収まらなくなった場合は、それを親に移動します。
  3. 現在のノードのいずれかの要素がサブツリーに収まる場合は、それをサブツリーに挿入します。

これでいいですか？改善できますか？

4

3 に答える 3

38

四分木構造が最適ではありません。ノードごとに 4 つのサブツリーを保存するのは正しいですが、実際のオブジェクトは内部ノードではなく、リーフ内にのみ保存する必要があります。したがって、実際のオブジェクトを保持するコレクションをリーフに移動する必要があります。

操作の実装を見てみましょう:

  1. 四分木にオブジェクトを挿入:
    オブジェクトが現在のノードと交差するかどうかを確認します。その場合は、再帰します。リーフ レベルに達したら、オブジェクトをコレクションに挿入します。
  2. 四分木からオブジェクトを削除する:オブジェクト
    を挿入する場合とまったく同じ手順を実行しますが、リーフ レベルに達したらコレクションから削除します。
  3. オブジェクトが四分木内のオブジェクトと交差するかどうかをテストします。オブジェクトを挿入する場合とまったく同じ手順を実行します
    が、リーフ レベルに達したら、コレクション内のすべてのオブジェクトとの衝突をチェックします。
  4. 四分木内のすべてのオブジェクト間のすべての衝突をテストします。四分木内のすべてのオブジェクトに対して
    、単一オブジェクトの衝突テストを実行します。
  5. 四分木を更新する:
    位置が変更された四分木からすべてのオブジェクトを削除し、再度挿入します。

これにはいくつかの利点があります。

  • 葉にオブジェクトを格納するだけで、四分木での操作を非常に簡単に処理できます (特殊なケースが少なくなります)。
  • 四分木には深さの異なるリーフを含めることができるため、カバーする空間領域に応じて四分木の密度を適応させることができます。この適応は実行時に発生する可能性があるため、オブジェクト/ノードの比率が最適に保たれます。

唯一の欠点:

  • オブジェクトは、quadtree 内の複数のコレクションに属することができます。重複なしですべてのオブジェクトを列挙するには、四分木の外側に追加の線形コレクションが必要になります。
于 2011-02-13T03:05:32.997 に答える
13

クワッド ツリーは、常に衝突検出に最適なデータ構造であるとは限りません。四分木のオーバーヘッドは無限になる可能性があり (ツリーの深さを制限しない場合)、最悪の場合、速度がまったく向上しません。代わりに、スパース グリッドの使用を検討することをお勧めします。これにより、複数のツリー レベルをトラバースするという追加のオーバーヘッドがなく、四分木よりも優れたパフォーマンスが得られます。

他の完全に異なるアプローチもあり、さらに優れている可能性があります。たとえば、次のモジュールで行ったように、Zomorodian と Edelsbrunner のアルゴリズムを実装してみることができます。

以下は、これらの問題について詳しく説明した、私が書いたいくつかの記事です。

特に、前のセクションのベンチマークを見ると、調査したすべてのライブラリの中で、R ツリー、グリッド、またはセグメント ツリーなどの他の衝突検出方法と比較して、クワッドツリーのパフォーマンスが非常に低い傾向にあることがわかります。

于 2015-06-15T20:31:22.097 に答える