三角剖分（Triangulation）

三角剖分（Triangulation）

三角剖分是计算几何中的一个重要概念，指将平面或三维空间中的点集或多边形分割成若干个不相交的三角形，使得这些三角形的并集恰好覆盖原始图形。三角剖分在计算机图形学、地理信息系统（GIS）、有限元分析、路径规划等领域有广泛应用。

基本概念

三角剖分的核心目标是将给定的点集或多边形分割成若干三角形，并满足以下条件：

• 所有三角形的并集完全覆盖原始图形。
• 任意两个三角形要么不相交，要么仅共享一条边或一个顶点。

三角剖分可以分为：

• 点集三角剖分（Point Set Triangulation）：对平面上的离散点集进行三角剖分。
• 多边形三角剖分（Polygon Triangulation）：将简单多边形分割成三角形。

德劳内三角剖分（Delaunay Triangulation）

一种特殊的点集三角剖分，满足空圆性质（Empty Circle Property）：对于剖分中的任意三角形，其外接圆内不包含其他点。德劳内三角剖分具有最大化最小角、避免狭长三角形的优良性质。

数学定义： $\text{给定点集 }P\text{，其德劳内三角剖分 }DT(P)\text{ 满足：对于任意三角形 }\mathrm{△}abc\in DT(P)\text{，其外接圆 }C(abc)\text{ 内不包含 }P\text{ 的其他点。}$

算法实现

增量算法（Bowyer-Watson 算法）

一种常用的德劳内三角剖分算法，步骤如下：

def bowyer_watson(points):
    # 初始化超级三角形（包含所有点）
    super_triangle = create_super_triangle(points)
    triangulation = [super_triangle]
    
    for p in points:
        bad_triangles = []
        # 找到所有外接圆包含p的三角形
        for tri in triangulation:
            if is_point_in_circumcircle(p, tri):
                bad_triangles.append(tri)
        
        polygon = []
        # 构建“空洞”的多边形边界
        for tri in bad_triangles:
            for edge in tri.edges:
                if edge not in [e for t in bad_triangles for e in t.edges if t != tri]:
                    polygon.append(edge)
        
        # 移除坏的三角形
        triangulation = [tri for tri in triangulation if tri not in bad_triangles]
        
        # 用新三角形填充空洞
        for edge in polygon:
            new_tri = Triangle(edge.p1, edge.p2, p)
            triangulation.append(new_tri)
    
    # 移除与超级三角形顶点相关的三角形
    triangulation = [tri for tri in triangulation if not any(v in super_triangle.vertices for v in tri.vertices)]
    return triangulation

输入示例：

points = [(0, 0), (1, 0), (0.5, 1), (0.5, 0.5)]

输出示例（三角形列表）：

[(0, 0), (1, 0), (0.5, 0.5)]
[(0, 0), (0.5, 1), (0.5, 0.5)]
[(1, 0), (0.5, 1), (0.5, 0.5)]

多边形三角剖分（耳切法）

适用于简单多边形的算法，通过递归切割“耳朵”（由连续三个顶点组成的凸角三角形）实现：

def ear_clipping(polygon):
    triangles = []
    remaining = polygon.copy()
    
    while len(remaining) > 3:
        for i in range(len(remaining)):
            prev = remaining[i-1]
            curr = remaining[i]
            next = remaining[(i+1) % len(remaining)]
            
            # 检查是否为耳朵（凸且无其他顶点在三角形内）
            if is_convex(prev, curr, next) and not has_points_inside(prev, curr, next, remaining):
                triangles.append((prev, curr, next))
                remaining.pop(i)
                break
    triangles.append(tuple(remaining))
    return triangles

可视化示例

graph TD A[三角剖分类型] --> B[点集三角剖分] A --> C[多边形三角剖分] B --> D[德劳内三角剖分] C --> E[耳切法] D --> F[空圆性质] E --> G[凸角切割]

应用案例

1. 地形建模：通过三角剖分将离散高程点转换为连续地形表面。 2. 有限元分析：将复杂几何体分割为三角形单元进行物理模拟。 3. 路径规划：在机器人导航中，三角剖分用于构建可通行区域的可视图。 4. 图像处理：使用三角网格实现图像变形（如Morphing）。

数学性质

• 平面简单多边形的三角剖分始终存在，且三角形数量为 $n-2$（$n$ 为顶点数）。
• 德劳内三角剖分是平面点集的对偶图（Dual Graph）对应的沃罗诺伊图（Voronoi Diagram）。

进阶主题

• 约束德劳内三角剖分（Constrained Delaunay）：强制保留某些边的剖分。
• 三维三角剖分（3D Tetrahedralization）：将三维空间分割为四面体。
• 并行三角剖分算法：适用于大规模点集的并行计算方法。