如果k相对较小（<20左右）并且您具有大致均匀的分布，请创建一个覆盖点下降范围的网格，并选择该网格，以使每个网格的平均点数舒适地高于k（因此a居中位置的点通常会在该一个网格点获得其k个邻居）。然后创建一组其他栅格，它们沿每个轴与第一个栅格（重叠）成半角。现在，对于每个点，计算它属于哪个网格元素（因为网格是规则的，因此不需要搜索），并选择四个点中最接近其中心的一个（或者您拥有许多重叠的网格）。

在每个网格元素内，这些点应在一个坐标中排序（比方说x）。从您选择的元素开始（使用对分查找），沿着排序的列表向外走，直到找到k个项目（同样，如果k小，则以二进制插入排序的方式来保持k个最佳匹配的列表的最快方法，让最差的匹配项在插入时最终消失；在现代硬件上，插入排序通常会击败其他所有项（最多约30个）。一直走，直到最远的最近邻居比x中距离您的下一个点更近（即不计算其y偏移，因此可能没有新点比迄今为止找到的第k个最近点）
。

如果您还没有k点，或者您有k点，但是网格元素的一个或多个壁比k点中的最远点更靠近您的兴趣点，请将相关的相邻网格元素添加到搜索中。

这应该使您具有类似的性能O(N*k^2)，且常数因子相对较低。如果k大，则此策略过于简单，您应该选择k中呈线性或对数线性的算法，例如kd树。