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

Question

我有一个大小为 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

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

Answer 1

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

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

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

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