三角剖分

集的一种三角剖分，因而由点集的三角剖分可以计算Voronoi图；最远点意义下Voronoi图的对偶图是点集凸壳（凸多边形）的一种三角剖分，由点集凸壳的某种三角剖分可以求得Voronoi图（只要该Voronoi图存在）。下面介绍集中平面点集三角剖分的几种算法。

2平面点集三角剖分算法及比较

2.1平面点集三角剖分的贪心算法

平面点集三角剖分算法的主要思想是对两点间的距离按照长短进行排序，生成长度不同线段，从小到大依次从这些线段中提取出三角剖分边，知道变数达到剖分要求。最终使剖分的边长度达到最小。

此算法虽然简单并且容易实现，但是其时间复杂度和空间复杂度都比较高，剖分的总体效率不高。

2.2渐次插入的三角剖分算法

渐次插入算法是对现有的Delaunay三角剖分插入新的点，当插入一个新点后，Delaunay三角网格将重新划分。初始三角网包含所有的数据点，可以未超三角形。算法如下：

步骤1定义包含所有数据点并作为初始Delaunay三角形的超三角形的顶点； 步骤2从数据中取出一点P加入到三角网中；

步骤3搜寻包含点P的三角形，将P与次三角形的三个顶点相连，形成三个三角形； 步骤4应用Lawson Lop从里到外更新所有生成的三角形； 步骤5重复步骤2至步骤4，直到所有点处理完毕； 步骤6删除所有包含一个或多个超三角形顶点的三角形。 2.3 Tsung-pao Fang和Les.pieg的Delaunay三角剖分算法

Tsung-pao Fang和Les.pieg的Delaunay三角剖分算法是一种较快的算法，这里简单说一下它的算法思想，就是使用一种单元格的网格构成形成三角形，然后搜寻边界和最近的点，通过凸壳旋转生成三角形。 2.4几种算法的比较

1.贪心算法的时间复杂性为O(n3)。

2.渐次插入三角网算法对约束情况下有一定的限制。

3.Tsung-pao Fang和Les.pieg的Delaunay三角剖分算法的时间复杂性为O(n)为线性的时间复杂度，同时生成的Delaunay三角形比较好，但该算法容易出现退化现象。

3一种新的平面点集三角剖分的算法

3.1算法的基本思想

本人在现在平面点集三角剖分算法基础上，研究出一个新的平面点集Delaunay三角剖