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

龙源期刊网 https://www.wendangku.net/doc/747081137.html,

基于四叉树结构的加权Voronoi图生成算法作者：李锐李佳田王华蒲海霞何育枫

来源：《计算机应用》2012年第11期

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

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

中图分类号： TP391.41