algorithm - 使用网格划分的二维最近邻搜索

Question

我在一个集合中有一组相当大的二维点 (~20000)，对于 x-y 平面中的每个点，我想确定集合中的哪个点最近。 (其实点是不同类型的，我只是想知道哪种类型最接近。x-y平面是位图，比如640x480。)

来自 this answer对于“All k nearest neighbors in 2D, C++”这个问题，我有了制作网格的想法。我创建了 n*m 个 C++ 向量并将点放入向量中，具体取决于它属于哪个 bin。这个想法是你只需要检查 bin 中点的距离，而不是所有点。如果 bin 中没有点，则继续以螺旋方式处理相邻的 bin。

不幸的是，我后来才看到 Oli Charlesworth 的评论:

Not just adjacent, unfortunately (consider that points in the cell two to the east may be closer than points in the cell directly north-east, for instance; this problem gets much worse in higher dimensions). Also, what if the neighbouring cells happen to have less than 10 points in them? In practice, you will need to "spiral out".

幸运的是，我已经弄清楚了螺旋式代码(一个不错的 C++ version here ，同一个问题还有其他版本)。但我仍然遇到了问题:

• 如果我在一个单元格中找到命中点，则可能在相邻单元格中找到更近的命中点(黄色是我的探针，红色是错误的选择，绿色是实际最近的点):

  

• 如果我在相邻的单元格中找到匹配项，那么 2 步之外的单元格中也可能有匹配项，正如 Oli Charlesworth 所说:

  

• 但更糟糕的是，如果我在两步外的单元格中找到一个命中，那么在三步外的一个单元格中仍然可能有更近的命中!这意味着我必须考虑所有具有 dx、dy= -3...3 或 49 个单元格的单元格!

  

现在，在实践中，这种情况不会经常发生，因为我可以选择我的 bin 大小，以便单元格足够填充。尽管如此，我还是希望得到一个正确的结果，而不是遍历所有点。

那么我如何确定何时停止“螺旋”或搜索？我听说有一种方法可以使用多个重叠网格，但我不太明白。是否有可能挽救这种网格技术？

Answer 1

由于您的位图尺寸不大，并且您想计算每个 (x,y) 的最近点，您可以使用动态规划。

令 V[i][j] 为从 (i,j) 到集合中最近点的距离，但考虑仅 集合中位于“矩形”[(1, 1), (i, j)] 中的点。

那么V[i][j] = 0 如果(i, j)中有一个点，或者V[i][j] = min(V[i'][j'] + dist((i, j), (i', j'))) 其中 (i', j') 是(i,j) 的三个邻居之一:

即

• (i - 1, j)
• (i, j - 1)
• (i - 1, j - 1)

这为您提供了最小距离，但仅限于“左上”矩形。我们对“右上”、“左下”和“右下”方向执行相同的操作，然后取最小值。

复杂度为O(size of the plane)，最优。