在均匀网格上查找到点云中最近点的距离

我有一个大小为 AxBxC 的 3D 网格，网格中的点之间的距离 d 相等。给定多个点，考虑到以下假设，找到每个网格点到最近点的距离（每个网格点应包含到点云中最近点的距离）的最佳方法是什么？

假设 A、B 和 C 相对于 d 来说相当大，给出的网格可能为 500x500x500，并且大约有 100 万个点。

还假设如果到最近点的距离超过 D 的距离，我们不关心最近点距离，并且可以安全地将其设置为某个大数（D 可能是 d 的 2 到 10 倍）

由于将有大量的网格点和可供搜索的点，因此简单详尽：

for each grid point:
   for each point:
     if distance between points < minDistance:
       minDistance = distance between points

不是一个好的选择。

我正在考虑做一些类似的事情：

create a container of size A*B*C where each element holds a container of points
for each point:
  define indexX = round((point position x - grid min position x)/d)
  // same for y and z
  add the point to the correct index of the container

for each grid point:
  search the container of that grid point and find the closest point
  if no points in container and D > 0.5d:
    search the 26 container indices nearest to the grid point for a closest point
  .. continue with next layer until a point is found or the distance to that layer 
        is greater than D

基本上：将点放入桶中并向外进行径向搜索，直到为每个网格点找到一个点。这是解决问题的好方法，还是有更好/更快的方法？有利于并行化的解决方案是首选。

实际上，我认为我有更好的方法，因为网格点的数量远大于样本点的数量。让|网格| = N，|样本| = M，那么最近邻搜索算法将类似于 O(N lg M)，因为您需要查找所有 N 个网格点，并且每次查找（最好情况）为 O(lg M)。

相反，循环遍历样本点。为每个网格点存储迄今为止找到的最接近的样本点。对于每个样本点，只需检查样本距离D内的所有网格点，看看当前样本是否比任何先前处理的样本更近。

运行时间为 O(N + (D/d)^3 M)，当 D/d 较小时，运行时间应该更好。

即使 D/d 较大，如果您能制定出截止策略，您可能仍然没问题。例如，如果我们正在检查距样本 5 的网格点，并且该网格点已标记为距前一个样本的距离 1，则不需要检查“超出”该网格点的所有网格点因为前一个样本保证比我们正在处理的当前样本更接近。您所要做的就是（我认为这并不容易，但应该是可行的）定义“超出”的含义并弄清楚如何迭代网格以避免对“超出”此类网格点的区域进行任何工作。