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

34　遥　　感　　学　　报第4卷

Nd,如NV>Nd则分割数据集,否则用逐点插入法生成三角网。合成算法包含3个模块:逐点插入法模块、寻找上下切线模块以及合并模块。3.1　逐点插入法模块

由上述知,逐点插入法有多种实现方法,这里选用Macedonio和Pareschi提出的方法。在这个方法中,把数据中的凸壳作为超级多边形。所谓凸壳即由数据中的凸集顺序相连形成的多边形。逐点插入法模块由以下4个步骤完成。

(1)找出凸壳。这一步用Larkin1991年提出的算法来做[12]。为提高搜索效率,先将数据集划分为矩形栅格。设每个栅格单元内包含的数据为4,则栅格的行列数为NV/4。因具有x,y,x+y,x-y的最大值及最小值的点是凸集中的点[13],把它们按逆时针方向顺序相连作为初始凸壳。然后用递归函数convex(I,J)完成整个凸壳。I,J是凸壳上的相邻点。convex(I,J)找出凸壳上I,J间的另一点K。如果不存在,则返回空。K是与IJ相交的栅格中位于IJ右侧且与IJ距离最大的点,或当IJ右侧无点,但IJ上有点,且位于I,J之间的点。

(2)建立初始三角网。以凸壳上x值最小的点为出发点,按序与其余点相连。

(3)插入点。先找出包含要插入的点P的三角形t,然后连接P与t的3个顶点。

(4)优化。用D-三角网的空心圆性质考查新生成的三角形,如不满足,则调换与相邻三角形所组成的四边形中相连的对角线。向相邻三角形扩展此过程直到满足条件为止。

后两步循环执行直到插入全部数据。3.2　寻找上下切线模块

这个模块找出连接左右两个子三角网的凸壳HL和HR的上切线和下切线。设X是HL中x值最大的点;Y是HR中x值最小的点;Z′是HR上Y逆时针方向的邻点;Z″是HL上X顺时针方向的邻点。寻找HL和HR的下切线过程由两个循不完成。(1)如Z′位于XY右侧,则Z′成为新的Y,Y逆时针方向的邻点成为新的Z′,否则退出。(2)如Z″位于XY右侧,则Z″成为新的X,X逆时针方向的邻点成为新的Z″,否则退出。用类似的方法可以生成HL和HR的3.3　合并模块

子三角网TL和TR的合并由一个循环完成。以HL和HR的下切线为起始基线,分别在TL和TR中找出与它构成Delaunay三角形的第3个顶点L1和R1,在这两个三角形中选择外接圆半径小的连接到三角网中。新生成的边作为新的基线继续这个过程,当基线成为HL和HR的上切线时终止。

在寻找上下切线模块和合并模块中,要频繁用到两个函数pred(Vi,Vj)和succ(Vi,Vj)。pred(Vi,Vj)是在包含公共端点Vi的一簇线段中,得到与边ViVj顺时针方向邻边的另一个端点。succ(Vi,Vj)相反,是得到与边ViVj逆时针方向邻边的另一个端点。

4　实例测试与结论

我们用MicrosoftC实现了合成算法,并用一个有2533个点的数据进行了测试。所用平台是586/90微机,内存16MB。为与分治算法及逐点插入法比较,由小到大取多个分割阈值进行测试。分割阈值越小,算法愈接近于分治算法,这里以10代之。因为当取更小的值时,子集中的点有共线现象。

表2　合成算法在不同分割阈下运行所需时间Table2　HybridizedAlgorithm'sperformance

undervarioussplitthreshold

分割阈1050100200500100020003000

运行时间/s35(分治算法)

252322262833

50(逐点插入法)

测试结果如表2。合成算法的时间效率远优于逐点插入法,在大多数情况下,它也好于分治算法。当分割阈值约为数据量的十分之一时,它的效率最高。

参考文献(References)

[].areas[]y