一种生成Delaunay三角网的合成算法_武晓波(2)
时间:2025-07-10
时间:2025-07-10
第1期武晓波等:一种生成Delaunay三角网的合成算法 33
直至子集中的点数不大于4而生成子三角网,然后逐级合并生成最终的三角网。
分治算法是通过递归地执行同一源代码而实现的。因此,当数据量很大时,会产生许多中间层次而占用大量计算机内存,即要求栈空间非常大。如果计算机没有足够的内存,这一方法就无法使用。2.2 逐点插入法
逐点插入方法是由Lawson1977年提出的[5]。它首先建立一个大的三角形或多边形,把所有数据包围进来。然后逐点插入到这个超级三角形或多边形中。同时用Lawson设计的局部优化过程LOP进行优化,以保证生成D-三角网。这一算法后来被许多人作了完善,如Lee和Schachter,Bowyer,Sloan,Macedonio和Pareschi等[6—9]。
逐点插入法虽然容易实现,空间要求不大,但它最大的不足是时间效率极低。2.3 三角网生长法
三角网生长法的操作过程是任选一点,找到与它距离最近的点相连成为一条Delaunay边。按De-launay条件寻找与此边构成Delaunay三角形的第3个顶点。重复进行这一过程直到所有数据都被连接进三角网中。因搜索第3个顶点的方法不同,这一算法有多种实现,如Brassel和Reif,McCullagh和Ross等
[10,11]
3 合成算法
由以上介绍不难看出,目前采用较多的前两类算法各具优势又有局限,同时,它们又具有明显的互
补性。分治算法时间性能好,空间性能差;逐点插入法空间性能好,时间性能差。我们评价一个算法的优劣是看它对时间和空间的消耗,即时空性能的综合表现。因此,就产生了一个非常自然的想法,为何不把它们结合起来,取长补短,从而提高算法的性能呢?
把分治算法与逐点插入法结合起来的具体做法是,以分治算法为主体,当递归分割数据集的过程进行到子集中的数据量小于一个预定值———分割阈值时终止,然后用逐点插入法在子集中生成子三角网。我们把这一新的算法称为合成算法。它的流程图见图1。其中V表示数据集:NV是V的数据量;Nd是分割阈值;NL,NR分别表示两个子集的数据量;TL,TR分别表示在子集中建立的两个子三角网。
。
表1列出了上述3类算法的时间复杂度,即程序中最大的语句执行频度,它是数据量的函数。
表1 几种Delaunay三角网生成算法的时间复杂度[2]Table1 Run-timecomplexitiesforseveralDelaunay
triangulationalgorithms
算法
分
治算法逐点插入法三角网生长法
Lee和Schachlter(1980)Dwyer(1987)Chew(1989)Lawson(1977)
Lee和Schachlter(1980)Bowyer(1981)Watson(1981)Sloan(1987)
Green和Sibson(1978)
一般情况O(NlogN)O(NloglogN)O(NlogN)O(N4/3)O(N3/2)O(N3/2)O(N3/2)O(N5/4)O(N3/2)
3/2
最坏情况O(N2)
O(NlogN)O(NlogN)O(NlogN)O(N2)O(N2)O(N2)O(N2)O(N2)O(N2)O(N)O(N)O(N2)
22
Lewis和Robinson(1978)O(NlogN)
图1 合成算法主程序流程图
Fig.1 Theflowchartofdataprocessinginhybridized
method
Brassel和Reif(1979)O(N)
MaCullagh和Ross(1980)O(N3/2)
3/2Mirante和Weigarten(1982)O(N)
图1表明,为便于分割,首先按升序以横坐标x为主,纵坐标y为辅把数据排序。然后比较NV与