基于线性四叉树结构的Voronoi图反向膨胀生成方法

摘要

提出一种基于线性四又树结构并顾及矢量与栅格计算性质的Voronoi图生成方法,其核心思想是利用线性四叉树结构以减小空间割分所产生的空间复杂度,改变膨胀模拟操作的计算方向以减小时间复杂度.讨论了基于数学形态学的反向膨胀计算模型及推理出基于该计算模型的几个优化计算性质.实验验证,这种方法能够有效地平衡时空复杂度,并且易于求取邻元,其时间复杂度小于均匀格网结构与常规四叉树结构.一般情况下,空间复杂度小于均匀格网结构.