快速粗糙域Voronoi图离散生成算法研究

摘要

Voronoi图是计算几何的一个重要分支，粗糙域Voronoi图是Voronoi图概念在复杂生成面上的扩展，对其离散生成进行研究有重要的现实意义。粗糙域Voronoi图离散生成一般采用最短路径法，算法的复杂度很高，很难适应宽范围、多母点的粗糙域分隔。为了降低粗糙域Voronoi图离散生成的复杂度，文章提出了加权的广度搜索算法对粗糙域Voronoi图进行离散生成，并利用边界方向直方图分析对粗糙域生成面分隔的有效性进行了验证。实验结果表明，本算法对粗糙域的分隔是有效的、解决了一般算法的空穴问题且大大降低了离散生成算法的复杂度。