基于合成算法的Delaunay三角网生成改进算法

潘丽丽,孙玉秋

(长江大学信息与数学学院,湖北荆州434023)

不规则三角网能够精确的表示复杂的地形。Delaunay三角网因其在所有可能的三角网中表现最为出色而被用于不规则三角网的生成。被人们广泛采用的Delaunay三角网生成算法有分治法与逐点插入法,这2种算法各有优劣,随之出现了综合2种算法的合成算法。合成算法虽然提高了执行效率,但并没有很好的解决其中的一些 “瓶颈”问题。因此,如何改进现有算法从而提高算法的执行效率成为必须要解决的另一个问题。为此,笔者基于合成算法对子模块中的关键步骤进行改进,提高算法的性能,简化算法的实现。

1 基本概念及性质

Voronoi图 (以下简称V图),又叫泰森多边形或Dirichlet图,它是由一组连接两邻点直线的垂直平分线组成的连续多边形。N个在平面上有区别的点,按照最邻近原则划分平面;每个点与它的最近邻区域相关联。Delaunay三角网是由与相邻Voronoi多边形共享一条边的相关点连接而成的三角形。Delaunay三角形的外接圆圆心是与三角形相关的Voronoi多边形的一个顶点。Voronoi三角网是Delaunay图的偶图。

性质1(空外接圆性质) 在由点集V生成的Delaunay三角网中,每个三角网的外接圆均不包含该点集的其他任意点。

性质2(最大最小角度性质) 在由点集V生成的Delaunay三角网中,所有三角形中的最小角度是最大的,即在生成的三角形网格中,各三角形的最小内角和为最大。

性质3(唯一性) 不论从区域何处开始构网,最终都将得到一致的结果。

2 合成算法

合成算法[1,2]的基本思想是将逐点插入法植入到分治算法中,即以分治算法为主体,当递归分割数据集的过程进行到子集中的数据量小于一个预定值时,用逐点插入法在子集中生成三角网,以达到互相取长补短,以体现它们的综合优势,从而达到较好的时空性能的效果,合成算法包含3个模块:逐点插入法模块、寻找上下切线模块以及合并模块。

1)逐点插入模块 ①找出凸壳;②建立初始三角网;③插入点;④优化。

2)寻找上下切线模块 这个模块找出连接左右2个子三角网的凸壳HL和H R的上切线和下切线。

3)合并模块 子三角网TL和TR的合并由一个循环完成。

3 改进算法

改进的合成算法主要分为逐点插入模块和合并模块,笔者在插入点的定位问题上以及凸壳生成问题上,改进了传统的算法,以提高算法的整体执行效率。

1)凸壳的生成与初始化三角网 原合成算法采用Larkin的凸壳生成算法[3]生成凸壳,这需要判断点的位置等操作,在点的数量大的时候,执行效率不高。凸壳的生成算法中较为经典的是格雷厄姆法[4]。

构建凸壳的算法需要满足的2个条件:实现简单,无需大量预处理工作;不影响下一步的点插入步骤。因此,笔者在格雷厄姆方法的基础上改进以更好的解决凸壳快速生成问题。

①首先对点集预处理,对其进行排序,用点(max(X),max(Y))、(min(X),min(Y))、(max(X),min(Y))和(min(X),max(Y))4个点所围矩形来构成凸壳,这样就生成了一个包含所有点的简单凸壳(如图1所示)。②连接含有max(X)、max(Y)、min(X)和min(Y)4个值的点并对所构成的多边形初始三角网(如图2所示)。③在三角网生成后要将这4个点删除,同时删除含有这4个点的三角形。图3为三角网生成后删除4个顶点前的三角网图;图4为删除顶点后的三角网图。

图1 凸壳

图2 初始三角形

图3 删除矩形顶点前三角网

图4 删除矩形顶点后三角网

2)点的快速定位 逐点插入的过程就是对点的定位循环过程,也就是查找点所在三角形的过程。因此,改进点的定位过程可以提高算法的效率。判断点是否在三角形内,一般的做法是扫描整个或局部三角网,利用点在多边形中原理判断计算。当三角形数目较多时是一个费时的过程。因此,点的定位算法为逐点插入过程的关键步骤。判断点是否在多边形内,常用的有射线法、转角法[5]以及适用于三角网的快速方向定位法[6]。对于点的定位方法需要遵循2个原则:实现简单和避免复杂运算。因此,笔者利用点在三角形内的特点来解决。

首先求出三角形顶点X、Y坐标的最大及最小值,并构成矩形,判断点是否在矩形中,若不在矩形中,则不在三角形中。若在矩形中,则作下面的判断。连接点A与P,B与P,C与P,得出3向量:

为了判断点与三角形的位置关系,定义:

图5 点在边上

图6 点在三角形外

图7 点在三角形内

4 结 语

在对Delaunay三角网生成算法进行深入研究的基础上,提出了一种基于合成算法的改进的Delaunay三角网生成算法,算法改进了原合成算法在凸壳生成过程以及的快速定位的不足,更好的发挥了分治算法与逐点插入算法合并后的优势,充分发挥了其兼顾时间、空间的特性,较原合成算法在速度和效率上所有提高。

[1]武晓波,王世新,肖春生.Delaunay三角网的生成算法研究 [J].测绘学报,1999,28(1):28-35.

[2]武晓波,王世新,肖春生.一种生成Delaunay三角网的合成算法[J].遥感学报,2000,4(1):32-35.

[3]Larkin B J.An ANSIC Program to Determine Expected Li near Time the Vertices of the Convex Hull ofa Set ofPlanar Points[J].Computers&Geosciences,1991,17(3):431-443.

[4]周培德.算法设计与分析[M].第2版.北京:清华大学出版社,2004:209-210.

[5]吴立新,史文中.地理信息系统原理与算法 [M].北京:科学出版社,2001:65-70.

[6]蒲浩,宋占峰,詹振炎.快速构建三角网数字地形模型方法的研究 [J].中国铁道科学,2001,22(6):100-106.