1

そのため、多数の n 次元粒子のシミュレーションに取り組んでおり、すべての点のペア間の距離を知る必要があります。いくつかのエラーを許容し、距離がしきい値を超えた場合にまったく関係がないことを考えると、これを達成するための良い方法はありますか? dist(A,C)必要であり、すでに知っていてdist(A,B)、dist(B,C)それを でバインドして、結果を並べ替えられた配列に格納できるかどうかはかなり確信してい[dist(A,B)-dist(B,C) , dist(A,B)+dist(B,C)]ますが、より良いものがあれば車輪を再発明したくありません。

次元数がロジックに大きな影響を与えるとは思いませんが、一部のソリューションではそうなるでしょう。前もって感謝します。

4

2 に答える 2

2

問題が単にすべてのペア間の距離を計算することである場合O(n^2)、より良い解決策の可能性がない問題になります。ただし、距離があるしきい値よりも大きい場合Dは、関心がないということです。これにより、より優れたアルゴリズムの機会が開かれます。

たとえば、2D の場合、スイープライン テクニックを使用できます。ポイントを辞書順に並べ替えます。最初は で、y次にで並べ替えますx。次に、幅のストライプで平面をD下から上に掃引します。そのストライプが平面を横切って移動すると、新しいポイントがストライプの上端から入り、下端から出ます。アクティブなポイント (つまり、現在ストライプ内にあるポイント) は、x座標によってソートされた、段階的に変更可能な線形データ構造に保持する必要があります。

ここで、新しいポイントがストライプに入るたびに、現在アクティブなポイントを(軸Dに沿って測定して) 左と右にチェックする必要があります。xそれで全部です。

このアルゴリズムの目的は (スイープ ライン アプローチの場合によくあることですが) 実際の複雑さを から遠ざけO(n^2)たりO(m)、 に近づけたりすることです。ここmで、 は実際に関心のある相互作用の数です。O(n^2).

上記は 2 次元の場合に適用されます。n次元の場合、別の手法を使用したほうがよいでしょう。ここでは、ある種のスペース分割がうまく機能するはずです。つまり、パーティション間の距離が よりも大きいことがわかっている場合D、これらのパーティションの特定のポイントを相互に考慮する理由がないという事実を利用するためです。

于 2012-11-03T18:14:06.907 に答える
0

特定のしきい値を超える距離が関係なく、このしきい値が大きすぎない場合は、これをより効率的にするための一般的な手法があります。空間分割データ構造を使用して、隣接するポイントの検索を制限します。可能なオプションは次のとおりです。

  • ビニング。
  • ツリー: quadtrees(2d)、kd-trees。
  • 空間ハッシュによるビニング。

また、点 A から点 B までの距離は、点 B から点 A までの距離と同じであるため、この距離は一度だけ計算する必要があります。したがって、次のループを使用する必要があります。

for point i from 0 to n-1:
     for point j from i+1 to n:
        distance(point i, point j)

これら 2 つの手法を組み合わせることは、たとえば、粒子が十分に近い場合に粒子が互いに影響を与える n 体シミュレーションでは非常に一般的です。2d での楽しい例を次に示します: http://forum.openframeworks.cc/index.php?topic=2860.0

ビニング (およびハッシュ) の説明は次のとおりです 。

于 2012-11-03T17:59:28.817 に答える