计算几何中的多边形三角剖分

1. 基本定义与目标
   多边形三角剖分（Polygon Triangulation）指将一个简单多边形（不自交的多边形）划分为一系列互不相交的三角形，使得这些三角形的并集等于原多边形，且任意两个三角形要么不相交，要么恰好共享一条边（即多边形的对角线）或一个顶点。

   • 多边形的顶点称为剖分中三角形的顶点，多边形的边是某些三角形的边，新增的对角线连接多边形的两个非相邻顶点。
   • 目标：用尽可能少的对角线（或满足特定优化条件）完成三角剖分，常用于图形学、有限元分析、路径规划等。

2. 剖分的存在性与三角形数量
   任意简单多边形（n ≥ 3）都可以被三角剖分。

   • 定理：一个n个顶点的简单多边形，其三角剖分恰好包含 n-2 个三角形，且使用 n-3 条对角线。
   • 证明思路（数学归纳法）：
     1. 对n=3，无需对角线，三角形数为1。
     2. 假设对顶点数小于n的多边形成立。对n顶点多边形，任取一顶点，可找到另一顶点与其构成一条完全位于多边形内部的对角线（通过“耳裁”法），将多边形分成两个顶点数更少的多边形，应用归纳假设可得结论。

3. 耳裁算法（Ear Clipping）
   一种简单的三角剖分算法，基于“耳”的存在性：

   • 定义：多边形的一个顶点v_i是“耳”，如果其相邻顶点v_{i-1}和v_{i+1}连接的线段是完全位于多边形内部的一条对角线（即不与任何边相交）。
   • 步骤：
     1. 存储多边形的顶点序列（通常按逆时针顺序）。
     2. 循环直到只剩下一个三角形：
        a. 找到一个耳顶点v_i。
        b. 输出三角形(v_{i-1}, v_i, v_{i+1})。
        c. 从多边形中移除v_i，更新顶点序列。
   • 时间复杂度：朴素实现为O(n³)（每步需检查对角线是否合法），优化后可达O(n²)。
   • 耳的存在性定理（“二耳定理”）：任何简单多边形至少有两个耳，保证算法可进行。

4. 单调多边形的线性时间三角剖分
   对特殊多边形可优化至O(n)时间：

   • 单调多边形：存在一条直线L，使得多边形与任意垂直于L的直线相交为一条线段（即多边形在L方向上“单调”）。
   • 算法思路（以单调于垂直方向为例）：
     1. 将顶点按y坐标排序（已有序时直接使用）。
     2. 用栈从左到右扫描顶点，分为左链和右链处理，通过栈维护待剖分的顶点，每次遇到新顶点时弹出栈顶构成三角形。
   • 此算法是许多高效三角剖分的基础，如将一般多边形分割为单调多边形再分别剖分。

5. 多边形的单调分割
   将一般简单多边形转化为单调多边形：

   • 通过扫描线算法识别“分裂顶点”与“合并顶点”（根据内角方向），添加对角线消除非单调顶点。
   • 分割后得到多个y-单调多边形，再分别用线性时间三角剖分，总复杂度O(n log n)（主要来自顶点排序）。

6. 带空洞多边形的三角剖分
   允许多边形包含空洞（即多个边界，内边界为孔洞）：

   • 方法：将外边界和内边界合并为一个顶点序列（如通过“桥接”边连接内外边界），转化为简单多边形再剖分，但需保证添加的桥接边不交叉。
   • 可用约束三角剖分（Constrained Triangulation）处理，要求某些边必须出现在三角剖分中。

7. 最优三角剖分问题
   在三角剖分中优化特定目标（如最小化对角线长度和、最大化最小内角等）：

   • 最小权重三角剖分：目标是使所有三角形边长总和最小，可用动态规划在O(n³)时间求解。
   • 最大化最小角：Delaunay三角剖分在点集上最大化最小角，但对多边形需约束边界，有O(n log n)算法。

8. 应用与扩展

   • 图形学渲染：将多边形网格细分为三角形以便光栅化。
   • 有限元分析：三角网格用于离散化求解偏微分方程。
   • 计算几何基础：许多算法依赖三角剖分，如可见性计算、路径规划。
   • 三维扩展：多面体表面三角剖分（更复杂，可能需四面体剖分）。