4

私はJavascriptで働いています。3D空間に点がある配列があり、その点が配列内の他の点にあまり近づかないようにしたいと思います。つまり、ポイント間の距離を。より大きくしたいのですx。今私がしているのは、距離を比較し、Z次元でポイントをさらに遠くに移動するためのダブルforループを持っていることです。

while(there_are_objects_that_are_close){
    for(all_the_objects){
        for (all_the_objects){
            if (distance_between_them < 100){
                object[i].z += 150;      
            }
        }
     }
}

問題は、私がこのアルゴリズムを嫌うことです。それは本当に遅く見え、より良い解決策を探しています。文学の背景を持つ「名前のあるアルゴリズム」でもある解決策があれば、これは私たちの学校のプロジェクトの一部であるため、もっと感謝します。

4

2 に答える 2

4

各ポイントを各ポイントと比較するのが最も簡単なので、アルゴリズムは良い出発点です。

これの欠点は、ポイントの量が膨大になると、ポイントの大部分が接近していない間に各ポイントをすべてのポイントと比較する必要があるため、アルゴリズムの動作がかなり悪くなり始めることです。このような場合、十分に近い可能性のあるポイントのみをチェックするように、ポイントを分割する必要があります。

静的ポイント (移動しないポイント) の場合、いくつかの親ノードを歩いてその子ノードをチェックするだけで済むようにツリーを作成するのは簡単です (互いに近い子ほど距離が近くなります)。これは R ツリーとも呼ばれ、他のオプションも存在します。

これは 3D にも当てはまります。

どちらもウィキペディアからの画像です。

視覚的には、はるかにシンプルになっていることがわかります。半径内にあるボックスをチェックするだけで、その方法で行う作業が大幅に少なくなります。

動的ポイント (移動するもの) の場合、そのような詳細な R ツリーを保持することは現実的ではない場合があります。したがって、詳細レベルを下げて、アプローチと R ツリーの間で何かを探す必要があります。たとえば、少し大きなボックスを作成するだけでも 1 つのアプローチです。

他のアプローチには、四角形 (ポイントが含まれている場合にのみ、立方体を毎回 4 つの小さな立方体に分割する) とグリッド (同じサイズの立方体を多数作成する) の使用が含まれます。R ツリーとその他の構造の詳細については、こちらを参照してください。

これの派生物は、たとえば、地球を三角形に分割する測地線グリッドですが、これは 3D には適用できない場合があります (三角形を地球の中央の頂点に接続しない限り)。

画像はウィキペディアより。

于 2012-11-19T22:49:53.310 に答える
0

ドットをより小さな領域に分割して比較する方法を見つける必要があります。

Z 次元を変更することによってのみドットを移動できるため、最初に考えたのは、Z 次元の値でドットを並べ替え、Z 次元が近いドットのみを比較することです。しかし、まだ領域を分割する方法がわかりません。

于 2012-11-20T03:47:23.847 に答える