计算几何中的单调多边形划分（Monotone Partitioning of Polygons in Computational Geometry） 多边形划分的基本概念 在多边形几何处理中， 多边形划分 指的是将一个复杂的简单多边形（不自交）分解为一系列更简单、更容易处理的多边形子区域的过程。最常见的划分目标包括 凸多边形 、 星形多边形 或 单调多边形 。划分的动机是简化计算，例如在三维图形学的三角剖分、机器人运动规划或可见性计算中，将问题归结为在更规则子部件上求解。划分的质量通常用 子多边形数量 或 总内边长度 等指标衡量。 单调多边形的定义 一个 单调多边形 相对于某条直线（通常是某坐标轴，如x轴）是单调的，是指多边形边界与该直线垂直的任何直线的交点至多有两个，且边界可分成两段，每段在该直线方向上是单调的。通常我们讨论 y-单调多边形 ：多边形边界与任何水平线（垂直于y轴的线）至多交于两个点，且存在两个顶点（通常称为 最高点 与 最低点 ），使得从左边界和右边界分别从最高点到最低点是y值单调不增或不降的路径。单调多边形是比凸多边形更一般、但比任意多边形更规整的类，其重要性在于可在线性时间内三角剖分。 单调多边形划分的目标 给定一个任意简单多边形（不一定是单调的），目标是将其划分为若干个y-单调多边形。这是多边形三角剖分算法（如 扫线三角剖分 ）的关键预处理步骤，因为单调多边形可在O(n)时间三角剖分，而任意多边形直接三角剖分需O(n log n)时间。划分方法是在多边形内部添加不相交的对角线，将多边形切割成单调片段。 如何识别单调性破坏点 多边形的顶点按类型分为： 起始点 、 终止点 、 分裂点 、 合并点 、 规则点 ，这基于其两个邻边的y值关系（上、下、水平）以及多边形内部的局部位置。具体定义如下（假设多边形顶点按逆时针顺序给出，y轴向上）： 起始点 ：两个邻边都在该点之下，多边形内部在点之上。 终止点 ：两个邻边都在该点之上，多边形内部在点之下。 分裂点 ：两个邻边都在该点之下，多边形内部在点之下。 合并点 ：两个邻边都在该点之上，多边形内部在点之上。 规则点 ：其他情况（一条边在上，一条边在下）。 其中， 分裂点 和 合并点 是破坏多边形y-单调性的顶点，因为它们会导致水平线与多边形边界有多个交点。 划分算法：平面扫描法 采用 平面扫描算法 ，用一条水平线从上到下扫描多边形。关键数据结构包括： 事件队列 ：按y值降序存储所有顶点。 扫描线状态 ：维护当前水平线与多边形边界相交的边，并按x坐标排序。 算法步骤： a. 对所有顶点按y坐标降序排序，放入事件队列。 b. 扫描线从上往下移动，在每个顶点事件处处理： 对于 分裂点 ：在其左侧找到扫描线状态中最近的边，从该边的某个点（通常通过查询其与水平线的交点）向分裂点添加一条对角线，从而消除分裂特性。 对于 合并点 ：类似地，在其左侧找到扫描线状态中最近的边，添加对角线连接该边的相关点与合并点。 添加的对角线将多边形分解，使得分裂点与合并点不再存在，所有子多边形成为y-单调的。 算法正确性与复杂度 该算法确保每个分裂点和合并点都通过添加一条对角线被消除，从而最终多边形中只包含起始点、终止点和规则点，这等价于y-单调性。算法运行时间：顶点排序O(n log n)，扫描过程每个顶点处理O(log n)（因为扫描线状态用平衡二叉树维护），总时间O(n log n)。空间复杂度O(n)。 应用 三角剖分 ：将多边形划分为单调部分后，每个单调部分可在O(n_ i)时间三角剖分，总时间O(n log n) + O(n) = O(n log n)。 可见性计算 ：单调多边形中两点之间的最短路径或可见性多边形可高效计算。 三维图形学 ：多边形网格的三角化是渲染的基础步骤。 通过以上步骤，我们完成了从多边形划分的基本概念，到单调多边形的定义，再到识别单调性破坏点、使用平面扫描算法进行划分，最终证明算法正确性和阐述应用的完整知识链。