アルゴリズムの最適化：3D空間内のアイテムのペアを見つけるためのループ

Question

ここではコードに問題はありませんが、私は問題を説明して解決するためのアイデアや良いキーワードを探しています。それはアルゴリズムの最適化に関するものです。

私は3D空間内のポイントであるアイテムの2つのセットを持っています。それらはすべてx、y、z座標を持っています。お互いの距離がdmax変数よりも小さい場合、AからBまでのアイテムとアイテムをペアにしたい。例えば

for i in A do 
    for j in B do 
    d = sqrt((xAi-xBj)^2+(yAi-yBj)^2+(zAi-zAj)^2) 
    if d <= dmax then 
     ok 
    fi 
    done 
done 

、I 100、セットA内のアイテム、及びIはAiとBjの距離がDMAX未満であればBからアイテムとからアイテムをペアリングするセットB. 50を有しています。

私はすでに行っていましたが、今はあまり効果がないかもしれません。これはAのすべてのアイテムとBのすべてのアイテムの距離を計算することですが、それはかなり遅く、同じ結果をすばやく得る方法があるかどうかを知りたいのです（両方のセットに数百万のアイテムがあるので）。

最初のアイデアは、AとBのセットが異なる部分にある3D空間を分割し、ボクセル内のすべての点を割り当て、このボクセルのAとBの項目間の距離を計算することでした。私は計算しなければならない距離。限界は、どんなペアも見逃したくなければ、ボクセルはスーパーインポーズする必要があるということです。これは重複を生成することができますが、私はそれに対処することができます。

私は既に計算速度を上げるためにsqrt関数を削除しましたが、現在はd²とdmax²を比較して条件に一致するかどうかを確認しています。

この問題の解決策を見つけるのに役立つかもしれない別のアイデアやキーワードがありますか（私の問題を説明する良い方法があると確信しています）？

は

Answer 1

あなたの問題は、「傍探索に近い一定の半径」と呼ばれてありがとう。これは、一般に、kDツリーまたはオクトリーで対処される。

ボクセルグリッドを使用することもできますが、あまりにも多くのボクセルが無効な場合は非効率的になることがあります。与えられた点の近傍を探すときは、その点を中心とした球との空でない交点を持つすべてのボクセルを参照する必要があります。