Delaunay三角网生成算法

   Delaunay三角剖分分为直接三角剖分和间接三角剖分。间接三角剖分首先计算为Voronoi图,然后由Voronoi图产生Delaunay三角网。这种方法的算法复杂、内存开销大、效率低,现今很少使用。直接Delaunay三角剖分是利用离散点按照空外接圆或者最大最小内角性质,直接生成Delaunay三角网,是目前基于离散点三角剖分的主流算法。
  Delaunay三角剖分分成三类：分而治之算法、三角网增长算法和逐点插入算法。

一、分而治之算法

  分而治之算法最早是1975年由Shamos和Hoey提出的，Lewis和Rovinson在1978年利用该方法进行了三角网的剖分，随后Lee和Schachter、Dwyer等对他们的算法进行了改进和优化。
  分而治之算法的思路是将复杂问题简单化，首先将数据点分割成包含少量点的子集，如一个子集中包括三个、四个点，然后每个子集进行三角剖分，并用局部优化算法（LOP）进行优化，保证三角剖分为Delaunay三角网，最后是对每个子集的三角剖分进行合并，形成最终的整体三角网。不同的实现方法可有不同的点集划分方法、子网生成方法及合并方法。Lee和Schachter提出了分而治之的经典算法，其基本步骤如下：

1. 把点集$V$以横坐标为主，纵坐标为辅按升序排序，即数据点之间满足条件：$(x_i,y_i)<=(x_{i+1},y_{i+1})$；
2. 把点集$V$分为近似相等的两个子集$V_L$和$V_R$；
3. 在$V_L$和$V_R$中生成三角网；
4. 使用局部优化算法，使之成为Delaunay三角网；
5. 找出连接$V_L$和$V_R$中两个凸壳的底线和顶线；
6. 由底线至顶线合并$V_L$和$V_R$中两个三角网；
7. 结束。

  该算法的时间复杂度为$(NlogN)$，其中$N$为数据点数，因此该算法执行时间效率高，但在$V_L$和$V_R$中生成三角网时，采用了递归运算，需占用较大的系统内存。

二、三角网生长算法

  三角网生长算法最早由Green和Sibson在V图中实现，稍后Brassel和Teif也发表了类似的算法。分为收缩生长算法和扩张生长算法，收缩生长算法是先生成凸壳，并以凸壳为源头，逐步缩小以形成整个三角网。收缩生长算法与数据点的分布密度有关，实际情况比较复杂。扩张生成算法与收缩算法过程刚好相反，算法是从一个三角形开始向外层扩展,最终形成覆盖整个区域的三角网，是常用的三角网生长算法。
  扩张生长算法的思想是先找出点集中最近两点连接成一条边，按照Delaunay三角网构成原则找出第三点，将这三点连接成初始三角形，再以该三角形的每一条边为基线扩展连接相邻离散点，组成新三角形，初始三角形的三边处理之后，继续以新三角形的边连接其他离散点，直到所有的离散点均包含在三角网中。该算法的基本步骤：

1. 在区域内所有离散点任取一点作为初始三角形的第一个顶点；
2. 找距离第一个顶点最近的点，作为初始三角形的第二个顶点，两点相连生成初始基线；
3. 找出距离初始基线中点最近且不和已有两点在一条直线上的点作为初始三角形的第三个顶点，三点连接成三角形，即为初始三角形；
4. 三角形的两条新边作为新的基线；
5. 重复步骤3、4直到所有基线处理完毕。

  该算法的时间复杂度在一般情况下为$O(N^{3/2})$,最坏情况下达到$O(N^2)$。因此该算法的时间效率低,优点是占用内存空间较小。在该算法的基础上有许多的改进算法,其改进点主要集中在“第三点”的搜索和三角形重复的判断上。

三、逐点插入算法

  逐点插入算法的思想最早由Lawson（1977）提出，随后Lee和Schachter（1980）、Bowyer（1981）、Watson（1981）、Tsai（1993）等先后对其进行改进，是一种动态的构网方式。
  逐点插入算法的思路是将未处理的点加入到己经存在的Delaunay三角网中，然后判断点所在的三角形，如果点在三角形内，连接点与三角形的各顶点，利用三角剖分准则，找出影响区域，删除影响区域中的边，对影响区域利用三角剖分准则重新构网，直到区域中所有的点都加入到三角网中。该算法的基本步骤如下：

1. 首先定义一个包含所有数据点的初始多边形，即包含所有数据点的凸闭包；
2. 在凸闭包中构建初始Delaunay三角网；
3. 从内部数据点中取出一点加入到三角网中；
4. 搜寻包含该点的三角形，将该点与此三角形的三个顶点相连，形成三个三角形；
5. 利用Delaunay三角网的剖分准则，找出影响区域，从里到外更新所有生成的三角形；
6. 重复步骤3、4、5直到处理完点集中所有点。

  该算法一般情况下时间复杂度为$O(N^{3/2})$，最坏情况下达到$O(N^2)$。该算法的时间效率低，优点是算法思路较简单，占用内存空间较小，空间性能较好。
通常,分而治之算法的效率是最高的，但是当数据量比较大，分块比较多时，块之间的合并算法复杂，且花时也多，并且递归执行，内存消耗大；三角网生长算法和逐点插入法的执行效率差不多，但是在构网的过程中逐点插入法能保持较好的空间特性。

四、约束Delaunay三角网

1、方法一

1、原始点云

2、构网结果

1、方法二

1、原始点云

2、普通Delaunay

3、约束Delaunay