基于四叉树结构的加权Voronoi图生成算法

摘要

Considering the limitation of research on ordinary Voronoi diagram and low efficiency of the capabilities to build weighted voronoi diagram, a method based on quadtree structure for generating weighted Voronoi diagram was proposed in tliis paper. The key idea of this method was to obtain searched correlated seeds region of the non-expansion nodes by the quadtree structure, calculate the time consumption value to replace weighted distance, and determine the ownership seed according to the node shortest time consumption value. The computing model based on quadtree structure and several basic characteristics of the method were given. The test result shows that the seeds are rapidly dilated, the time complexity gets effectively lower than uniform grid structure. The algorithm is simple, and it has a strong maneuverability and practical value.%针对普通Voronoi图研究的局限性和加权Voronoi算法的低效率问题,提出基于四叉树结构的加权Voronoi图生成方法.核心思想是利用四叉树结构的层次性,获取未膨胀节点的搜索区域和相关生长源,以时间消耗值替代加权距离,并以节点的最短时间消耗值为依据查找归属生长源.推理了基于四叉树结构计算模型的几个基本性质.实验结果表明,本方法能实现生长源的快速膨胀,有效降低时间复杂度,其时间复杂度小于均匀格网结构,可操作性强,具有较好的实用价值.