我有一个相当大的2D点集（~20000），对于平面上的每个点，我想确定该集合中最接近的点是哪个（实际上，这些点是不同类型的，我只想知道哪种类型最接近。并且xy平面是位图，比如640x480）。
来自此答案的问题“All k nearest neighbors in 2D, C++”中我们可以得到创建一个网格的想法。我创建了n*m的C++向量，并将点放入向量中，具体取决于其所属的bin。这样做的想法是您只需要检查bin中的点的距离，而不是所有点的距离。如果bin中没有点，则继续以螺旋方式处理相邻的bin。
不幸的是，我在阅读Oli Charlesworth的评论之后才发现：
来自此答案的问题“All k nearest neighbors in 2D, C++”中我们可以得到创建一个网格的想法。我创建了n*m的C++向量，并将点放入向量中，具体取决于其所属的bin。这样做的想法是您只需要检查bin中的点的距离，而不是所有点的距离。如果bin中没有点，则继续以螺旋方式处理相邻的bin。
不幸的是，我在阅读Oli Charlesworth的评论之后才发现：
幸运的是，我已经想出了螺旋代码（这里有一个不错的C++版本，并且在同一问题中有其他版本）。但是我仍然面临一个问题：遗憾的是，不仅仅是相邻的（请考虑东部两个单元格中的点可能比东北方向直接的点更靠近，例如; 在更高维度下，这个问题会变得更加严重）。另外，如果相邻的单元格恰好少于10个点，则怎么办？ 在实践中，您需要“螺旋形向外扩展”。
如果在一个单元格中找到匹配项，则相邻单元格可能会有更接近的匹配项（黄色是我的探针，红色是错误选择，绿色是实际最接近的点）：
如果在相邻单元格中找到匹配项，则可能会在两步之外的单元格中找到匹配项，如Oli Charlesworth所指出的：
但更糟糕的是，如果我在两个步骤之外的单元格中发现匹配项，就可能仍然会有更接近的匹配项！ 这意味着我必须考虑所有dx，dy = -3 ... 3或49个单元格！
那么我如何知道何时停止"螺旋式"搜索呢？我听说有一种方法是使用多个重叠的网格，但我并没有完全理解。这个网格技术还能挽救吗？