计算多维空间——主要是二维空间——中最近点问题是GIS、游戏、计算机图形学中常遇到的问题。最近点问题包含但不局限于下面问题：

1. 一维空间中距离点A 最近的一个点
2. 一维空间中距离点A 最近的K 个点
3. 一维空间中距离点A 小于D 的所有点
4. 二维空间中距离点A 最近的一个点
5. 二维空间中距离点A 最近的K 个点
6. 二维空间中距离点A 小于D 的所有点

下面以问题 5. 二维空间中距离点A 最近的K 个点 为例，谈谈我的思路：

 首先将二维距离变为一维距离，得到距离该点（红点）在一个坐标系上最近的1→i 个点，所对应的点的集合为Sx。下图是当i=3 时，距离最近的点：

同理，得到y轴上最近的1→i 个点，点的集合为Sy。

i 的大小从1 逐渐递增，每次计算集合Sx和集合Sy 的交集（Sx∩Sy），如果交集中的点w 是x、y坐标距离红点之和（△x+△y）第k 小的那个点，且满足约束条件：

△x+△y < max(Sx∪Sy)

那么停止i 的递增，在Sx和集合Sy 的交集（Sx∩Sy）中距离红点之和（△x+△y）中最小的k 个点即是平面上距离红点之和（△x+△y）最小的k 个点。当然约束条件可以进一步优化为：

△x+△y ≤ max(min(Sx)+max(Sy),min(Sy)+max(Sx))

因为二维平面距离之和（△x+△y）与距离（）满足：

△x+△y ≥  

 那么距离红点最近的k 个点距离上限小于△x+△y。

最终，只需要在一个较小的集合Sx∪Sy 中遍历找到距离红点最近的k 个点就可以咯~~~