基于Delaunay三角剖分生成Voronoi图算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于Delaunay三角剖分生成Voronoi图算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要:针对Delaunay三角网生长算法和间接生成Voronoi图算法构网效率不高的问题,提出了一种Delaunay三角网生长法间接生成Voronoi图的改进算法。该算法以点集凸壳上一边快速生成种子三角形,定义了半封闭边界点的概念,在三角形扩展过程中动态删除封闭点及半封闭边界点,加快Delaunay三角网生成速度。然后又定义了有序目标三角形的概念,该算法能迅速查找点的有序目标三角形,生成无射线的Voronoi图;考虑凸壳上点的特性,借助三个无穷点生成带射线的Voronoi图。通过实验结果分析表明,改进的算法执行效率有了很大提高。

关键词:Delaunay三角剖分;Voronoi图;凸壳;计算几何

中图分类号: TP391.41

文献标志码:A

Voronoi diagram generation algorithm based on Delaunay triangulation

SUN Jizhong1,HU Yan2, MA Yongqiang1

1.School of Information Science and Technology,Southwest Jiaotong University, Chengdu Sichuan 610031,China;

2.Department of Mathematics, Southwest Jiaotong University, Chengdu Sichuan 610031,China

)

Abstract: Considering the problem that the algorithm of building autoconnected Delaunay triangulation and indirectly building Voronoi diagram is of low efficiency, an improved Voronoi generation algorithm based on autoconnected Delaunay triangulation was presented. The seed triangle was rapidly generated by one side of the convex hull.The notion of half closedborderpoint was proposed. The algorithm removed closedpoints and half closedborderpoints in the process of expanding triangle and improved the speed of generating Delaunay triangulation.Then, the notion of ordered target triangle was defined. It quickly found ordered target triangles and generated the nonray Voronoi diagram. Considering the characteristics of convex hull, a ray Voronoi diagram was generated by three infinite points. The experimental results show that the efficiency of the improved algorithm is obviously improved.

Key words: Delaunay triangulation; Voronoi diagram; convex hull; computational geometry

0 引言

Voronoi图与Delaunay三角形、Convex hull并列为计算几何的三大支柱,它已成功解决了找最近点、求最大空圆、求N个点的凸包、求最小生成树等问题,在计算机图形学、地理信息系统、模式识别等有广泛的应用 [1-2]。Voronoi图与Delaunay三角剖分互为对偶图,则可以通过Delaunay三角剖分间接生成Voronoi图。Delaunay三角剖分具有最大化最小角、外接圆准则等重要性质。文献[3]根据实现过程,把生成D三角网的各种算法分为三类:分治算法、逐点插入法、三角网生长法。而三角生长法基本上都在寻找“第三点”上进行改进。例如McCullagh和Ross[4]通过把点集分块和排序改进了点搜索方法,减少了搜索时间。文献 [5]中提出了封闭点概念对三角网生长算法作出了一些改进,如果凸壳上的点数过多,影响第三点的搜索速度,算法效率会降低。由Delaunay图构造Voronoi图,通常做法是遍历所有三角形,找到与该点相关的三角形。如果点集数比较多,每次都遍历一次所有三角形,搜索效率比较低;其次不能有效区分对凸壳内部点与凸壳边界点生成Voronoi图。为此,针对以上问题提出了一种Delaunay三角剖分间接生成Voronoi图的改进算法,该算法能提高构造Delaunay三角剖分速度,对凸壳内部点与凸壳边界点进行有效识别与处理,同时提高构造 Voronoi图的速度。

1 基本概念

在构造Delaunay图过程中,动态剔除封闭点和半封闭边界点,可以减少第三点的搜索时间,提高生成新三角形的速度。所以在文献[5]封闭点概念的基础上,定义半封闭边界点:

定义1 不共线点集S={v0,v1,v2,…,vn|n≥2},Ъ偕瑾v为点集S凸壳上的一点,与v相连接的点集合E(v)={p1,p2,…,pm}。如果存在E(v)Р晃空,p1vp2、p2vp3,А, pm-1vpmО纯占渌呈闭牖蚰媸闭刖已形成三角形,且p1、pm为凸壳上的点及vp1、vpm为凸壳上的边,则v为半封闭边界点。

为了提高Voronoi图的构造效率,定义有序目标三角形。

