1、生成生成Del aunay三角网的合成算法三角网的合成算法 一种生成一种生成Delaunay三角网的合成算法三角网的合成算法 2000武晓波，王世新，肖春生武晓波，王世新，肖春生 生成生成Del aunay三角网的快速合成算法三角网的快速合成算法 吴宇吴宇晓，张登荣晓，张登荣 2004 经过经过20多年的研究，自动生成多年的研究，自动生成Delaunay三角网三角网的算法已趋于成熟。它们基本上可分为的算法已趋于成熟。它们基本上可分为分治算分治算法逐点插入法、三角网生长法法逐点插入法、三角网生长法等等3类。其中前类。其中前两类较第两类较第3类在应用户上更加广泛。但即使这类在应用户上更加广泛。但即
2、使这两类算法也分别存在着时间和空间效率上的缺两类算法也分别存在着时间和空间效率上的缺陷，使它们的应用受到了一定的限制。陷，使它们的应用受到了一定的限制。武晓武晓波波,2000提出了一个融以上两类算法优点于一提出了一个融以上两类算法优点于一体，兼顾空间与时间性能的合成算法。经测试，体，兼顾空间与时间性能的合成算法。经测试，它的运算效率大大高于逐点插入法，在大多数它的运算效率大大高于逐点插入法，在大多数情况下，也高于分治算法，在分割阈值约为总情况下，也高于分治算法，在分割阈值约为总数据量的十分之一时，效率最高。数据量的十分之一时，效率最高。 1引言分治算法和逐点插入法由于易于实现，是当前应用较广的
3、两类算法。这两类算法所采用的实现方法决定了它们存在着明显的局限性，分治算法需要大量的内存，逐点插入法运行速度极慢。当数据量较大或计算机性能较差时，它们的使用都将遇到困难。 武晓波武晓波,2000提出了一个成功地解决了上述问题的合成算法。该算法将逐点插入法嵌入到分治算法中，使它们优势互补，弥补了各自的缺陷。经过一个有2533个点数据测试，表明合成算法的运算效率大大高于逐点插入法，在大多数情况下也高于分治算法 2己有算法介绍己有算法介绍2. 1分治算法分治算法2. 2逐点插入法逐点插入法2. 3三角网生长法三角网生长法 3合成算法合成算法 由以上介绍不难看出，目前采用较多的前两由以上介绍不难看出，
4、目前采用较多的前两类算法各具优势又有局限，同时，它们又具有类算法各具优势又有局限，同时，它们又具有明显的互补性。明显的互补性。分治算法时间性能好，空间性分治算法时间性能好，空间性能差能差;逐点插入法空间性能好，时间性能差逐点插入法空间性能好，时间性能差。我们评价一个算法的优劣是看它对时间和空间我们评价一个算法的优劣是看它对时间和空间的消耗，即时空性能的综合表现。因此，就产的消耗，即时空性能的综合表现。因此，就产生了一个非常自然的想法，为何不把它们结合生了一个非常自然的想法，为何不把它们结合起来，取长补短，从而提高算法的性能呢起来，取长补短，从而提高算法的性能呢? 把分治算法与逐点插入法结合起来
5、的具体把分治算法与逐点插入法结合起来的具体做法是，以分治算法为主体，当递归分割做法是，以分治算法为主体，当递归分割数据集的过程进行到子集中的数据量小于数据集的过程进行到子集中的数据量小于一个预定值一个预定值分割阈值时终止，然后用逐分割阈值时终止，然后用逐点插入法在子集中生成子三角网。我们把点插入法在子集中生成子三角网。我们把这一新的算法称为这一新的算法称为合成算法合成算法。它的流程图。它的流程图见图见图1。其中。其中v表示数据集表示数据集:Nv是是V的数据的数据量量;Nd是分割阈值是分割阈值;Nl, Nr分别表示两个子集分别表示两个子集的数据量的数据量;Tl,Tr分别表示在子集中建立的两分别表
6、示在子集中建立的两个子三角网。个子三角网。 合成算法结合了传统的递归分割法和逐点插入法的优点，兼顾空间和时间性能然而，该算法不可避免地继承了两种传统算法的不足，在执行效率上受到限制，为了解决执行效率问题，吴宇晓，张登荣 2004提出了快速合成算法，对合成算进行了改进和优化。该算法基于面积坐标的点定位算法和简化的高效空外接圆判断算法，从而大大提高算法的整体执行效率;同时充分考虑平面点集的任意性，适用于对任意平面点集构建Delaunay三角网。 4算法的基本模块算法的基本模块 为了便于分割，在执行各模块之前，首为了便于分割，在执行各模块之前，首先要对初始点集按升序以先要对初始点集按升序以x坐标为主
7、，坐标为主，y坐坐标为辅进行排列，确保子三角网不相互叠标为辅进行排列，确保子三角网不相互叠置置. 4. 1格雷厄姆法计算凸壳格雷厄姆法计算凸壳 4. 2初始三角网的建立与修正初始三角网的建立与修正 以凸壳上以凸壳上y值最小的点值最小的点(设为点设为点P1)为出发为出发点，按序与凸壳上其余的点相连点，按序与凸壳上其余的点相连(如图如图3( b)所示所示). 需要注意的是，点集是任意离散的，出发点需要注意的是，点集是任意离散的，出发点P1可能与多点共线可能与多点共线.如图如图3 ( a)所示，点所示，点P1一一P5共共线，而事实上点线，而事实上点P2一一P4不参加构成初始三角网，不参加构成初始三角
8、网，因此，需要在建立初始三角网前对凸壳进行修因此，需要在建立初始三角网前对凸壳进行修正。如果存在点正。如果存在点P3, P4,.Pk(2 kn)，与，与P1P2共共线，则必须删去点线，则必须删去点P2, P3, ., Pk-1，并由，并由P1Pk代替代替P1P2成为初始边成为初始边.同样，如果存在点同样，如果存在点Pk,Pk+1.,Pn-1(2 k0, L 20, L 30; 若P在三角形外，则至少有一个面积坐标小于零.如图4( b)所示，P在三角形P2P3边外侧，则 L10, L 30;若P在三角形边上(这儿排除P与三角形顶点重合的情况)，那么必有值为0的面积坐标.如图4c所示，P在三角形P
9、2P3边上，则有L1=0, L 20, L 30; 综上分析可知，综上分析可知，正是小于正是小于0的面积坐标指明的面积坐标指明了目标三角形的方向了目标三角形的方向.在建立了三角形拓扑在建立了三角形拓扑关系的三角网中，利用面积坐标的这一特关系的三角网中，利用面积坐标的这一特性，可很快查到包含点所在的三角形或所性，可很快查到包含点所在的三角形或所处的三角边处的三角边. 基于面积坐标的定位过程如图基于面积坐标的定位过程如图5所示所示.设三角形设三角形P1P2P3为搜索的起点，计算点为搜索的起点，计算点P的面积坐标可知的面积坐标可知L10, L 20, L 30都大于都大于0，则点，则点P在三角形在三
10、角形P7P6P8内内;若若Li(i=1，2, 3)=0，则点，则点P在在Li所对应的边上所对应的边上. 4.3.2点定位后的三角网修改点定位后的三角网修改 由于所有待插入点必在凸壳内，所以待由于所有待插入点必在凸壳内，所以待插入点必在三角形内或三角边上插入点必在三角形内或三角边上.跟据点与跟据点与所处三角形的关系，点插入三角网的情况所处三角形的关系，点插入三角网的情况及相应的三角网修改方法分为如下及相应的三角网修改方法分为如下3种情况种情况(见图见图6) . 插入点在三角形内.如图6( a)所示，待插入点P在三角形P1P2P3内.此时，将点P与此三角形的三个顶点相连，形成3个三角形. 待插入点
11、在非凸壳边上.由于所在边不是凸壳边，此边必是两个三角形的公共边.如图6( b)所示，待插入点P在边P2P3上，P2P3是三角形P1P2P3和P2P3P4的公共边.此时，点P与P2P3两个三角形的对应点P1和P4相连，形成4个三角形. 待插入点在凸壳边上. 凸壳边有且仅有一个相邻三角形，因此图6(c)中，只需将点P与P2P3惟一的相邻三角形P1P2P3的对应点P1相连，形成两个三角形. 4.4 LOP优化 一旦三角网被修改，必须进行LOP优化.使用Delaunay空外接圆准则考查新生成三角形，如不满足，则调换与相邻三角形所组成的凸四边形的对角线.若对角线发生交换，则继续向相邻三角形扩展此过程，直
12、至满足空外接圆准则或到达三角网边界. LOP优化时，首要的问题是对新增三角形和其相邻三角形所组成的凸四边形进行空外接圆检测.在算法中，空外接圆检测具有累计性，当数据量较大时，其在整个程序执行中所占用的时间不容忽视.该检测过程是一个数值分析与计算过程，因而应在计算稳定可靠的前提下，尽量减少计算次数和低效的函数，从而提高执行效率.下面提出了一个简化的空外接圆检测算法. 如图7所示，新增三角形PP3P2与三角形P1P2P3相邻，组成凸四边形，且有公共边P2P3.当a a时，点P在三角形P1P2P3的外接圆内.由于a+B=180，故通过比较cos a和cosB的大小来判断点P与三角形P1P2P3的外接
13、圆的关系. 若若 点点P在三角形在三角形P1P2P3的的外接圆外外接圆外; 若若 点点P在三角形在三角形P1P2P3的的外接圆上外接圆上; 若若 点点P在三角形在三角形P1P2P3的的外接圆内外接圆内. 如点P在外接圆内，则交换凸四边形的对角线(如图8 ( a)所示).当点在外接圆上时，则比较凸四边形两个对角线，保留较短的那条(如图8(b)所示).若凸四边形的对角线发生交换，应继续向相邻三角形扩展优化，直至被检测三角形满足空外接圆准则或到达三角网边界. 4.5上下切线的查找算法上下切线的查找算法 该模块找出连接相邻两个子三角网的外该模块找出连接相邻两个子三角网的外凸壳的上切线和下切线凸壳的上切
14、线和下切线.设设SL, SR分别表示左分别表示左右两个凸壳。右两个凸壳。 首先在左凸壳首先在左凸壳SL上任取一凸壳点，按上述上任取一凸壳点，按上述三角形面积判定法找出右凸壳上的第一条三角形面积判定法找出右凸壳上的第一条通视边的第一个凸壳点。若无通视边，则通视边的第一个凸壳点。若无通视边，则在在SL上顺时针取下一点再作搜索判断，直上顺时针取下一点再作搜索判断，直到找到通视边。到找到通视边。 以右凸壳SR上刚找到的点仍按面积判定法搜索左凸壳SL上最后一条通视边的第二个凸壳点。 重复以上两个步骤，在SL和SR上循环搜索，直到从SL上的凸壳点不再能找到SR上的通视边，目从SR上的凸壳点也不再能找到SL
15、上的通视边。 此时，连接在SL和SR上分别找到的最后的凸壳点，所连线即为左右凸壳的下底线。 2. 6子网合并 找到左右两个了三角网的下底线后如图(ac)中的，就可从下底线ac开始向上分别在SL上找到a的上一个凸壳点b，在SR上找到c的下一个凸壳点d。对四边形acdb通过LOP优化新生两个三角形 abc和bdc。 将新生三角形在左右两个了三角网中分别和与其共边的三角形进行优化处理，并按照共边即需优化的原则，一直优化到底，直到己是最优化为止。 再以bd为底边，重复上述步骤，分别向上找点生成新的优化三角形，直到出现三角形的面积值为正值时停止。就完成了两子三角网的合并。 3算法测试 4结语 本文提出了经过优化改进的快速合成算法.该算法不但继承了合成算法的优点，可根据实际的点集数目和运算环境，调节阀值，从而动态平衡时空性能;而且时间效率和稳定性大大提高，既有很高的执行效率，又适用于任意平面点集分布状况.
