计算几何中的梯形分解（Trapezoidal Decomposition in Computational Geometry）
字数 2513 2025-12-24 16:10:26

计算几何中的梯形分解（Trapezoidal Decomposition in Computational Geometry）

计算几何中的梯形分解，也称为梯形化（trapezoidation），是一种将平面细分（subdivision）转化为一组互不相交的梯形的算法技术。它是许多更高级几何算法和数据结构的基础预处理步骤。我将从最基础的几何概念开始，逐步深入到梯形分解的算法和性质。

第一步：理解“梯形”在分解中的定义
在标准的欧几里得几何中，梯形是至少有一对平行边的四边形。然而，在计算几何的梯形分解上下文中，“梯形”的定义被广义化了。这里，一个“梯形”指的是被两条垂直线（通常是垂直于x轴）和两条线段（不一定平行）所界定的一个区域。更精确地说，它是一个四边形或三角形（可视为退化的四边形），其顶部和底部是给定线段（或线段的一部分），左右两侧是垂直的直线。如果顶部或底部边界是某个线段的端点，那么梯形可能退化为三角形。这种广义定义使得我们可以用梯形覆盖任何平面细分。

第二步：从输入到输出——明确问题
梯形分解的典型输入是一个由不相交线段（除了可能在端点处相交）组成的集合 S。更常见的应用场景是输入一个简单多边形 P（由 n 条线段首尾相连围成，内部无孔洞）。输出是平面的一个划分，将感兴趣的区域（如线段集合的包围盒内部，或多边形内部）分解为一组互不相交的梯形。每个梯形的上下边界是输入线段的子段或多边形边界的一部分，左右边界是垂直的直线，从梯形的顶部边界垂直延伸到其底部边界。

第三步：为何要梯形分解？——动机与应用
梯形分解本身结构规整，易于处理。它的主要价值在于：

  1. 点定位：给定一个查询点，要确定它在哪个梯形中，从而可以快速判断它与输入几何（如多边形）的关系（内部/外部）。在梯形分解上，可以使用随机增量构造和搜索结构（如历史DAG）实现 O(log n) 期望时间的点定位。
  2. 三角剖分的基础：简单多边形的梯形分解可以很容易地转化为三角剖分。具体方法是，在分解出的每个梯形内部，连接其上下边界的对角线（如果上下边界顶点数超过2，可能需要进一步处理），最终可以在 O(n) 时间内得到三角剖分。
  3. 其他算法的预处理：如可见性计算、运动规划等，规整的单元划分能简化问题。

第四步：算法的核心思想——平面扫描与数据结构
梯形分解的标准确定性算法通常采用平面扫描。其基本步骤如下：

  1. 预处理：确定所有线段端点的 x 坐标。实际上，扫描线是垂直的，从左向右（沿 x 轴方向）移动。
  2. 扫描线状态：扫描线状态维护一个与当前扫描线相交的所有线段的有序表（通常按它们在扫描线处的 y 坐标排序）。这个排序是动态的，随着扫描线移动，线段之间会交换顺序（当它们在某个事件点相交时）。
  3. 事件点处理：事件点是线段的端点和线段之间的交点。从左到右处理这些事件点：
    • 在左端点，将新线段插入扫描线状态的有序表中。这定义了一个新梯形的开始。需要找到新线段上方和下方的相邻线段，从而确定新梯形的左右边界。
    • 在右端点，从扫描线状态中移除该线段。这标志着一个梯形的结束，并可能合并相邻的梯形。
    • 在交点，两条相交线段在扫描线状态的有序表中交换顺序。这个交换操作会终止两个旧的梯形并开始两个新的梯形。这是算法最复杂的部分，需要正确更新梯形间的邻接关系。
  4. 梯形构建：在相邻事件点之间，扫描线状态保持不变。这个“条带”被相邻线段划分成一个个梯形单元。算法需要仔细地记录每个梯形的上下边界、左右邻居，以构建完整的分解。

