文档介绍：delaunay算法简介
三角剖分原理：
    很多时候我们获取的信息信号都是很离散的信号，比如大地高程测量时的成果测网，纸质各种参数曲线的数字化数据等等，靠大量增加采样点的方法不现实而且会超乎想象的增加处理的计算量，通过趋势个新的三角形，接着判断。如果所有点都在这外接圆外面的话，那么分别以这个三角形的三条边为基础延伸，一直循环到所有点。这样想的话就比上一篇的可实现性好一些了，但是还是不好，没有一点智能判断在里面，每次循环时都要把所有点数据都判断一遍，当数据量特别大时，这种算法简直是要人命，咱们还是不要自己琢磨了，看看专家们是怎么解决这个问题的吧，看看他们的算法！
    Delaunay三角形网的通用算法－逐点插入算法：
    具体算法过程如下：
　　1、遍历所有散点，求出点集的包容盒，得到作为点集凸壳的初始三
角形并放入三角形链表。
　　2、将点集中的散点依次插入，在三角形链表中找出其外接圆包含插入点的三角形（称为该点的影响三角形），删除影响三角形的公共边，将插入点同影响三角形的全部顶点连接起来，从而完成一个点在Delaunay三角形链表中的插入。
　　3、根据优化准则对局部新形成的三角形进行优化（如互换对角线等）。将形成的三角形放入Delaunay三角形链表。
　　4、循环执行上述第2步，直到所有散点插入完毕。
　　上述基于散点的构网算法理论严密、唯一性好，网格满足空圆特性，较为理想。由其逐点插入的构网过程可知，在完成构网后，增加新点时，无需对所有的点进行重新构网，只需对新点的影响三角形范围进行局部联网，且局部联网的方法简单易行。同样，点的删除、移动也可快速动态地进行。但在实际应用当中，这种构网算法不易引入地面的地性线和特征线，当点集较大时构网速度也较慢，如果点集范围是非凸区域或者存在内环，则会产生非法三角形。
   
    为了克服基于散点构网算法的上述缺点，特别是为了提高算法效率，可以对网格中三角形的空圆特性稍加放松，亦即采用基于边的构网方法，其算法简述如下：
　　1、根据已有的地性线和特征线，形成控制边
链表。
　　2、以控制边链表中一线段为基边，从点集中找出同该基边两端点距离和最小的点，以该点为顶点，以该基边为边，向外扩展一个三角形（仅满足空椭圆特性）并放入三角形链表。
　　3、按照上述第2步，对控制边链表所有的线段进行循环，分别向外扩展。
　　4、依次将新形成的三角形的边作为基边，形成新的控制边链表，按照上述第2步，对控制边链表所有的线段进行循环，再次向外扩展，直到所有三角形不能再向外扩展为止。
其它Delaunay优化算法：
    1、Watson的算法
　　Watson的算法一开始就要形成一个包含所有给定点区域的超级三角形。起初，超级三角形是不完全的 (图2, 3, 4 and 5). 然后，通过算法继续递增地在已经存在的三角化格网内插入新的点。查找所有其外接圆包含新的点并且被删除掉给出已知的插入多边形。这样就产生了新的三角网。这个过一直将持续到用完所有的插入点以及所有拥有超级三角形顶点的三角形被删除掉。
这是Delaunay三角化最简单和最广泛应用的算法
　　2、Lawson的算法或对角线交换算法
　　如果将一个点加入到一个已经存在的三角网中，那么就形成