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

Algorithm for generating weighted Voronoi diagram based on quadtree structure

作　　者：李锐[1] 李佳田[1] 王华[1] 蒲海霞[1] 何育枫[1] 

机构地区：[1]昆明理工大学国土资源工程学院,昆明650093

出　　处：《计算机应用》2012年第11期3078-3081,共4页journal of Computer Applications

基　　金：国家自然科学基金资助项目(40901197;41161061);云南省自然科学基金资助项目(2008D032M)

摘　　要：针对普通Voronoi图研究的局限性和加权Voronoi算法的低效率问题,提出基于四叉树结构的加权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 this 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图 四叉树结构 相关生长源区域 时间消耗值 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]