最近点查询

在二维笛卡儿平面上存在一个点集P,我们可能需要进行这样的查询“在P中离x点最近的点是哪个?”。x可能并不属于P。这些查询也可以扩展到n维的空间。初级的实现方式是探测所有P中的点,是一种线性的算法。由于我们一开始就能知道P,所以应该能够对P的信息构建合理的数据结构,在查询时抛弃一些不必要的点,加快查询的速度。

也许我们可以将平面分成k2个格子,每个格子的大小是固定的,m×m,如图9-18a。在P中有10个点被放入了9个相邻的格子中。当寻找x的最邻近点时,在它周围的格子中寻找。如果格子是非空的,那么我们只需要在这些格子中寻找和某些圆相交的点,这些圆的半径是:

阅读 ‧ 电子书库

在这个例子中,目标的格子中没有任何点,所以我们需要检查邻近的三个格子。这个方法可能会带来潜在的性能下降,因为a大多数格子可能为空。b算法仍然需要查找大多数邻近格子。简而言之,将P划分到多个格子中并不是一个很高明的方法。

广告:个人专属 VPN,独立 IP,无限流量,多机房切换,还可以屏蔽广告和恶意软件,每月最低仅 5 美元

另外一种解决方案便是构建Voronoi图(Preparata和Shamos,1985),将平面划分成n个区域Ri(0≤i<n),Ri的定义为“离pi最近的点集”。因此这个区域是能够根据情况扩展到所需的大小[1]。在一个二维平面中,这样的区域是一个多边形(在更高的维度,每个区域是一个n维的多面体)。图9-18b是使用图9-18a的点得到的Voronoi图。一旦这个结构构建起来,那么只需找到邻近的区域Ri就能找到最邻近点。平均情况下,构建Voronoi图需要O(n log n)的时间,但是实现起来却非常复杂。使用Voronoi图,寻找最邻近点只需要O(log n)。

阅读 ‧ 电子书库
图 9-18 划分格子和Voronoi图的两种方法

在图9-19(a)中,我们使用kd树来表示图9-18的19个点。kd树顾名思义,是沿着坐标系统的垂直坐标轴,切分一个k维的平面。在接下来的讨论中,我们假设这棵树是基于二维平面的,但是我们也要注意,kd树可以扩展到任意高维。一棵kd树是一个递归的二叉树结构,其节点包含多个点以及一个坐标标记(x或者y),这个标记表示切分线。根节点表示矩形范围是[xlow=-∞,ylow=-∞,xhigh=+∞,yhigh=+∞]。通过点p1画一条垂直切分线V。左子树表示是V左边的区域,右子树表示右边的区域。通过点p2画一条水平切分线H,根节点的左子节点会根据这条分割线将V的左部切分成上下两个部分。根节点的左子节点表示的区域是[-∞,-∞,P1.x,+∞],右子节点表示[p1.x,-∞,+∞,+∞]。这些区域都高效地嵌套在一起。我们看到一个祖先节点的区域完全包含其所有后代的区域。

当kd树被正确地构建起来之后,在第i层的节点表示的矩形区域是第i+1层节点表示的矩形区域的两倍。这个性质使得最邻近点算法(图9-20)能够以O(log n)的性能高效地查找目标点,因为它能够抛弃整棵不可能包含最近点的子树。在接下来的“范围查询”一节中,我们将会看到这个实现是如何高效地进行范围查询的。

阅读 ‧ 电子书库
图 9-19 使用kd树切分二维平面
阅读 ‧ 电子书库
图 9-20 最近点查询详解

输入/输出

输入

一个二维的点集P。一些最近点的查询(实现并不知道)。

输出

计算出一棵kd树。对于每个查询,计算在P中离x点最近的点。

假设

可能会有两个点非常近,在计算时会因为浮点的误差导致算法选择了错误的点,但是,由于这两个点如此接近,所以不会对结果产生致命的影响。

[1]在Voronoi图中,凸包上的区域是“开口”的,直到遇到图的边界,而内部节点的区域面积有限。