Voronoi diagram generation algorithm based on Delaunay triangulation

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.