编辑“︁三角剖分（Triangulation）”︁（章节）

== 算法实现 ==
=== 增量算法（Bowyer-Watson 算法） ===
一种常用的德劳内三角剖分算法，步骤如下：
<syntaxhighlight lang="python">
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
</syntaxhighlight>

'''输入示例'''：
<pre>
points = [(0, 0), (1, 0), (0.5, 1), (0.5, 0.5)]
</pre>

'''输出示例'''（三角形列表）：
<pre>
[(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)]
</pre>

=== 多边形三角剖分（耳切法） ===
适用于简单多边形的算法，通过递归切割“耳朵”（由连续三个顶点组成的凸角三角形）实现：
<syntaxhighlight lang="python">
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
</syntaxhighlight>