三角化算法

三角化算法也称为点集三角剖分，是计算机图形学领域的一个基本问题。点集三角剖

分指的是将一个给定的平面点集分割成一组无重叠的三角形，使得这些三角形的顶点就是

给定的平面点集中的某些点，每个点都是三角形的顶点之一，并且没有三角形的内部包含

任何给定点。

在三维空间中，点集三角剖分也就是将给定的平面点集转化为一个三角网格模型，这

个模型通常用于计算机图形学中的三维建模和动画中。

三角化算法可以分为两个大类：划分和增量类。划分类算法将给定点集分割成若干个

不相交的三角形，如分治算法和从一组凸包出发的分割算法。而增量类算法则是分别将所

有点逐一添加到一个空网格上，每次加入一个新点都会导致一些现有边的拆分和新的边的

生成，这样逐渐形成了一个完整的三角网格模型。

下面我们将简要介绍三角化算法中常用的几种算法。

一、

 Delaunay 

三角剖分算法

    Delaunay 

三角剖分是最有名的三角剖分算法之一，其在科技、工程和数学等领域都

有广泛应用。在地图、物理、化学、生物等科学领域，

Delaunay 

三角剖分也有重要的应

用。

    Delaunay 

三角剖分是指将一个平面点集逐个连接成一个个的三角形，使得所有连接

线的延长线互不交叉，并且所有三角形都不包含更多的点。如果把所有连接线画出来，然

后连接它们的中垂线，就会得到唯一的一个包含所有输入点的圆。这个圆，就是

Delaunay 

三角剖分的特殊圆，被称为

 Delaunay 

圆。

    Delaunay 

三角剖分算法的基本思路是，逐个加入输入点，然后使其尽可能地满足

Delaunay 

三角剖分的规则。加入一个新点后，需要检查这个点所涉及的所有三角形，看

是否需要将它替换为三角形的圆内任意的一个点，以更新

 Delaunay 

三角剖分。这个过程

可以通过一种叫作优先队列的数据结构以较高的效率完成。

在这个过程中，需要确保新增的约束线不会导致新的非

 Delaunay 

点出现。为了实现

这个目标，算法维护一个

 Delaunay 

网格的定义和性质，即对角线两端端点的圆不能包含

第三个非共线点，同时在每次加入约束线时，必须对网格进行局部更新并维护

 Delaunay 

定义的正确性。

三、

 Ear Clipping 

算法