生成Delaunay三角网的合成算法•一种生成Delaunay三角网的合成算法2000武晓波，王世新，肖春生•生成Delaunay三角网的快速合成算法吴宇晓，张登荣2004•经过20多年的研究，自动生成Delaunay三角网的算法已趋于成熟。它们基本上可分为分治算法逐点插入法、三角网生长法等3类。其中前两类较第3类在应用户上更加广泛。但即使这两类算法也分别存在着时间和空间效率上的缺陷，使它们的应用受到了一定的限制。武晓波,2000提出了一个融以上两类算法优点于一体，兼顾空间与时间性能的合成算法。经测试，它的运算效率大大高于逐点插入法，在大多数情况下，也高于分治算法，在分割阈值约为总数据量的十分之一时，效率最高。•1引言•分治算法和逐点插入法由于易于实现，是当前应用较广的两类算法。这两类算法所采用的实现方法决定了它们存在着明显的局限性，分治算法需要大量的内存，逐点插入法运行速度极慢。当数据量较大或计算机性能较差时，它们的使用都将遇到困难。•武晓波,2000提出了一个成功地解决了上述问题的合成算法。该算法将逐点插入法嵌入到分治算法中，使它们优势互补，弥补了各自的缺陷。经过一个有2533个点数据测试，表明合成算法的运算效率大大高于逐点插入法，在大多数情况下也高于分治算法•2己有算法介绍2.1分治算法2.2逐点插入法2.3三角网生长法•3合成算法•由以上介绍不难看出，目前采用较多的前两类算法各具优势又有局限，同时，它们又具有明显的互补性。分治算法时间性能好，空间性能差;逐点插入法空间性能好，时间性能差。我们评价一个算法的优劣是看它对时间和空间的消耗，即时空性能的综合表现。因此，就产生了一个非常自然的想法，为何不把它们结合起来，取长补短，从而提高算法的性能呢?•把分治算法与逐点插入法结合起来的具体做法是，以分治算法为主体，当递归分割数据集的过程进行到子集中的数据量小于一个预定值——分割阈值时终止，然后用逐点插入法在子集中生成子三角网。我们把这一新的算法称为合成算法。它的流程图见图1。其中v表示数据集:Nv是V的数据量;Nd是分割阈值;Nl,Nr分别表示两个子集的数据量;Tl,Tr分别表示在子集中建立的两个子三角网。•合成算法结合了传统的递归分割法和逐点插入法的优点，兼顾空间和时间性能然而，该算法不可避免地继承了两种传统算法的不足，在执行效率上受到限制，为了解决执行效率问题，[吴宇晓，张登荣2004]提出了快速合成算法，对合成算进行了改进和优化。该算法基于面积坐标的点定位算法和简化的高效空外接圆判断算法，从而大大提高算法的整体执行效率;同时充分考虑平面点集的任意性，适用于对任意平面点集构建Delaunay三角网。•4算法的基本模块•为了便于分割，在执行各模块之前，首先要对初始点集按升序以x坐标为主，y坐标为辅进行排列，确保子三角网不相互叠置.•4.1格雷厄姆法计算凸壳•4.2初始三角网的建立与修正•以凸壳上y值最小的点(设为点P1)为出发点，按序与凸壳上其余的点相连(如图3(b)所示).••需要注意的是，点集是任意离散的，出发点P1可能与多点共线.如图3(a)所示，点P1一P5共线，而事实上点P2一P4不参加构成初始三角网，因此，需要在建立初始三角网前对凸壳进行修正。如果存在点P3,P4,...Pk(20,L2>0,L3>0;若P在...
