Delaunay三角剖分算法

Delaunay三角剖分是计算机图形学中一种常见的算法，用于将二维平面上的点集进行三角剖分。其基本思想是通过计算每个三角形外接圆的空圆性质，将点集划分为不重叠的三角形。

Delaunay三角剖分的优势在于，该算法所得到的三角形具有最大化的最小角度性质，这对于很多计算机图形学应用来说是非常重要的。Delaunay三角剖分也被广泛应用于地理信息系统、CAD和有限元分析等领域。

该算法的具体实现方式有多种，其中比较常见的包括增量法、分治法和翻转法等。增量法是最常用的一种实现方式，其基本思想是从一个空三角形开始，逐步将点集中的点加入到三角剖分中，保证每次加入点后，所得到的三角剖分仍然满足Delaunay性质。