Abstract: Considering the problem that the algorithm of building autoconnected Delaunay triangulation and indirectly building Voronoi diagram is of low efficiency, an improved Voronoi generation algorithm based on auto-connected Delaunay triangulation was presented. The seed triangle was rapidly generated by one side of the convex hull. The notion of half closedborderpoint was proposed. The algorithm removed closed-points and half closedborderpoints 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 non-ray 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, computational geometry, convex hull

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

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