计算机应用 ›› 2012, Vol. 32 ›› Issue (11): 3078-3081.DOI: 10.3724/SP.J.1087.2012.03078

• 计算机软件 • 上一篇    下一篇

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

李锐,李佳田,王华,蒲海霞,何育枫   

  1. 昆明理工大学 国土资源工程学院,昆明 650093
  • 收稿日期:2012-05-28 修回日期:2012-07-09 发布日期:2012-11-12 出版日期:2012-11-01
  • 通讯作者: 李佳田
  • 作者简介:李锐(1987-), 女, 云南曲靖人, 硕士研究生, 主要研究方向:地标提取中的Voronoi方法;
    李佳田(1975-), 男, 黑龙江佳木斯人, 副教授,主要研究方向:Voronoi模型与方法;
    王华(1988-), 女, 陕西西安人, 硕士研究生, 主要研究方向:Voronoi邻近查询方法;
    蒲海霞(1987-), 女, 甘肃天水人, 硕士研究生, 主要研究方向:空间性文本的建模与计算;
  • 基金资助:
    ;国家自然科学基金资助项目(61079006,61179060);云南省自然科学基金

Algorithm for Generating Weighted Voronoi Diagram Based on Quadtree Structure

LI Rui,LI Jia-tian,WANG Hua,PU Hai-xia,HE Yu-feng   

  1. Faculty of Land Resource Engineering, Kunming University of Science and Technology, Kunming Yunnan 650093,China
  • Received:2012-05-28 Revised:2012-07-09 Online:2012-11-12 Published:2012-11-01
  • Contact: LI Jia-tian

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

关键词: 加权Voronoi图, 四叉树结构, 相关生长源区域, 时间消耗值

Abstract: 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.

Key words: weighted Voronoi diagram, quadtree structure, related seed region, times consumption value

中图分类号: