0

さまざまなオブジェクトの検出を処理するプログラムを作成しようとしています。オブジェクトには、原点、幅、高さ、および速度があります。すべてのオブジェクトが他のすべてのオブジェクトとチェックしないようにデータ構造/アルゴリズムを設定する方法はありますか?

私が回避しようとしている問題のサンプルコード:

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
       }
    }
}
4

2 に答える 2

2

四分木を使用すると、別の四角形と交差するすべての四角形をすばやく見つけることができます。長方形以外の形状を処理する必要がある場合は、境界ボックスが交差するオブジェクトを最初に見つけることができます。

四分木の一般的な用途

  • ...
  • 2 次元での効率的な衝突検出
  • ...
于 2012-07-06T21:57:59.460 に答える
1

他の回答で述べたように、四分木構造を使用して衝突検出を高速化できます。

優れた四分木実装を備えた GEOSオープンソース C++ ライブラリをお勧めします。quadtree クラスのドキュメントは次のとおりです。

したがって、疑似コードは次のようになります。

Quadtree quadtree;
// Create and populate the quadtree.
// Change it whenever the balls move.

// Here's the intersection loop:
for (int i=0; i<ballCount; ++i) {
    Envelope envelope = ...;  // Get the bounds (envelope) of ball i
    std::vector<void*> possiblyIntersectingBalls;
    quadtree.query(envelope, possiblyIntersectingBalls);
    // Now loop over the members of possiblyIntersectingBalls to check
    // if they really intersect, since quadtree only checks bounding
    // box intersection.
}
于 2012-07-06T22:06:26.260 に答える