我有一组相当大的 2D 点（~20000），对于 xy 平面中的每个点，我想确定集合中的哪个点最接近。（其实点的类型不同，我只想知道哪种类型最接近。而xy平面是位图，比如640x480。）
从这个问题的答案“所有 k 最近的邻居在 2D，C++ ”我得到了制作网格的想法。我创建了 n*m C++ 向量并将点放入向量中，具体取决于它属于哪个 bin。这个想法是你只需要检查 bin 中点的距离，而不是所有点。如果 bin 中没有点，则继续以螺旋方式处理相邻的 bin。
不幸的是，我后来只看了 Oli Charlesworth 的评论：
不幸的是，不仅仅是相邻的（例如，考虑到单元格 2 中向东的点可能比单元格中正向东北的点更接近；这个问题在更高维度上会变得更糟）。另外，如果相邻的单元格中恰好有不到 10 个点怎么办？在实践中，您将需要“盘旋”。
幸运的是，我已经弄清楚了螺旋式代码（这里有一个不错的 C++ 版本，在同一个问题中还有其他版本）。但我仍然存在问题：
如果我在一个单元格中找到一个命中，则相邻单元格中可能有一个更接近的命中（黄色是我的探针，红色是错误的选择，绿色是实际最近的点）：
如果我在相邻的单元格中发现命中，则可能会在 2 步外的单元格中命中，正如 Oli Charlesworth 所说：
但更糟糕的是，如果我在两步外的牢房中发现命中，三步外的命中仍然可能会更近地命中！这意味着我必须考虑所有 dx,dy= -3...3 或 49 个单元格的单元格！
现在，实际上这不会经常发生，因为我可以选择我的 bin 大小，这样单元格就足够填充了。不过，我希望得到一个正确的结果，而不是遍历所有点。
那么我如何找出何时停止“螺旋”或搜索？我听说有一种方法有多个重叠网格，但我不太明白。是否有可能挽救这种网格技术？