计算几何中的单调剖分（Monotone Partition） 好的，我们开始学习“单调剖分”。这是计算几何中一个将复杂多边形分解为更简单子部分的关键预处理技术，尤其为高效三角剖分算法奠定基础。 第一步：从问题动机出发——为什么需要“剖分”？ 想象一个任意给定的简单多边形（即边不自交的多边形）。我们想对它进行三角剖分，即用不相交的对角线将其内部划分为全部由三角形组成的集合。一个直接的想法是递归地切割多边形，但面对“有凹角”的复杂多边形，直接设计高效且正确的算法并不容易。单调剖分的核心思想是： 先将一个任意的简单多边形，切割成若干个“单调多边形”，因为单调多边形拥有良好的几何性质，可以非常高效（线性时间）地被三角剖分。 第二步：理解核心概念——“单调多边形” 一个多边形被称为相对于某条直线L是“单调的”，如果任意一条垂直于L的直线，与多边形的交集是一个连续的线段（或一个点，或为空集）。 更直观的理解 ：我们通常考虑相对于x轴的单调性（y-单调多边形）。这意味着，如果你想象一个垂直的扫描线从左向右扫过整个多边形，这条扫描线与多边形内部的交点始终是一个 连续的区间 ，不会分裂成多段。这等价于说，多边形边界可以分成两条链（左链和右链），每条链上的点，其y坐标的变化是单调的（即一直增加或一直减少）。 例子 ：一个顶点按y坐标排序后呈“山”形或“谷”形的多边形是y-单调的。而一个像“C”字形或更复杂凹陷形状的多边形，垂直扫描线可能会与之交于多个离散的片段，因此不是y-单调的。 第三步：剖分目标与思路——如何得到单调多边形？ 我们的目标是将输入多边形P转化为一个由y-单调多边形组成的集合，并且这些多边形的并集恰好是P。实现这一点的关键，是识别并消除那些导致多边形不单调的顶点—— 拐点 。 顶点分类 ：在多边形中，根据其相邻边的方向，顶点可以分为几种类型（假设我们沿边界逆时针行走）： 起始点 ：两条邻边都向下走，顶点是局部y坐标最小值。 终止点 ：两条邻边都向上走，顶点是局部y坐标最大值。 规则点 ：两条邻边一个向上一个向下，y坐标单调变化。 分裂点 ：两条邻边都向下走，但顶点是局部y坐标最大值（在一个凹进去的“帽沿”）。 合并点 ：两条邻边都向上走，但顶点是局部y坐标最小值（在一个凸出来的“屋檐”）。 关键洞察 ：导致多边形非y-单调的“罪魁祸首”正是 分裂点 和 合并点 。在分裂点，垂直扫描线会首次与多边形分裂成两段；在合并点，分开的两段会合并回来。 第四步：算法核心——消除分裂点与合并点 单调剖分算法（如著名的 Lee-Preparata 算法）通常采用 平面扫描线 技术： 预处理 ：将所有顶点按y坐标从高到低排序（扫描线从上往下扫）。 扫描与维护 ：用一条水平扫描线从上到下移动，并维护一个数据结构（通常是用平衡二叉树实现的“扫描线状态”），它记录了当前扫描线与多边形边界相交的边，并按其交点的x坐标排序。 处理事件点 （每个顶点都是一个事件点）： 当扫描线遇到一个 分裂点 时，我们需要添加一条对角线，将这个顶点连接到其左侧链上的某个特定顶点，从而“缝合”分裂开的部分。这个连接点可以通过查询扫描线状态结构找到。 当扫描线遇到一个 合并点 时，同样，我们需要添加一条对角线，将其连接到其左侧链上的某个顶点，以消除这个合并结构。 对于起始点、终止点和规则点，我们只需要更新扫描线状态结构（插入或删除边）。 结果 ：添加的所有对角线（以及多边形的原始边）共同将原多边形分割成了若干个多边形。可以证明，这些子多边形都不再包含任何分裂点或合并点，因此它们都是y-单调多边形。 第五步：总结与应用 单调剖分本身 ：是一个将任意简单多边形在线性时间 O(n log n) 内（主要开销在顶点排序）分解为y-单调多边形集合的过程。添加的对角线数量是O(n)级别的。 后续三角剖分 ：一旦得到单调多边形，每个单调多边形可以在O(n)时间内被三角剖分（例如，使用简单的贪心栈算法）。因此，整个“单调剖分 + 单调多边形三角剖分”的流程，构成了一个O(n log n)时间的简单多边形三角剖分完整算法，这是许多教科书中的经典方法。 核心价值 ：单调剖分展示了计算几何中“分而治之”和“规范化”的深刻思想。它将一个不规则的问题（任意多边形三角剖分）转化为若干个具有规整几何结构（单调性）的子问题，从而大幅降低了后续处理的复杂度。除了三角剖分，单调剖分在可见性计算、运动规划等领域也是有用的预处理步骤。