一种生成Delaunay三角网的合成算法_武晓波(2)

第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与