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

作     者：李锐 李佳田 王华 蒲海霞 何育枫 LI Rui;LI Jia-tian;WANG Hua;PU Hai-xia;HE Yu-feng

作者机构：昆明理工大学国土资源工程学院昆明650093 

出 版 物：《计算机应用》 (journal of Computer Applications)

年 卷 期：2012年第32卷第11期

页      面：3078-3081页

核心收录：

学科分类：08[工学] 080203[工学-机械设计及理论] 0802[工学-机械工程] 

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

主　　题：加权Voronoi图 四叉树结构 相关生长源区域 时间消耗值 

摘      要：针对普通Voronoi图研究的局限性和加权Voronoi算法的低效率问题,提出基于四叉树结构的加权Voronoi图生成方法。核心思想是利用四叉树结构的层次性,获取未膨胀节点的搜索区域和相关生长源,以时间消耗值替代加权距离,并以节点的最短时间消耗值为依据查找归属生长源。推理了基于四叉树结构计算模型的几个基本性质。实验结果表明,本方法能实现生长源的快速膨胀,有效降低时间复杂度,其时间复杂度小于均匀格网结构,可操作性强,具有较好的实用价值。