直线多边形矩形连接算法的扩展

### 直线多边形矩形连接算法的扩展 在空间数据处理中，直线多边形的连接操作是一个重要的问题。传统的方法往往存在一些局限性，本文将探讨如何扩展矩形连接算法以高效处理直线多边形的连接问题。 #### 1. 空间连接与过滤步骤 在两步连接评估中，过滤步骤对近似对象进行连接操作，排除那些不会对连接结果产生贡献的对象。为了提高空间连接的性能，提升过滤步骤的效率并减少其生成结果的规模至关重要。 大多数连接算法在过滤步骤中使用最小边界矩形（MBR）。MBR 可以通过 R - 树和四叉树等索引结构进行索引，从而能被高效处理，加速空间连接评估的过滤步骤。然而，MBR 是对空间对象的粗略近似，很可能出现两个对象本身不相交，但它们的 MBR 相交的情况（即误判）。误判会导致访问那些并非连接结果一部分的空间对象，减慢连接评估的细化步骤。因此，减少误判的数量可以提升空间连接评估的性能，开发适合空间连接的近似方法变得很有意义。 近似的质量定义为实际空间对象的面积与近似对象面积的比值。质量为 1 的近似与实际对象完全相同，近似质量越接近 1，近似就越精细。“保守”近似（即包含对象的近似）的质量 ≤1。在这种情况下，质量较低的近似会增加误判的数量，而质量较高的近似可以减少误判。 研究中考虑了六种保守近似方法：MBR、旋转 MBR、最小边界圆、最小边界椭圆、凸包和最小边界 n 角形，并基于空间连接中多个数据集的误判情况进行了比较。此外，还使用了多边形的栅格近似进行空间连接评估。这些研究中的连接策略通常是先对空间对象的 MBR 进行连接评估，然后根据 MBR 连接结果确定更精细近似的交集，并对可能相交的对象对进行细化步骤。研究表明，旋转 MBR、最小边界 5 角形和栅格近似可以提高空间连接评估的整体性能。 本文考虑了一种“直线”近似方案，它结合了 MBR 的简单性和栅格近似的高质量。直线（或正交）多边形是边界与坐标轴平行的多边形。如果一个直线多边形有 ℓ 个边界点（ℓ 必须为偶数），则称其为 ℓ 角直线多边形。对于一个二维简单多边形 S，定义其 ℓ 角直线近似为包含 S 的所有 ℓ 角直线多边形中质量最高的那个。 #### 2. 分解式连接算法 为了评估直线多边形的连接，可以采用将直线多边形分解为矩形，然后对生成的矩形应用矩形连接算法的方法。具体步骤如下： - **分解步骤**：将两个集合 r 和 s 中的每个直线多边形分解为一个或多个（可能重叠）的矩形，得到两个矩形集合 rect(r) 和 rect(s)。使用特定算法，可以将一个 ℓ 角直线多边形最多划分为 (ℓ/2 - 1) 个（非重叠）矩形，并且这个界限是严格的。由于 r 和 s 各包含 n 个多边形，因此分解阶段在 rect(r) 和 rect(s) 中各自产生的矩形数量不超过 n×(ℓ/2 - 1) 个。 - **矩形连接步骤**：对 rect(r) 和 rect(s) 应用矩形连接算法。现有的矩形连接算法有很多，不同算法的最坏情况 IO 复杂度和输入要求各不相同，如下表所示： | 算法类别 | 最坏情况 IO 复杂度 | 是否使用空间索引结构 | 输入要求 | | --- | --- | --- | --- | | z - 排序 [16,17,18] | O(N²) | 否 | 从 MBR 计算的 z - 排序 | | 网格文件 [3] | O(N²) | 否 | 对应 MBR 的 4 - D 点的网格文件 | | 分区 [19,15] | O(N²) | 否 | MBR 的分区 | | 分布式扫描 [2] | O(N logₘ(N/b) + k/b) | 否 | MBR 在 x 和 y 投影上排序 | | 连接索引 [20] | O(N²) | 是 | 连接结果的网格文件 | | R∗ - 树 [7,11] | O(N²) | 是 | 无 | | 外部线段树 [1] | O(N logₘ(N/b) + k/b) | 是 | MBR 在 y 投影上排序 | | 过滤树 [22] | O(N²) | 是 | 无 | | 区间 B⁺ - 树 [25] | O(bN logb(N/b) + k) | 是 | MBR 在 y 投影上排序 | 为了高效评估直线多边形的连接，应选择 IO 复杂度较好的矩形连接算法。分布式扫描 [2]、外部线段树 [1] 和区间 B⁺ - 树（IB⁺ - 树）[25] 等算法具有较好的 IO 复杂度，是该步骤的候选算法。以 [25] 中的 rjoin 算法为例进行分析，假设 r 和 s 是两个包含 n 个 ℓ 角直线多边形的集合，其大小均为 N = n×ℓ。分解后得到的矩形集合各包含 O(N) 个矩形。rjoin 算法使用区间 B⁺ - 树作为索引结构，并应用平面扫描技术。矩形连接步骤所需的 IO 操作是 O(bN logb(N/b) + k′)，其中 k′ 是相交矩形对的数量。在最坏情况下，两个 ℓ 角直线多边形的矩形分解之间有 O(ℓ²)