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

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

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

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

绘图1

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

绘图2

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

绘图3

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 个点就可以咯~~~