圆形剖分再生长的扩展Voronoi图构建方法

Construction method of extended Voronoi diagram based on circular partition and re-growth

针对传统Vonoroi图生成过程中存在的局限性,根据各种Voronoi图生成算法的原理和特点,该文融合Delaunay算法和模拟生长算法的思想,提出了一种基于圆形剖分再生长的扩展Voronoi图生成方法。根据任务要求自定义生长函数,实现初始圆的扩展生长,达到成熟条件时停止生长;计算相邻圆之间的交点并作交线,通过一定处理后得到对应生成元的Voronoi图边界,遍历所有生长圆即可得到全域Voronoi图。通过仿真验证了该方法的可行性,易于拓展到加权Voronoi图的构建,为Voronoi图的构建提供了一种技术手段,且该方法更简洁直观。

In view of the limitations of the traditional Vonoroi diagram’s generation process, according to the principle and characteristics of various Voronoi diagram’s generation algorithms, a new Voronoi diagram generation method based on circular partition and re-growth was proposed by combining the ideas of Delaunay algorithm and simulating growth algorithm in this paper. According to the task requirements, the growth function was defined to realize the expansion and growth of the initial circle, and the growth stoped when the mature condition was reached. The intersection points between adjacent circles were calculated and the intersection lines were made. After certain processing, the boundary of Voronoi diagram of the corresponding generators was obtained, and the Voronoi diagram of the whole region could be obtained by traversing all the growing circles. The feasibility of this method was verified by simulation, which was easy to be extended to the construction of weighted Voronoi diagram, and provided a technical means for the construction of Voronoi diagram. Moreover, this method was more concise and intuitive.