计算二维空间某点的最近k 个点

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

下面以问题 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）与距离（ $\sqrt{\bigtriangleup x^2+\bigtriangleup y^2}$ ）满足：

△x+△y ≥ $\sqrt{\bigtriangleup x^2+\bigtriangleup y^2}$

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

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

呆鸥