使用网格划分的2D中的最近邻居搜索

Question

我在一组中具有相当大的一组2D点（~20000），并且对于x-y平面中的每个点想要确定来自该组的哪一点最接近。 （实际上，这些点是不同类型的，我只想知道哪种类型最接近，而xy平面是位图，比如说640x480）。

从this answer到问题“All k nearest neighbors in 2D, C++”我的想法是做一个网格。我创建了n * m个C++向量，并将这些点放入向量中，具体取决于它落入哪个bin。这个想法是，你只需要检查仓内点的距离，而不是所有的点。如果垃圾箱中没有点，则以螺旋方式继续相邻垃圾箱。

不幸的是，我只看过奥利查尔斯沃思的评论算账：

不只是相邻的，不幸的是（考虑到在细胞点的两个 向东可能比点更接近直接在单元格东北部，例如： ;这个问题在更高维度上变得更糟）。 另外，如果相邻单元碰巧有少于10个点的话呢？在实践中，你需要“螺旋形”。

幸运的是，我已经有不断上升的代码想通了（一个不错的C++ version here，并有在同一个问题的其他版本）。但我还是留下的问题：

• 如果我发现小区内的打击，有可能是在相邻的小区更近的命中（黄色是我的探头，红色的是错误的选择，绿色实际的最近点）：

  

• 如果我发现相邻小区一击，有可能是在细胞内命中2步之遥，为奥利查尔斯沃思说：

  

• 但更糟糕的是，如果我在两步之外的单元格中发现命中，那么三步之外的命中仍然可能更接近命中！这意味着我不得不考虑所有的细胞与DX，DY = -3 ... 3，或49细胞！

  

现在，在实践中，这不会经常发生，因为我可以选择我的窗口尺寸使细胞充满足够。不过，我想得到一个正确的结果，而不是遍历所有点。

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

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（飞机的大小），这是最佳的。

Answer 2

一个解决方案是构建具有不同网格大小的多个分区。

假设你创建的水平1,2,4,8分区，..

现在，搜索网格尺寸1点（你是在9个方格基本搜索）。如果搜索区域中有一个点，并且到该点的距离小于1，则停止。否则，转到下一个网格大小。

您需要构建的网格数量大约是创建一个分区级别的两倍。

Answer 3

对于您的任务通常使用Point Quadtree，特别是当点不均匀分布时。

要保存主内存，您可以使用使用存储桶的PM或PMR-Quadtree。

您可以在您的细胞中进行搜索，并在最坏的情况下搜索细胞周围的所有四元组细胞。您可以使用k-d tree。

Answer 4

一个解决方案我尝试

• 首先做一个网格，这样你的平均说每盒1（如果你想要更大的扫描更多）点。
• 选择中心框。以循环方式继续选择邻居框，直到找到至少一个邻居。此时你可以选择1或9左右的盒子
• 选择一层相邻的盒子
• 现在你有一个相当小的点列表，通常不超过10个，你可以冲入距离公式找到最近的邻居。

由于每个盒子平均有1个点，所以您将主要选择9个盒子并比较9个距离。可根据数据集属性调整网格大小以获得更好的结果。另外，如果你的数据有很多方差，你可以尝试2级网格（或者更多），所以如果选择工作并在单个查询中返回超过50个点，则开始下一个网格搜索大小的1/10 ...