18.6. 其他空间数据结构（Other Spatial Data Structures）¶

kd 树 与 PR 四叉树 之间的区别说明了创建 空间数据结构 时会遇到的许多设计选择。 kd 树对区域提供 对象空间分解，而 PR 四叉树提供 键空间分解 （因此它是一种 字典树）。 kd 树在所有结点存储记录，而 PR 四叉树只在叶结点存储记录。最后，这两种树具有不同的结构。 kd 树是二叉树（不一定是满的），而 PR 四叉树是具有 \(2^d\) 个分支的 满树 （在二维情形下，\(2^2 = 4\)）。考虑将此概念扩展到三维。三维的 kd 树将沿 \(x\)、\(y\) 和 \(z\) 三个维度交替判别器。 PR 四叉树在三维中的等价形式将是具有 \(2^3\) 即八个分支的树。这样的树被称为 八叉树。

考虑 PR 四叉树与二叉空间分割树的区别。两者都使用对象空间分解，因此都是字典树。但它们的不同之处在于 PR 四叉树一次在所有维度上分裂，而二叉空间分割树在其各维度之间轮转，一次分裂一个维度。

另一种选择是，我们可以使用以数据点为中心的空间四路分解。由这种分解产生的树称为 点四叉树。这可以看作 PR 四叉树在对象空间分解下的对等形式。或者也可以看作 kd 树的一种一次分裂所有维度的变体。图 18.6.1 所示是一个点四叉树的例子。

我们对用于存储点的空间数据结构的讨论仅仅触及了空间数据结构这一领域的表面。人们已经发明了数十种不同的空间数据结构，其中许多还有变体和不同的实现。除了点之外，还存在用于存储多种空间数据形式的空间数据结构。最重要的区别在于树结构（是否为二叉树、是否为规则分解）以及用于决定某一区域内所含数据是否过于复杂、需要细分该区域的分解规则。

一种这样的空间数据结构是 区域四叉树，用于存储像素值往往成块状的图像，例如世界各国的地图。区域四叉树使用与 PR 四叉树类似的四路规则分解方案。分解规则很简单：分割任何包含多种颜色或值的像素的结点。

空间数据结构也可以用来存储线对象、矩形对象或任意形状的对象（例如二维中的多边形或三维中的多面体）。一种简单而有效的、用于存储矩形或任意多边形形状的数据结构可以从 PR 四叉树导出。选取一个阈值 \(c\)，如果某区域包含超过 \(c\) 个对象，就把该区域细分为四个象限。当超过 \(c\) 个对象相交时，必须处理一个特殊情况。

空间数据结构方面一些最有趣的进展与将它们改造为基于磁盘的应用有关。然而，所有此类基于磁盘的实现归根结底都是将空间数据结构存储在某一种 B 树 或 哈希 的变体中。