算法优化 : loop to find pair of items in 3D space

Question

这里我对代码没有问题，但我正在寻找想法和好的关键字来解释和解决我的问题。一切都与算法优化有关。

我有两组项目，它们是 3D 空间中的点，它们都有 x、y、z 坐标。如果 A 中的项目与 B 中的项目彼此之间的距离小于 dmax 变量，我想将它们配对。

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

例如，我在 A 组中有 100 个项目，在 B 组中有 50 个项目。 如果 Ai 和 Bj 的距离小于 dmax，我想将 A 中的项目与 B 中的项目配对。

我已经做过但目前可能不是很有效的事情。这是，计算 A 中所有项目和 B 中所有项目之间的距离，但是它很慢，我想知道是否有办法快速获得相同的结果(因为我在两组中都有数百万个项目).

我的第一个想法是将 A 和 B 集合在不同部分的 3D 空间拆分，并将所有点分配到一个体素中，从而计算这个体素中 A 和 B 的项目之间的距离，这限制了距离的数量我得计算一下。限制是如果我不想错过任何一对，体素必须叠加。这会产生重复项，但我可以处理它。

我已经放弃了 sqrt 函数以加快计算速度，我现在正在比较 d² 和 dmax² 以检查它是否符合条件。

您是否有其他想法或关键字(因为我确信有更好的方法来解释我的问题)可以帮助我找到解决此问题的方法？

谢谢

Answer 1

您的问题称为“固定半径近邻搜索”。它通常用 kD 树或八叉树来寻址。

也可以使用体素网格，但如果有太多体素是空的，则效率会很低。在查找给定点的邻居时，您必须访问与以该点为中心的球体具有非空交点的所有体素。