计算几何中的单调剖分 我们来循序渐进地了解计算几何中的一个基础而重要的概念——单调剖分。 第一步：核心目标与基本定义 核心目标 ：单调剖分的核心目的是将一个复杂的 简单多边形 （即边界不自交的多边形）切割成若干个更简单的子多边形，称为“单调多边形”或“单调片”。这种简化是解决许多多边形问题（如三角剖分、艺术画廊问题、可见性计算）的关键预处理步骤。 基本定义 ：要理解单调剖分，首先需要明确“单调多边形”的定义。 单调链 ：在平面上给定一条直线L（通常为了方便，我们取L为垂直或水平线）。一条多边形链（由顶点依次连接而成的折线）如果与任何一条垂直于L的直线相交至多一次，则称这条链关于直线L是 单调的 。直观地说，沿着这条链移动时，在垂直于L的方向上，坐标值是严格单调递增或递减的，不会“回头”。 单调多边形 ：一个简单多边形P，如果存在一条直线L，使得P的边界可以分解为两条关于L都单调的链，则称P是一个 关于L单调的多边形 。通常，我们讨论的是关于垂直（y轴）或水平（x轴）单调的多边形。关于y轴单调的多边形，其边界由左、右两条单调链组成，这两条链的顶点y坐标都是单调变化的。 第二步：为什么需要单调剖分？ 一个任意的简单多边形可能非常不规则，其边界“起伏不定”，这给许多算法（如三角剖分）带来了直接处理的困难。例如，一个高效的三角剖分算法（如扫线法）通常要求输入多边形是单调的。 单调剖分的作用 ，就是作为一个“桥梁”或“预处理步骤”，它能够 将任意简单多边形转化为一系列y-单调（或x-单调）多边形 的并集。这些单调多边形之间仅共享边（即剖分产生的对角线），而不再重叠。 一旦得到了单调剖分，就可以 独立地对每个单调多边形 应用更简单、更高效的专门算法（如单调多边形三角剖分的线性时间算法），最后将所有结果组合，就得到了原问题的解。 第三步：如何构造单调剖分？核心思想与顶点分类 构造单调剖分的经典算法是扫描线算法。其核心思想是：想象一条垂直线从左到右扫描整个多边形，在扫描过程中处理多边形的顶点，并在 某些顶点之间添加对角线 ，从而消除导致多边形不单调的“局部结构”。 顶点分类 ：为了判断在哪里添加对角线，算法首先根据多边形顶点在局部几何结构中的角色进行分类。给定一个顶点v，考虑与其相邻的两个顶点（前驱 prev(v) 和后继 next(v) ）。 起始点（Start） ：如果 prev(v) 和 next(v) 都在v的下方，且多边形内部在v处形成一个向下的凹口，则v是起始点。它是单调链可能的开始。 终止点（End） ：如果 prev(v) 和 next(v) 都在v的上方，且多边形内部在v处形成一个向上的凹口，则v是终止点。它是单调链的结束。 分裂点（Split） ：如果 prev(v) 和 next(v) 都在v的下方，但多边形内部在v处是向上凸出的（即v是一个凹顶点），则v是分裂点。这是导致多边形不单调的“罪魁祸首”之一，需要从它向左引出一条对角线连接到某个已扫描过的顶点。 合并点（Merge） ：如果 prev(v) 和 next(v) 都在v的上方，但v是凹顶点，则v是合并点。同样，它也需要处理，通常需要与一个已扫描的顶点连接对角线。 规则点（Regular） ：其他情况，例如 prev(v) 在下方， next(v) 在上方，或者反过来。这类顶点通常不会破坏单调性。 第四步：算法流程与数据结构（以垂直单调剖分为例） 输入 ：一个由n个顶点（按逆时针顺序给出）定义的简单多边形P。 预处理 ：将多边形所有顶点按它们的x坐标排序（如果x坐标相同，则按y坐标排序）。得到一个有序的顶点事件队列。 扫描与处理 ：使用一条垂直扫描线从左到右处理每个事件点（顶点）。同时，维护一个动态的数据结构（通常是一个平衡二叉搜索树）来存储当前与扫描线相交的多边形边（称为“扫描线状态”）。 关键操作 ：当扫描线遇到不同类型的顶点时，进行不同的操作： 遇到 起始点 ：将其关联的边插入扫描线状态。 遇到 终止点 ：将其关联的边从扫描线状态中移除。 遇到 分裂点 ：这是算法的核心。在扫描线状态中，找到位于分裂点正左侧的那条边（即y坐标恰好位于分裂点上下方两条边之间的那条边）。然后，从分裂点向那条边的下端（或上端，取决于实现）引一条对角线。添加这条对角线后，多边形被分割。分裂点成为新的单调链的起始点，其关联边被加入扫描线状态。 遇到 合并点 ：类似地，找到其左侧的边，并从合并点向左引对角线连接到合适顶点。合并点成为单调链的终止点，其关联边从状态中移除。 遇到 规则点 ：更新扫描线状态（例如，移除一条旧边，加入一条新边）。 输出 ：算法结束后，所有添加的对角线连同多边形的原边一起，将多边形P划分成了若干个y-单调多边形。 第五步：算法性质与应用 时间复杂度 ：经典的扫描线算法可以在 O(n log n) 时间内完成，其中n是多边形的顶点数。排序需要O(n log n)，每个顶点的处理（查找、插入、删除扫描线状态）需要O(log n)时间。 空间复杂度 ：O(n)，用于存储顶点、事件队列和扫描线状态。 主要应用 ： 多边形三角剖分 ：这是最直接的应用。先做单调剖分得到O(n)个单调多边形，然后对每个单调多边形在O(k)时间内三角剖分（k是该单调多边形的顶点数），总时间仍为O(n log n)，这是简单多边形三角剖分的最优算法之一。 艺术画廊问题 ：寻找覆盖多边形内部的最少守卫点。将多边形单调剖分后，问题可以在每个单调片上更容易分析和解决。 可见性计算 ：判断多边形内一点能看到多大范围。单调多边形的可见性计算更简单。 多边形偏移与骨架计算 ：在计算机图形学和CAD中，单调剖分可以简化这些复杂运算。 总结 ：单调剖分是一个 分而治之 的策略。它将一个复杂的几何结构（任意简单多边形）通过添加内部对角线，系统性地分解为一系列具有良好性质（单调性）的更简单子结构。其实现依赖对顶点局部几何的精细分类（起始、终止、分裂、合并、规则）和扫描线算法的高效处理。它是计算几何中连接“复杂输入”与“高效专用算法”的关键桥梁。