定义2 p0为目标点,如果三角形TУ娜个顶点中包含点p0,г虺篇Tв氇p0相关,记为R(p0,T)。显然若多个三角形Tiв氲悛p0相关,Ъ俏R(p0,T0,T1,…,Tn)。把T0,T1,…,TnО纯占湮恢盟呈闭牖蚰媸闭肱判蛭T0′,T1′,…,Tn′,则称R(p0,T0′,T1′,…,Tn′)为关于p0的有序目标三角形。

由于算法的实现和绘图的需要,定义如下数据结构。

定义3 用于存储平面上散乱点的数组为pointArray,构成Delaunay三角网的初始化点集链表为PointList,构成Voronoi图点集链表为PointList_V。定义了如下三个类:1)点类,包括点编号ID、У阕标(x,y)、是否为凸壳上的点huSign、该点使用次数是否为2clSign、与该点相关的边集edgeList;2)边类,与该点相连的有向边终点编号ID,边的使用次数nCount;3)三角形类,三角形的编号ID、点指针数组*index[3]、三角形是否扩展enlarge。

2 Delaunay三角剖分的生成

改进算法构造Delaunay三角剖分的基本思想:先快速生成包含点集的凸壳,利用凸壳上的一边快速创建满足三角剖分的种子三角形,然后对该种子三角形的一边进行扩展,生成新的三角形,循环扩展所有新三角形新生成的两边,同时删除封闭点和半封闭边界点,直到三角形都扩展完毕。其过程如图1所示。

算法的关键是:1)如何快速创建凸壳。2)快速创建种子三角形。选凸壳上的一边进行扩展可省去确定第二点的时间。3)如何快速搜素第三点,搜素第三点关键在于删除封闭点和半封闭边界点,减少点的搜素时间。

图片

图1 三角剖分构成过程

图片

图2 点集凸壳生成过程

2.1 点集的预处理

С跏蓟点集SУ氖组pointArray、У慵SУ牧幢PointList、三角形链表TriList、Delaunay三角剖分后点集SУ牧幢PointList_V、三角形个数Tricount=0。

2.2 凸壳的生成

构建散乱点集S的凸壳CH(S)的方法,通常可以分为两类:一类是基于对点集排序的基础上,时间复杂度主要取决于排序时间,如格雷厄姆扫描法、卷包裹法。另一类不用预先进行排序,如增点递推算法,其时间复杂度为O(2hn) [7]。本文凸壳算法引用文献[6],不需要排序,时间复杂性为线性,执行效率比较高。

步骤1 求点集S中,xё标最大时yё标也最大、xё标最小时yё标也最小所对应的点,设为p0(x┆min,yxmin)、p4(x┆max,yxmax)如图2所示。对点集求区间L=(x┆min,x┆max)/k(k=x┆max-x┆min为正整数),Щ分点集S所在区域为k个长条,计算S中各点所在长条的编码,位于第i条的点构成Si。S=∪ki=aSi。г谙叨为p0p4е间的点,计算Si中点的y坐标最大、最小值的点,设为piymax、piymin,i=1,k,S•i={px,piymax,piymin}。О椽xё标值升序把S•iе歇piymaxб来渭尤肓幢LiskYmax。同理,按xё标值降序把S•iе歇piyminб来渭尤肓幢LiskYmax。如图2,经过处理后,除横坐标为x┆min、x┆maxУ牡阃,分为S上= {p5, p6, p7, p8, p9},S下= {p1, p2, p3, p10, p11}。オ

步骤2 把长条区间S•1е歇p1ymin、p1ymaxХ侵馗吹愕囊来渭尤肓幢LiskHull,然后依次以Listmax中的点为极坐标顶点,求Listmax中此点以后基于xе嵴方向斜率最大的点加入ListHull中,直到链表LiskYmax遍历到最后一个点为极坐标顶点,把最后一个点加入ListHull中。如图2所示,以p0为极坐标顶点,求p0б院罅幢LiskYmax中基于xе嵴方向最大斜率的点为p7,О血p7Ъ尤LiskHull。同理依次把p6、p5、p4Ъ尤ListHull中。

步骤3 把长条区间S•kе歇yё标最小的点非p4У慵尤肓幢LiskHul。分别以链表ListYmin中的点为极坐标顶点,在链表LiskYmin中求最大斜率的点,直到链表ListYmin遍历到最后一个点为极坐标顶点,把最后一个点加入ListHull中。如图2所示,分别把p3、p2、p1Ъ尤LiskHull中。

步骤4 链表LiskHull即为点集凸壳上的点。

┑1期 ┧锛讨业:基于delaunay三角剖分生成voronoi图算法

┆扑慊应用 ┑30卷

