计算几何中的梯形分解（Trapezoidal Decomposition in Computational Geometry）
字数 2104 2025-12-24 23:11:02

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

我们来详细讲解计算几何中的“梯形分解”。这是一个将复杂平面区域（通常是由一组线段或简单多边形边界定义的平面细分）系统地划分为更简单、易于处理的梯形结构的方法。

第一步：问题与目标
想象在平面上有一组互不相交的线段（除了可能在端点处相交），这些线段可能是简单多边形的边，也可能是任意放置的线段。我们的目标是：将这个被线段分割的平面区域，系统地划分成一组“梯形”。

  • 什么是这里的“梯形”？ 在这个上下文中，梯形被放宽了定义：它是一个四边形，至少有一对平行边。其中，这两条平行边必须是水平的。更具体地说，一个梯形被定义为由一个顶部线段、一个底部线段和左右两条垂直的“支柱”（可能退化为一个点）所围成的区域。这使得每个梯形内部不包含任何输入线段的内部点。
  • 主要目标：通过引入垂直的“分割线”，从每个线段端点（有时也从交点）向上和向下延伸，直到碰到另一条线段或边界，从而将平面分解为一系列这样的梯形单元。这为许多几何查询和算法提供了基础数据结构。

第二步：梯形分解的基本构建过程
我们可以通过一个直观的“平面扫描”思想来理解构建过程，但更经典的描述是随机增量构造。这里我们分步描述逻辑过程：

  1. 输入：一组互不相交的线段集合 S = {s₁, s₂, …, sₙ}。假设它们在一个大的包围框内。
  2. 初始化：开始时，整个包围框就是一个大的梯形（实际上是一个矩形）。
  3. 逐步插入线段：按照某种顺序（例如随机顺序）逐一插入每条线段 sᵢ。对于每条新插入的线段 sᵢ：
    a. 定位：首先找到当前梯形分解结构中，线段 sᵢ 的左端点位于哪个梯形内。
    b. 分割：线段 sᵢ 会穿过一系列现有的梯形。对于它穿过的每一个梯形 T：
    - 线段 sᵢ 将梯形 T “切割”成上下两部分。
    - 我们需要调整 T 的顶部或底部边，使其在 sᵢ 穿过的部分，以 sᵢ 作为新的边界。
    - 关键是，在线段 sᵢ 的左端点处，需要从该点向上和向下引出垂直分割线，直到碰到 T 的顶部边和底部边，这可能会将左边的区域进一步细分。
    - 同样，在线段 sᵢ 的右端点处，也需要引入垂直分割线。
    c. 合并：在完成对 sᵢ 穿过的所有梯形的分割和调整后，新产生的区域可能会与相邻的、被同一垂直线贯穿的区域合并，如果它们的顶部边和底部边相同，就合并成一个更大的梯形。这一步是为了保持分解的简洁性，避免不必要的细小梯形。
  4. 输出：当所有线段插入完毕后，我们就得到了平面的一个梯形分解。每个梯形由至多两条线段（作为顶边和底边）和左右两条垂直线界定。

第三步：数据结构与搜索结构
为了高效地使用梯形分解，我们通常将构建过程与一个搜索结构（通常是一个随机化的二叉搜索树，称为“梯形图”的伴生结构）结合起来。

  • 梯形图 (Trapezoidal Map)：这是分解结果的图表示。节点代表梯形，边代表梯形之间的邻接关系（通过垂直线段或输入线段的端点连接）。
  • 搜索结构 (Search Structure)：这是一个决策树，用于根据一个查询点（x, y）的坐标，快速定位它位于哪个梯形中。树的内部节点是两种类型：
    • x-节点：存放一个线段端点（x坐标）。根据查询点的x坐标是小于还是大于该节点的x坐标，决定向左还是向右子树搜索。
    • y-节点：存放一条线段 s。根据查询点是在线段 s 的上方还是下方，决定向左还是向右子树搜索。
  • 在随机增量构造算法中，线段以随机顺序插入。每次插入一条新线段时，我们不仅更新梯形图，也更新搜索结构：在树中，将被新线段“影响”的、那些被分割的梯形所对应的叶子节点，替换为一个小型的、针对这条新线段和其产生的垂直分割线的新子树。这种随机化保证了搜索结构期望上是平衡的。

第四步：性质与应用

  • 复杂度：对于 n 条互不相交的线段，最终的梯形分解包含 O(n) 个梯形、顶点和边。随机增量构造算法的期望时间复杂度为 O(n log n)，期望空间复杂度为 O(n)。点定位查询（给定点找所在梯形）的期望时间为 O(log n)。
  • 应用：
    1. 点定位：如前所述，梯形分解及其搜索结构是解决平面点定位问题（给定一个由线段构成的平面细分和一个查询点，确定点落在哪个区域）的经典、高效方法之一。
    2. 多边形三角剖分：梯形分解可以作为简单多边形三角剖分算法的第一步。首先对多边形进行梯形分解，然后每个梯形（由多边形的两条边和两条垂直线围成）很容易再被划分为两个三角形。
    3. 可见性计算：在计算从某个点能看见哪些线段（可见性图）时，梯形分解能帮助系统化地处理遮挡关系。
    4. 运动规划：在二维空间为机器人规划无碰撞路径时，自由空间可以被梯形分解，路径规划则在相邻梯形之间进行。

总结来说，梯形分解是一种将平面线段排列规整化的工具，它通过强制引入垂直分割，将空间划分为顶部和底部由输入线段界定的梯形单元。其核心价值在于构建了一个可用于快速点定位的搜索结构，并作为解决许多更复杂几何问题的基础步骤。

