编辑“︁Delaunay三角剖分”︁

{{DISPLAYTITLE:Delaunay三角剖分}}

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

== 定义与特性 ==
给定平面上的点集<math>P = \{p_1, p_2, ..., p_n\}</math>，其Delaunay三角剖分满足以下条件：
* 所有三角形的外接圆（称为'''外接圆'''）内部不包含点集<math>P</math>中的任何其他点（空圆特性）。
* 最大化所有三角形的最小内角，避免出现“狭长”的三角形。

数学表达式为：对于任意三角形<math>\triangle p_i p_j p_k</math>，其外接圆<math>C(\triangle p_i p_j p_k)</math>满足：
<math>\forall p_l \in P \setminus \{p_i, p_j, p_k\}, p_l \notin \text{Int}(C(\triangle p_i p_j p_k))</math>

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

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

== 算法实现 ==
常见的构造算法包括：
* '''增量算法'''（Incremental Algorithm）
* '''分治算法'''（Divide and Conquer）
* '''Bowyer-Watson算法'''（常用动态插入实现）

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

<syntaxhighlight lang="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)
</syntaxhighlight>

'''输出示例：'''
<pre>
三角形顶点索引：
[[3 1 2]
 [3 0 1]
 [3 0 2]]
外接圆圆心坐标：
[[0.5        0.5       ]
 [0.5        0.5       ]
 [0.5        0.5       ]]
</pre>

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

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

== 数学性质证明 ==
Delaunay三角剖分的空圆特性可通过'''局部优化'''（LOP）验证：
* 对于任意两个相邻三角形构成的四边形，若交换对角线后外接圆半径减小，则交换对角线。
* 最终状态满足全局Delaunay条件。

<math>
\forall \triangle ABC \in \mathcal{T}, \nexists P \in P \text{ s.t. } P \in \text{Int}(C(\triangle ABC))
</math>

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

== 常见问题 ==
{{Q&A
|问题1 = 如何处理共线或共圆点？
|答案1 = 实际实现中需添加微小扰动或使用符号计算。
|问题2 = 时间复杂度是多少？
|答案2 = 最优算法为<math>O(n \log n)</math>（如分治法），Bowyer-Watson算法平均<math>O(n^{3/2})</math>。
}}

== 可视化示例 ==
<mermaid>
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
</mermaid>

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:计算几何算法]]