2.3 Delaunay三角网生成

步骤1 对凸壳上的点及边链表更新。凸壳上的点huSign=TRUE,点的有向边链表使用次数赋值为1。

步骤2 创建种子三角形。如图1所示:以p1p2为一边,在链表PointList中寻找点p0,使角∠p1p0p2ё畲,创建种子三角形,加入到链表TriList中,三角形计数Tricount加1,Ц新点的边链表及边的使用次数分别加1。

步骤3 扩展种子三角形第一边。如图1所示p1p2П,边的使用次数为2就不再扩展。

步骤4 循环扩展所有三角形。循环扩展三角形的链表TriList中新生成的两条边,直到链表TriList中三角形遍历完为止,执行步骤5。

寻找第三点应满足:1)与该点相关的边的使用次数不全为2;2)与该边所对应该点的角度在未扩展点集中最大;3)当前扩展三角形的另一顶点分布在当前扩展边的两侧。

边的扩展:若边的使用次数小于2时扩展,等于2不扩展。

生成的新三角形加入到三角形链表TriList中,Tricount次数加1,Ц新点的边链表以及边的使用次数加1。而每个新生成三角形有向边为6,均加1。当点成为封闭点和半封闭边界点时,删除此点,加快第三点的搜索速度。

由文献[5]和定义1可以判断封闭点与半封闭边界点:如果点的边链表使用次数均为2且该点不是凸壳上的点,则该点为封闭点,如图1的p0У恪M箍巧系牡闱业愕谋吡幢硎褂么问均为2时,则该点为半封闭边界点,如图1p1У恪K以删除封闭点和半封闭边界点判别条件统一为:判断点的边链表使用次数是否均为2。

步骤5 三角形链表TriList即为所求三角剖分。

3 Voronoi图生成

3.1 间接生成Voronoi图分析

由Delaunay三角网构造Voronoi图关键寻找每个点的有序目标三角形。而寻找有序目标三角形定位的常规方法[8]是遍历所有的三角形,找到与该目标点相关的所有三角形。对有序目标三角形的圆心按空间位置进行顺时针或逆时针排序,然后依次连接圆心生成该点Voronoi图。遍历所有点,Ь蜕成点集SУVoronoi图。如果点集S很大,г蛏成的三角形的总数很多,如果每个点都遍历一次三角形链表,然后排序生成Voronoi图,则花费的时间较多,从而影响了Voronoi图的生成速度。针对以上问题,改进算法思想是快速定位每个点的有序目标三角形,顺序连接三角形外接圆的圆心,生成Voronoi图。该算法同时考虑凸壳边界点的特性,对生成带射线Voronoi图与不带射线Voronoi图进行详细分析。

3.2 快速确定有序目标三角形

由定义3可以得到点和边的类数据结构,加上点集数组pointArray,我们可以快速确定有序目标三角形。如图3所示,点p0У谋吡幢砜梢匀范ǖ{C0,C1,C2,C3,C4,C5}的ID号,在点的数组pointArray可以确定坐标,然后把p0У谋吡幢碇械牡惆此呈闭牖蚰媸闭肱判,可以确定p0的有序目标三角形R{P0,T0,T1,T2,T3,T4,T5}。

图片

图3 有序目标三角形

3.3 带射线的Voronoi图与无射线的Voronoi图

带射线Voronoi图与无射线Voronoi图的区别关键是凸壳上的点的处理。对凸壳内部的点,二者处理都是一样。

只处理凸壳内部的点时,生成不带射线的Voronoi图,如图4所示:点K0、K1、K2、K3为初始点集S,A1、A2、A3Х直鹞构造Delaunay三角剖分后外接圆的圆心,虚线表示不带射线的Voronoi图。考虑Delaunay图与Voronoi图的关系,借助相对于点集所在区域中最大X、Yе滴耷畲笠约白钚―X、Yе滴耷钚≈械娜个辅助点参与三角剖分,三个辅助点与其外接圆圆心相连彼此近似120°即可。显示时,凡是包含三个辅助点中任意一点的Delaunay三角剖分都不显示,而包含其中两个点的三角形的外接圆的圆心不参与Voronoi图的构成。如图5所示添加三个辅助点w1、w2、w3,Ч钩Voronoi图的过程,得到红方框内的带射线的Voronoi图,如图6所示。

图片

图4 不带射线的Voronoi图

图片

图5 添加三个无穷点构成Voronoi图过程

3.4 改进的间接生成Voronoi图算法

