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

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

Voronoi diagram generation algorithm based on Delaunay triangulation

SUN Jizhong1,HU Yan2, MA Yongqiang1

of Information Science and Technology,Southwest Jiaotong University, Chengdu Sichuan 610031,China??;??
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 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 , 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三角网的各种算法分为三类:分治算法、逐点插入法、三角网生长法。而三角生长法基本上都在寻找“第三点”上进行改进。ullagh和Ross[4]通过把点