逐点插入法构建Delaunay 三角网

学科竞赛 测绘程序设计
1

Delaunay 三角网生成（逐点插入法 / Bowyer-Watson）

1. 方法概述

逐点插入法（Bowyer-Watson Algorithm）是一种经典的 Delaunay 三角剖分构建方法。其核心思想是：

每插入一个点，就删除所有“坏三角形”（外接圆包含该点的三角形），然后用新点重新连接形成新的三角形。

2. 算法步骤

（1）构建超级三角形

首先根据所有点的范围构建一个覆盖所有点的“超级三角形”。

min_x = min(p[0] for p in points)
max_x = max(p[0] for p in points)
min_y = min(p[1] for p in points)
max_y = max(p[1] for p in points)

dx = max_x - min_x
dy = max_y - min_y
t = max(dx, dy) * 10

mid_x = (min_x + max_x) / 2
mid_y = (min_y + max_y) / 2

v_p1 = [mid_x - t, mid_y - t]
v_p  = [mid_x, mid_y + t]
v_p2 = [mid_x + t, mid_y - t]

（2）初始化点集与三角形集合

将超级三角形顶点加入点集，并初始化三角形列表。

all_points = points + [v_p1, v_p, v_p2]
triangles = [[n, n+1, n+2]]

（3）逐点插入处理

对原始点集中的每一个点进行处理。

for each point A in points:

（4）寻找坏三角形（Bad Triangles）

判断当前点是否落在某个三角形的外接圆内：

如果点 A 在三角形外接圆内 → 该三角形为坏三角形

if point_in_circumcircle_extended(point, triangle, all_points):
    bad_triangles.append(triangle)

（5）删除坏三角形

将所有坏三角形从当前三角形集合中移除。

for triangle in bad_triangles:
    triangles.remove(triangle)

（6）提取边界多边形（Polygon Hole）

找出坏三角形组成的“空洞边界”，即只出现一次的边：

如果一条边只属于一个坏三角形 → 该边是边界边

polygon_edges = []

（7）重新构建三角形

用当前插入点 + 边界边重新生成三角形：

for edge in polygon_edges:
    triangles.append([i, edge[0], edge[1]])

（8）移除超级三角形相关结果

最后删除所有包含超级三角形顶点的三角形：

final_triangles = []
for triangle in triangles:
    if all(t < n for t in triangle):
        final_triangles.append(triangle)

3. 核心函数：外接圆判断

point_in_circumcircle_extended

用于判断点是否在三角形外接圆内。

def point_in_circumcircle_extended(self, point, triangle, all_points):
    px, py = point

    p1, p2, p3 = [all_points[i] for i in triangle]

    x1, y1 = p1
    x2, y2 = p2
    x3, y3 = p3

    d = 2 * ((x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1))

    if abs(d) < 1e-10:
        return False

    ux = ((x1**2 + y1**2)*(y2 - y3) +
          (x2**2 + y2**2)*(y3 - y1) +
          (x3**2 + y3**2)*(y1 - y2)) / d

    uy = ((x1**2 + y1**2)*(x3 - x2) +
          (x2**2 + y2**2)*(x1 - x3) +
          (x3**2 + y3**2)*(x2 - x1)) / d

    radius_sq = (x1 - ux)**2 + (y1 - uy)**2
    dist_sq = (px - ux)**2 + (py - uy)**2

    return dist_sq < radius_sq

4. 总结

Bowyer-Watson 逐点插入法的关键在于：

  • 每次插入点都会“局部重构”三角网
  • 通过外接圆判断维护 Delaunay 性质
  • 使用超级三角形保证边界完整性
  • 最终去除无效超级结构

关于泰森多边形的更多知识分享见博客： 泰森多边形 – ntu17’s Musings

2 个赞