这里只阐述不带射线的Voronoi图生成过程,带射线Voronoi图需要添加三个辅助点参与Delaunay图构成即可。

步骤1 在Delaunay生成过程中,用点集链表PointList_V添加删除的封闭点和半封闭边界点,然后把链表PointList中剩余的点添加到PointList_V中。

步骤2 遍历点链表PointList_V。

判断当前点为p0是否为空,若不空执行1),否则结束链表的遍历。

1)若p0为凸壳上的点(半封闭边界点),不参与Voronoi图构成,执行5),否则执行2)。

2)凸壳内部的点(封闭点),遍历该点的边链表edgeList,边链表保存有向边终点ID号,利用点集数组pointArray,求得各点坐标。

3)把各点坐标按顺时针或逆时针排序,排序后生成有序目标三角形R(p0,T0,T1,…,Tn),Ъ扑愀魅角形的外接圆的圆心。

4)顺时针或逆时针依次连接圆心生成该点Voronoi图。

5)遍历下一个节点。

图片

图6 带射线的Voronoi图

4 实现的结果与分析

本文算法采用C++语言编程,用VC++6.0编译环境分别实现了原算法及改进的算法。计算机的配置为Intel CPU 1.80 GHz(2 CPUs),1B024 MB内存。在随机产生没有约束的1B000个离散点后,生成凸包,如图7所示。生成细线为Delaunay三角剖分和粗线为不带射线Voronoi图,如图8所示。

图片

图7 初始化点集和生成凸壳 图8 Delaunay图和Voronoi图

为了比较算法改进前后的效率,分别用1B000、2B000、3B000、4B000、5B000和10B000个随机离散点,在没有约束的情况下,分别对生成Delaunay三角网和生成不带射线Voronoi图分阶段进行构网,实验结果对比如表1、2所示。

表格(有表名)

表1 Delaunay三角网算法改进前后对比

点数凸壳上さ闶三角形数

耗时/s

文献[5]算法改进后算法

1B000171B9810.5380.451

2B000243B9701.5821.473

3B000265B9653.3963.076

4B000217B9755.9395.043

5B000239B9719.0597.078

10B0002919B96035.09126.822

由表1可以看出改进的Delaunay构网算法,总体上效率高于文献[5]中的算法,点数较少时,二者相差很小,当点数较多时,改进算法优势较明显。由表2所示,在Delaunay三角剖分基础上生成Voronoi图,随着点数和三角形的增多,改进的算法较原算法的效率提高就越明显。表2的原算法之所以比表1生成Delaunay三角网的时间还要高,主要原因是随点数增多和生成Delaunay三角形增多,每次遍历寻找有序目标三角形,花费时间较大。

表格(有表名)

表2 D图直接生成V图算法改进前后对比

点数三角形数

耗时/s

原算法改进后算法

1B0001B9810.2280.038

2B0003B9800.7550.074

3B0005B9612.8670.107

4B0007B9747.2140.113

5B0009B97012.4170.124

10B00019B95849.9160.169

5 结语

Delaunay三角剖分间接生成Voronoi图的改进算法,无论是在Delaunay三角网构造阶段还是在Voronoi图构造阶段,效率较原算法均有所提高,特别是在寻找点集的有序目标三角形效率非常高,但间接构造Voronoi图算法仍依赖于Delaunay三角形的构网速度。

参考文献:[1] AURENHAMMER F. Voronoi diagrams: A survey of a fundamental geometric data structure[J]. ACM Computing Surveys,1991, 23(3): 345-405.

[2] 刘金义,刘爽. Voronoi图应用综述[J].工程图学学报,2004,25(2):125-132.

[3] BRASSEL K E,REIF D. Procedure to generate thissen polygons[J]. Geographical Analysis, 1979(11): 289-303.

[4] McCULLAGH M J,ROSSC G T.Delaunay triangulation of a random data set for is arithmic mapping[J]. The Cartographic Journal,1980(17): 93-99.

[5] 凌海滨,吴兵,改进的自连接Delaunay三角网生成算法[J].计算机应用,1999,19(12):10-12.

[6] 周培德.计算几何:算法设计与分析[M]. 3版.北京:清华大学出版社,2008.

[7] 张忠武,吴信才.平面海量散乱点集凸壳算法[J].计算机工程,2009,35(9):43-45.

[8] 刘少华,罗小龙, 何幼彬, 等. 基于Delaunay三角网的泰森多边行生成算法研究[J]. 长江大学学报,2007,4(1):100-103.