Delaunay三角剖分

Delaunay三角剖分（Delaunay Triangulation）是计算几何中的一种重要方法，用于将一组平面点集划分为不相交的三角形，满足空圆特性（Delaunay准则）。该算法广泛应用于地理信息系统（GIS）、有限元分析、计算机图形学等领域。

定义与特性

给定平面上的点集$P=\{p_1,p_2,...,p_n\}$，其Delaunay三角剖分满足以下条件：

• 所有三角形的外接圆（称为外接圆）内部不包含点集$P$中的任何其他点（空圆特性）。
• 最大化所有三角形的最小内角，避免出现“狭长”的三角形。

数学表达式为：对于任意三角形$\mathrm{△}{p}_i{p}_j{p}_k$，其外接圆$C(\mathrm{△}{p}_i{p}_j{p}_k)$满足： $\mathrm{\forall }{p}_l\in P\setminus \{p_i,p_j,p_k\},p_l\notin \text{Int}(C(\mathrm{△}{p}_i{p}_j{p}_k))$

对偶图：Voronoi图

Delaunay三角剖分与Voronoi图互为对偶图。Voronoi图的每个顶点对应Delaunay三角形的一个外接圆圆心。

graph LR A[Delaunay三角剖分] -- 对偶 --> B[Voronoi图]

算法实现

常见的构造算法包括：

• 增量算法（Incremental Algorithm）
• 分治算法（Divide and Conquer）
• Bowyer-Watson算法（常用动态插入实现）

以下为Bowyer-Watson算法的Python实现示例：

import numpy as np
from scipy.spatial import Delaunay

# 输入：二维点集
points = np.array([[0, 0], [1, 0], [0.5, 1], [0.5, 0.5]])

# 计算Delaunay三角剖分
tri = Delaunay(points)

# 输出结果
print("三角形顶点索引：")
print(tri.simplices)
print("外接圆圆心坐标：")
print(tri.circumcenters)

输出示例：

三角形顶点索引：
[[3 1 2]
 [3 0 1]
 [3 0 2]]
外接圆圆心坐标：
[[0.5        0.5       ]
 [0.5        0.5       ]
 [0.5        0.5       ]]

实际应用案例

1. 地形建模：将离散高程点转换为三角形网格。 2. 路径规划：在机器人导航中生成可通行区域的三角网格。 3. 有限元分析：为物理模拟提供优化的网格结构。

graph TD A[离散点集] --> B(Delaunay三角剖分) B --> C[地形渲染] B --> D[碰撞检测] B --> E[流体模拟]

数学性质证明

Delaunay三角剖分的空圆特性可通过局部优化（LOP）验证：

• 对于任意两个相邻三角形构成的四边形，若交换对角线后外接圆半径减小，则交换对角线。
• 最终状态满足全局Delaunay条件。

$\mathrm{\forall }\mathrm{△}ABC\in {𝒯},\nexists P\in P\text{ s.t. }P\in \text{Int}(C(\mathrm{△}ABC))$

扩展与变体

• 约束Delaunay三角剖分（CDT）：强制包含指定边。
• 加权Delaunay三角剖分：考虑点权重（Power Diagram对偶）。
• 三维Delaunay四面体剖分：推广到三维空间。

可视化示例

graph TD P1((0,0)) -->|连接| P2((1,0)) P1 --> P3((0.5,1)) P2 --> P3 P4((0.5,0.5)) --> P1 P4 --> P2 P4 --> P3

该内容结构适合从基础到进阶的学习路径，结合理论、代码与实践案例，满足不同层次读者的需求。