计算几何中的梯形分解（Trapezoidal Decomposition in Computational Geometry） 我们来详细讲解计算几何中的“梯形分解”。这是一个将复杂平面区域（通常是由一组线段或简单多边形边界定义的平面细分）系统地划分为更简单、易于处理的梯形结构的方法。 第一步：问题与目标 想象在平面上有一组互不相交的线段（除了可能在端点处相交），这些线段可能是简单多边形的边，也可能是任意放置的线段。我们的目标是：将这个被线段分割的平面区域，系统地划分成一组“梯形”。 什么是这里的“梯形”？ 在这个上下文中，梯形被放宽了定义：它是一个四边形，至少有一对平行边。其中，这两条平行边必须是 水平的 。更具体地说，一个梯形被定义为由一个顶部线段、一个底部线段和左右两条垂直的“支柱”（可能退化为一个点）所围成的区域。这使得每个梯形内部不包含任何输入线段的内部点。 主要目标 ：通过引入垂直的“分割线”，从每个线段端点（有时也从交点）向上和向下延伸，直到碰到另一条线段或边界，从而将平面分解为一系列这样的梯形单元。这为许多几何查询和算法提供了基础数据结构。 第二步：梯形分解的基本构建过程 我们可以通过一个直观的“平面扫描”思想来理解构建过程，但更经典的描述是随机增量构造。这里我们分步描述逻辑过程： 输入 ：一组互不相交的线段集合 S = {s₁, s₂, …, sₙ}。假设它们在一个大的包围框内。 初始化 ：开始时，整个包围框就是一个大的梯形（实际上是一个矩形）。 逐步插入线段 ：按照某种顺序（例如随机顺序）逐一插入每条线段 sᵢ。对于每条新插入的线段 sᵢ： a. 定位 ：首先找到当前梯形分解结构中，线段 sᵢ 的左端点位于哪个梯形内。 b. 分割 ：线段 sᵢ 会穿过一系列现有的梯形。对于它穿过的每一个梯形 T： - 线段 sᵢ 将梯形 T “切割”成上下两部分。 - 我们需要调整 T 的顶部或底部边，使其在 sᵢ 穿过的部分，以 sᵢ 作为新的边界。 - 关键是，在线段 sᵢ 的左端点处，需要从该点向上和向下引出 垂直分割线 ，直到碰到 T 的顶部边和底部边，这可能会将左边的区域进一步细分。 - 同样，在线段 sᵢ 的右端点处，也需要引入垂直分割线。 c. 合并 ：在完成对 sᵢ 穿过的所有梯形的分割和调整后，新产生的区域可能会与相邻的、被同一垂直线贯穿的区域合并，如果它们的顶部边和底部边相同，就合并成一个更大的梯形。这一步是为了保持分解的简洁性，避免不必要的细小梯形。 输出 ：当所有线段插入完毕后，我们就得到了平面的一个梯形分解。每个梯形由至多两条线段（作为顶边和底边）和左右两条垂直线界定。 第三步：数据结构与搜索结构 为了高效地使用梯形分解，我们通常将构建过程与一个搜索结构（通常是一个随机化的二叉搜索树，称为“梯形图”的伴生结构）结合起来。 梯形图 (Trapezoidal Map) ：这是分解结果的图表示。节点代表梯形，边代表梯形之间的邻接关系（通过垂直线段或输入线段的端点连接）。 搜索结构 (Search Structure) ：这是一个决策树，用于根据一个查询点（x, y）的坐标，快速定位它位于哪个梯形中。树的内部节点是两种类型： x-节点 ：存放一个线段端点（x坐标）。根据查询点的x坐标是小于还是大于该节点的x坐标，决定向左还是向右子树搜索。 y-节点 ：存放一条线段 s。根据查询点是在线段 s 的上方还是下方，决定向左还是向右子树搜索。 在 随机增量构造 算法中，线段以随机顺序插入。每次插入一条新线段时，我们不仅更新梯形图，也更新搜索结构：在树中，将被新线段“影响”的、那些被分割的梯形所对应的叶子节点，替换为一个小型的、针对这条新线段和其产生的垂直分割线的新子树。这种随机化保证了搜索结构期望上是平衡的。 第四步：性质与应用 复杂度 ：对于 n 条互不相交的线段，最终的梯形分解包含 O(n) 个梯形、顶点和边。随机增量构造算法的 期望时间复杂度 为 O(n log n)， 期望空间复杂度 为 O(n)。点定位查询（给定点找所在梯形）的期望时间为 O(log n)。 应用 ： 点定位 ：如前所述，梯形分解及其搜索结构是解决平面点定位问题（给定一个由线段构成的平面细分和一个查询点，确定点落在哪个区域）的经典、高效方法之一。 多边形三角剖分 ：梯形分解可以作为简单多边形三角剖分算法的第一步。首先对多边形进行梯形分解，然后每个梯形（由多边形的两条边和两条垂直线围成）很容易再被划分为两个三角形。 可见性计算 ：在计算从某个点能看见哪些线段（可见性图）时，梯形分解能帮助系统化地处理遮挡关系。 运动规划 ：在二维空间为机器人规划无碰撞路径时，自由空间可以被梯形分解，路径规划则在相邻梯形之间进行。 总结来说 ，梯形分解是一种将平面线段排列规整化的工具，它通过强制引入垂直分割，将空间划分为顶部和底部由输入线段界定的梯形单元。其核心价值在于构建了一个可用于快速点定位的搜索结构，并作为解决许多更复杂几何问题的基础步骤。