第五步：随机增量构造——一种更高效的实用算法
尽管平面扫描算法是确定性的，但其时间复杂度（O((n+k) log n)，k 是交点数量）在处理大量交点时可能较高。一种更著名且在实际中常用的是随机增量构造算法（如Seidel的算法）。

  1. 随机化：随机打乱输入线段的顺序。
  2. 增量添加：依次将每条线段插入当前的梯形分解中。插入一条线段 s 时：
    • 利用已有的点定位数据结构（在构造过程中同时维护），找到包含 s 左端点的梯形。
    • 从这个梯形开始，向右“追踪”（follow）线段 s 穿过当前梯形分解的路径。s 会依次穿过一系列梯形。
    • 对于 s 穿过的每个梯形，s 将其“切割”成更小的梯形（或三角形）。这可能需要拆分梯形，并更新邻接关系。
  3. 更新搜索结构：在切割梯形的过程中，同步更新一个历史有向无环图（DAG），它记录了梯形被拆分的历史。这个DAG将作为未来的点定位搜索结构。
  4. 复杂度：这个算法的总期望时间复杂度是 O(n log n + k)，其中 k 是输出梯形的数量（通常为 O(n+k)），空间复杂度为 O(n + k)。其优点是简单、实现相对容易，且能同时得到分解和高效的点定位结构。

第六步：关键性质与注意事项

  1. 唯一性：梯形分解通常不是唯一的。它依赖于线段处理的顺序（在增量算法中）或扫描线处理事件的方式。不同的分解在几何上是等价的（覆盖相同的区域），但梯形划分可能不同。
  2. 退化情况：垂直线段、共线点、多条线段交于一点等特殊情况需要仔细处理，通常通过符号扰动或特殊约定来处理。
  3. 复杂度：梯形分解的输出大小（梯形数量）是 O(n + k)，其中 n 是线段数，k 是线段间的交点数。在最坏情况下（如有许多交点），k 可以是 O(n²)，但许多应用中输入的线段是简单多边形的边（不相交，除了在端点处），此时 k=0，输出大小为 O(n)。
  4. 与三角剖分的关系：如前所述，简单多边形的梯形分解是构造三角剖分的第一步。由于梯形分解可以在 O(n log n) 时间内完成，因此它也提供了一个简单的 O(n log n) 时间的三角剖分算法（虽然存在 O(n) 时间的线性算法，但更复杂）。

总结：梯形分解是一种强大的几何工具，它将不规则的平面划分转化为一组规则、易于遍历的梯形单元。其核心价值在于它能高效地支持点定位，并作为通往三角剖分的桥梁。算法上，既可以通过确定性的平面扫描实现，也可以通过更实用的随机增量算法实现，后者在构造分解的同时，自然地生成了一个用于快速查询的点定位数据结构。

