4

n 個の3 次元オブジェクト (多面体) があるとします。すべてのオブジェクトの交差を計算する最速の方法は O(n ^ 2) ですか?

現在、基本的に T(n) を n ^ 2 に等しくするライブラリを使用しています。

for each object: // there are n objects
    get list of intersecting objects // this takes n steps

これは文字通り n ^ 2 ステップかかります。

私が考えることができる唯一の高速な方法は、依然として O(n ^ 2) ですが、T(n) = n(n+1) / 2、または (n*n + n) / 2 です。

擬似コードは次のとおりです。

for(int i = 0; i < len(objects) - 1; i++)
    for(int j = i + 1; j < len(objects); j++)
        if object at i intersects object at j:
            object at i . addToIntersectList ( object at j )
            object at j . addToIntersectList ( object at i )

この方法では、2 つのオブジェクトが 2 回交差するかどうかを確認する必要がありません。反復処理中のリストには約 3000 個のオブジェクトがあることがわかっています。このアルゴリズムは 4501500 ステップかかりますが、元のアルゴリズムはそのほぼ倍の 9000000 ステップかかります。

何か不足していますか？これは私たちが得ることができる最高のものですか？

4

3 に答える 3

3

ループ処理を変更することで O(n²) のパフォーマンスを改善する方法はいくつかありますが、衝突チェックの方法について他のことを変更することで大幅に改善することができます。

コードの主な非効率性の 1 つは、各多面体を他のすべての多面体に対して完全にチェックすることに依存している方法です。これは、常に必要であるとは限りません。2 つの形状が近接していない場合は、集中的な交差テストを行う必要はありません。また、広大な空間によって分離された形状の 2 つのクラスターがある場合は、2 つのクラスターの各メンバーをチェックする必要はありません。他のクラスターのすべてのメンバーも同様です。この種の最適化を実行するためのいくつかの手法には、次のものがあります。

これらの手法を使用して、衝突検索を大幅に高速化できます。

于 2014-06-27T19:39:32.150 に答える
0

すべてのオブジェクトを 3D ツリー構造に配置できます。次に、何らかの意味で互いに「近い」ペアをチェックするだけで済みます。

これは、空間情報を格納する一般的な方法です。たとえば、neo4j 空間には、場所を保存し、「near to」タイプのクエリを実行するための ak ツリーが内部にあります。

于 2014-06-27T22:16:09.403 に答える