三角剖分

What · 是什么

三角剖分（Triangulation）是把平面点集（或多边形/平面区域）细分为一组互不重叠的三角形，覆盖整个点集凸包（或多边形内部），且所有点都作为三角形顶点。多边形三角剖分：顶点数 n 的多边形恰有 n-2 个三角形、n-3 条对角线；点集三角剖分：含 n 个点（其中 h 个凸包点）有 2n-2-h 个三角形。构造方法：耳切法（Ear Clipping，O(n²)，适合简单多边形）、三角剖分存在无限多种；『最优』剖分（最大化最小角、最小化总边长等）需用 Delaunay 或贪婪启发。应用：3D 渲染网格化、有限元、多边形面积/重心分解、单调多边形分解。

Why · 为什么

How · 实现

伪代码

# 耳切法剖分简单多边形
def triangulate(poly):
  if len < 3: return []
  tris = []
  while len(poly) > 3:
    for i in range(len(poly)):
      if is_ear(poly, i):
        prev, cur, nxt = neighbors
        tris.append((prev,cur,nxt))
        poly.remove(cur)
        break
  tris.append((poly[0],poly[1],poly[2]))
  return tris

def is_ear(poly, i):
  cur = poly[i]; prev=..., nxt=...
  if not is_convex(prev,cur,nxt): return False
  for p in poly(except these 3):
    if point_in_triangle(p, prev,cur,nxt): return False
  return True

Python 实现

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])


def point_in_tri(p, a, b, c):
    """点 p 是否在三角形 abc 内部或边上 (边界归为外部更稳妥? 此处含边)."""
    d1 = cross(a, b, p)
    d2 = cross(b, c, p)
    d3 = cross(c, a, p)
    has_neg = d1 < -1e-12 or d2 < -1e-12 or d3 < -1e-12
    has_pos = d1 > 1e-12 or d2 > 1e-12 or d3 > 1e-12
    return not (has_neg and has_pos)


def is_ear(poly, i):
    n = len(poly)
    prev = poly[(i - 1) % n]
    cur = poly[i]
    nxt = poly[(i + 1) % n]
    # 凸顶点检查 (假设多边形逆时针)
    if cross(prev, cur, nxt) <= 0:
        return False
    # 三角形内部无其他顶点
    for j, p in enumerate(poly):
        if p in (prev, cur, nxt):
            continue
        # 严格内部 (排除边上重叠)
        if point_in_tri(p, prev, cur, nxt) and \
           abs(cross(prev, cur, p)) > 1e-12 and \
           abs(cross(cur, nxt, p)) > 1e-12 and \
           abs(cross(nxt, prev, p)) > 1e-12:
            return False
    return True


def ear_clipping(poly):
    """耳切法: 简单多边形 -> 三角形列表 (逆时针)."""
    poly = list(poly)
    tris = []
    guard = 0
    while len(poly) > 3 and guard < 1000:
        guard += 1
        clipped = False
        for i in range(len(poly)):
            if is_ear(poly, i):
                prev = poly[(i - 1) % len(poly)]
                cur = poly[i]
                nxt = poly[(i + 1) % len(poly)]
                tris.append((prev, cur, nxt))
                poly.pop(i)
                clipped = True
                break
        if not clipped:
            break  # 数值问题或退化
    if len(poly) == 3:
        tris.append((poly[0], poly[1], poly[2]))
    return tris


def area(poly):
    s = 0.0
    n = len(poly)
    for i in range(n):
        x1, y1 = poly[i]
        x2, y2 = poly[(i + 1) % n]
        s += x1 * y2 - x2 * y1
    return s / 2.0


def tri_area(a, b, c):
    return abs(cross(a, b, c)) / 2.0


if __name__ == "__main__":
    # 凸多边形: 正方形
    sq = [(0, 0), (2, 0), (2, 2), (0, 2)]
    tris = ear_clipping(sq)
    assert len(tris) == 2
    assert abs(sum(tri_area(*t) for t in tris) - 4.0) < 1e-9

    # L 形多边形 (凹多边形): (0,0),(3,0),(3,1),(1,1),(1,3),(0,3)
    L = [(0, 0), (3, 0), (3, 1), (1, 1), (1, 3), (0, 3)]
    tris = ear_clipping(L)
    assert len(tris) == len(L) - 2
    total = sum(tri_area(*t) for t in tris)
    assert abs(total - abs(area(L))) < 1e-9, (total, area(L))

    # 五边形 (凸): 面积核对
    pent = [(0, 0), (4, 0), (5, 3), (2, 5), (0, 3)]
    tris = ear_clipping(pent)
    assert len(tris) == 3
    assert abs(sum(tri_area(*t) for t in tris) - abs(area(pent))) < 1e-9

    # C 形多边形 (严重凹): 面积核对
    c_poly = [(0, 0), (3, 0), (3, 3), (2, 3), (2, 1), (1, 1), (1, 3), (0, 3)]
    tris = ear_clipping(c_poly)
    assert len(tris) == len(c_poly) - 2, len(tris)
    assert abs(sum(tri_area(*t) for t in tris) - abs(area(c_poly))) < 1e-9

    # 三角形本身
    tri = [(0, 0), (1, 0), (0, 1)]
    tris = ear_clipping(tri)
    assert len(tris) == 1
    print("All tests passed.")

易错点

• 多边形方向（顺/逆时针）影响 cross 符号，耳切需一致处理
• 凹顶点不能被切（cross<0 不是耳朵）
• 内部包含测试要排除自身三个顶点
• 退化共线点会造出面积 0 三角形，破坏 n-2 计数
• 浮点下『点在三角形边界上』判定需 eps，否则耳朵误判
• 点集剖分要先把凸包点与内部点分离，直接耳切不适用

例题

信源

• OI Wiki✓ https://oi-wiki.org/geometry/triangulation/
• 书籍✓ CPH ch29 Geometry (p291-304)