3Dで1つのポイントが別のポイントの近くにあるかどうかをチェックするための効率的なアルゴリズムを探しています。
sqrt((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2) < radius
これは速すぎるようには見えませんし、実際にはそれほど大きな精度は必要ありません。他にどのように私はこれを行うことができますか？
10 に答える
24
距離を2乗し、への呼び出しをドロップしますsqrt()。これははるかに高速です。
(((x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 < radius * radius
もちろん、多くの場合、少なくともradius * radius事前に計算して、たとえばとして保存することができますsquaredRadius。
于 2010-01-22T10:23:38.657 に答える
10
球形の距離ではなく立方体の距離で満足できる場合は、かなり単純な実装は次のようになります。
Math.Abs(x2-x1) < radius && Math.Abs(y2-y1) < radius && Math.Abs(z2-z1) < radius
ボトルネックが判明した場合は、Math.Absを最適化するための独自のお気に入りの方法を使用できます。
また、ディメンションの1つが一般的に他のディメンションよりも変化が少ない場合は、最後に1つ置くと、パフォーマンスが向上するはずです。たとえば、主に「地面」のxy平面上のオブジェクトを処理している場合は、最後にz軸をチェックします。これは、xチェックとyチェックを使用して衝突を早期に除外できるはずだからです。
于 2010-01-22T10:26:47.047 に答える
3
大きな精度が必要ない場合は、2番目の点が球ではなく立方体（辺の長さ「2a」）の内側にあるかどうかを確認できます。1番目の点は中心にあります。
|x2-x1|<a && |y2-y1|<a && |z2-z1|<a
于 2010-01-22T10:29:02.590 に答える
2
パイプライン化されたプロセッサアーキテクチャのため、ほとんどの場合、FPU計算を1回の分岐として、2回実行する方が効率的です。ブランチの予測ミスの場合、（cpu-termsで）何年もの間ストールしています。
ですから、私は分岐の方法ではなく、計算の方法に行きたいと思います。
于 2010-01-22T11:05:28.657 に答える
1
何十億回も実行されていたためにこれを最適化する場合は、unwindの方法を使用してこれを解決し、SIMDを使用して並列化します。それを行うにはいくつかの異なる方法があります。1つの演算ですべての減算（x2-x1、y2-y1、z2-z1）を実行してから、1つの演算で乗算することもできます。そうすれば、アルゴリズムを再設計することなく、メソッド内で並列化できます。
または、多くの要素で（x2-x1）^ 2 +（y2-y1）^ 2 +（z2-z1）^ 2-r ^ 2を計算し、結果を配列に格納するバルクバージョンを作成することもできます。スループットを向上させることもできますが、それはアルゴリズムを再設計することを意味し、テストの用途によって異なります。
本当にたくさんのテストを続けて行っている場合は、OpenMPのようなものを使用してこれを簡単に最適化することもできます。
于 2010-01-22T13:43:32.070 に答える
1
精度が必要ない場合は、球ではなく立方体にいるかどうかを確認できます。
ここにもオプションがあり、球を囲む立方体（偽陰性なし）を選択できます。球と同じ体積の立方体（いくつかの偽陽性と陰性ですが、最大エラーは最小化されます）、内に含まれる立方体球体（誤検知なし）。
この手法は、より高い次元にも拡張できます。
すべてのポイントを別のポイントの近くに配置したい場合は、何らかの形式の空間インデックスも適切な場合があります（おそらくkdツリー）
于 2010-01-22T10:27:39.687 に答える
1
他の多くのポイントと照合する必要がある場合は、空間順序付け方法を使用して、特定の場所の近くにあるポイントをすばやく見つけることを検討できます。このリンクを見てください： wikiリンク
于 2010-01-22T11:12:00.830 に答える
0
平方根を削除した後、値が大きくなる場合は、対数を適用することをお勧めします。
于 2010-01-22T13:27:50.107 に答える
0
max（abs（x1-x2）、abs（y1-y2）、abs（z1-z2））を使用します
于 2010-01-22T10:26:22.693 に答える
0
これは立方体の距離を実行します。多くのポイントを実行している場合、ほとんどの場合、最初のテストのみが実行されます。
close = (abs(x2-x1) < r && abs(y2-y1) < r && abs(z2-z1) < r);
于 2010-01-22T15:36:35.223 に答える