计算几何中的梯形分解（Trapezoidal Decomposition in Computational Geometry） 计算几何中的梯形分解，也称为梯形化（trapezoidation），是一种将平面细分（subdivision）转化为一组互不相交的梯形的算法技术。它是许多更高级几何算法和数据结构的基础预处理步骤。我将从最基础的几何概念开始，逐步深入到梯形分解的算法和性质。 第一步：理解“梯形”在分解中的定义 在标准的欧几里得几何中，梯形是至少有一对平行边的四边形。然而，在计算几何的梯形分解上下文中，“梯形”的定义被广义化了。这里，一个“梯形”指的是被两条垂直线（通常是垂直于x轴）和两条线段（不一定平行）所界定的一个区域。更精确地说，它是一个四边形或三角形（可视为退化的四边形），其顶部和底部是给定线段（或线段的一部分），左右两侧是垂直的直线。如果顶部或底部边界是某个线段的端点，那么梯形可能退化为三角形。这种广义定义使得我们可以用梯形覆盖任何平面细分。 第二步：从输入到输出——明确问题 梯形分解的典型输入是一个由不相交线段（除了可能在端点处相交）组成的集合 S。更常见的应用场景是输入一个简单多边形 P（由 n 条线段首尾相连围成，内部无孔洞）。输出是平面的一个划分，将感兴趣的区域（如线段集合的包围盒内部，或多边形内部）分解为一组互不相交的梯形。每个梯形的上下边界是输入线段的子段或多边形边界的一部分，左右边界是垂直的直线，从梯形的顶部边界垂直延伸到其底部边界。 第三步：为何要梯形分解？——动机与应用 梯形分解本身结构规整，易于处理。它的主要价值在于： 点定位 ：给定一个查询点，要确定它在哪个梯形中，从而可以快速判断它与输入几何（如多边形）的关系（内部/外部）。在梯形分解上，可以使用随机增量构造和搜索结构（如历史DAG）实现 O(log n) 期望时间的点定位。 三角剖分的基础 ：简单多边形的梯形分解可以很容易地转化为三角剖分。具体方法是，在分解出的每个梯形内部，连接其上下边界的对角线（如果上下边界顶点数超过2，可能需要进一步处理），最终可以在 O(n) 时间内得到三角剖分。 其他算法的预处理 ：如可见性计算、运动规划等，规整的单元划分能简化问题。 第四步：算法的核心思想——平面扫描与数据结构 梯形分解的标准确定性算法通常采用 平面扫描 。其基本步骤如下： 预处理 ：确定所有线段端点的 x 坐标。实际上，扫描线是垂直的，从左向右（沿 x 轴方向）移动。 扫描线状态 ：扫描线状态维护一个与当前扫描线相交的所有线段的 有序表 （通常按它们在扫描线处的 y 坐标排序）。这个排序是动态的，随着扫描线移动，线段之间会交换顺序（当它们在某个事件点相交时）。 事件点处理 ：事件点是线段的端点和线段之间的交点。从左到右处理这些事件点： 在 左端点 ，将新线段插入扫描线状态的有序表中。这定义了一个新梯形的开始。需要找到新线段上方和下方的相邻线段，从而确定新梯形的左右边界。 在 右端点 ，从扫描线状态中移除该线段。这标志着一个梯形的结束，并可能合并相邻的梯形。 在 交点 ，两条相交线段在扫描线状态的有序表中交换顺序。这个交换操作会终止两个旧的梯形并开始两个新的梯形。这是算法最复杂的部分，需要正确更新梯形间的邻接关系。 梯形构建 ：在相邻事件点之间，扫描线状态保持不变。这个“条带”被相邻线段划分成一个个梯形单元。算法需要仔细地记录每个梯形的上下边界、左右邻居，以构建完整的分解。 第五步：随机增量构造——一种更高效的实用算法 尽管平面扫描算法是确定性的，但其时间复杂度（O((n+k) log n)，k 是交点数量）在处理大量交点时可能较高。一种更著名且在实际中常用的是 随机增量构造算法 （如Seidel的算法）。 随机化 ：随机打乱输入线段的顺序。 增量添加 ：依次将每条线段插入当前的梯形分解中。插入一条线段 s 时： 利用已有的点定位数据结构（在构造过程中同时维护），找到包含 s 左端点的梯形。 从这个梯形开始，向右“追踪”（follow）线段 s 穿过当前梯形分解的路径。s 会依次穿过一系列梯形。 对于 s 穿过的每个梯形，s 将其“切割”成更小的梯形（或三角形）。这可能需要拆分梯形，并更新邻接关系。 更新搜索结构 ：在切割梯形的过程中，同步更新一个历史有向无环图（DAG），它记录了梯形被拆分的历史。这个DAG将作为未来的点定位搜索结构。 复杂度 ：这个算法的总期望时间复杂度是 O(n log n + k)，其中 k 是输出梯形的数量（通常为 O(n+k)），空间复杂度为 O(n + k)。其优点是简单、实现相对容易，且能同时得到分解和高效的点定位结构。 第六步：关键性质与注意事项 唯一性 ：梯形分解通常不是唯一的。它依赖于线段处理的顺序（在增量算法中）或扫描线处理事件的方式。不同的分解在几何上是等价的（覆盖相同的区域），但梯形划分可能不同。 退化情况 ：垂直线段、共线点、多条线段交于一点等特殊情况需要仔细处理，通常通过符号扰动或特殊约定来处理。 复杂度 ：梯形分解的输出大小（梯形数量）是 O(n + k)，其中 n 是线段数，k 是线段间的交点数。在最坏情况下（如有许多交点），k 可以是 O(n²)，但许多应用中输入的线段是简单多边形的边（不相交，除了在端点处），此时 k=0，输出大小为 O(n)。 与三角剖分的关系 ：如前所述，简单多边形的梯形分解是构造三角剖分的第一步。由于梯形分解可以在 O(n log n) 时间内完成，因此它也提供了一个简单的 O(n log n) 时间的三角剖分算法（虽然存在 O(n) 时间的线性算法，但更复杂）。 总结 ：梯形分解是一种强大的几何工具，它将不规则的平面划分转化为一组规则、易于遍历的梯形单元。其核心价值在于它能高效地支持点定位，并作为通往三角剖分的桥梁。算法上，既可以通过确定性的平面扫描实现，也可以通过更实用的随机增量算法实现，后者在构造分解的同时，自然地生成了一个用于快速查询的点定位数据结构。