delaunay算法简介.doc

三角剖分原理： 很多时候我们获取的信息信号都是很离散的信号，比如大地高程测量时的成果测网，纸质各种参数曲线的数字化数据等等，靠大量增加采样点的方法不现实而且会超乎想象的增加处理的计算量，通过趋势分析插值的方法可以使得数字化的模型更逼近原始模型，但是终归于这些离散数据是要通过一种方式在电脑中成为一种整体数据，不管是2d还是3d。 三角剖分最终是要将离散的数据通过连接成很多三角形来达到面化或体化的目的（四面体其实就是四个三角形）。那么我们是不是可以随便来连三角形呢？当然不行了，咱们连成的面或体要与离散化前的原始模型越接近越好。 怎么样才能使咱们连成的面或体要与离散化前的原始模型越接近越好呢？一般来说每个离散点都有一定的作用范围，那么我们在连三角形是不是就要想到，尽量让每个三角形内的三个点相对来说隔得近一点。首先有两个原则： 1 产生的三角形不相重叠。（如果重叠，那么其中的一个三角形岂不是多余了） 2 不产生新的顶点。（如果产生新的顶点了，那么这个顶点的值我们可以确认它符合于原始模型吗？），不过这条原则很难完全保证不产生。然后有两个问题要解决： 1 面化或体化时是否要考虑到边界的问题？也就是是否考虑边界离散点的凹凸判断，如果要考虑的话，所有边界点依次相连就行，如果不用考虑的话，所有凸点边界点依次相连就行。一般来说是要考虑的。 2 面化或体化时是否要考虑到面内或体内空洞的问题？也就是是否考虑内部空白区的判断，如果要考虑的话，内部空白区的边界点要跟问题1同等考虑。 再次我们看一下经典的三角剖分方法： 谈到三角剖分，这个名字你不得不熟悉，这就是经典-Delaunay三角剖分。Delaunay三角剖分具有四个特有的性质：（1）保证最邻近的点构成三角形，即三角形的边长之和尽量最小，且每个Delaunay三角形的外接圆不包含面内的其他任何点，称之为Delaunay三角网的空外圆性质。这个特征已经作为创建Delaunay三角网的一项判别标准；（2）它的另一个性质最大最小角性质：在由点集中所能形成的三角网中，Delaunay三角网中三角形的最小内角尽量最大，即三角形尽量接近等边三角形，从这个意义上讲，Delaunay三角网是“最接近于规则化的”的三角网。（3）Delaunay三角网是唯一的。（4）三角网的外边界构成了点集的凸多边形“外壳”； 大概的道理我们是懂了，但是给你任意一些点，你采用什么思路将之三角剖分呢？先易后难，我们可以先从四个点逆时针排列ABCD（任意三个点不在一条直线上）来判断，显而易见只有两种剖分方式（ABC & CDA）或者（DAB & BCD），如果我们按照三角网的空外圆性质来判断的话，问题化为：第一种剖分方式的要求：点D在三角形ABC的外接圆的外部 & 点B在三角形CDA的外接圆的外部第二种剖分方式的要求：点C在三角形ABC的外接圆的外部 & 点A在三角形CDA的外接圆的外部上面的条件哪种方式成立，那么哪种方式就是我们要求的三角剖分方式。如果按照上一篇的思路，如果点数稍微一多，那么我们在三角剖分的时候就会遇到大量的判断和计算，看来我们的思路有一定问题，虽然是按照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的算法或 对角线交换算法如果将一个点加入到一个已经存在的三角网中，那么就形成了所有新的三角形的外接圆。如果任何 相邻的区域位于任何三角形的外接圆内，那么用三角形和它的相邻的区域便可形成一个四边形。四边形的对角线被转换为一个新的三角网。这个过程一直持续到不再有的错误三角形和不在需要变换。3、限制性的Delaunay三角化（Constrained Delaunay Triangulation） (CDT) 如果指定了平面的点集以及一系列不交错的边缘，那么CDT 将产生如下的网格：a、在三角网中包含了所有给定的边缘 b、尽可能使其与Delaunay三角网相近 这种算法已经在N个给定点的区域在O(NlogN) 的时间复杂性下经过了测试。如果指定点集和不交叉边缘，那么给定点集的CDT具有所有新的边缘所具有的特性，即存在一个这样的圆，a、边缘的终点都落在圆内b、如果有任一个节点在圆内，那么至少边缘的一个节点是不可见的，例如，如果线是从点到边缘的两个节点来画的，那么至少有一条直线会与网格的边缘相交。因此，如果没有指定边缘，那么CDT与Delaunay是一样的。CDT是一种分而取之的方法，因为给定的数据是依据任意的尺寸来筛选的，并且将区域划分成若干带。这个过程将一直重复，直到得到整个区域的CDT为止。4、扫描线算法（Sweepline algorithm）在Voronoi多边形中，扫描线被定义为一条移动的水平线与Voronoi 边界的交点。外接圆是通过找出连接节点的直线的三条平分线的交点来定位的。但是这样得到Voronoi 多边形不是太有力。一对一的几何变