自由边界平面连通域的Voronoi图生成方法研究

摘要

平面连通域的Voronoi图被广泛应用于许多领域,常用的分治法等算法实现较为复杂,影响了其应用范围.在凸多边形中轴算法的基础上,提出一种建立自由边界平面连通域的Voronoi图的新方法.通过求解相邻边界元素的平分线,计算出相邻平分线的交点,由距离最小的平分线交点实现Voronoi图边的增长,最终建立完整的平面单连通域的Voronoi图.同时,还介绍了平面多连通域的内外边界的Voronoi图的合并算法.