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

关键词：平面连通域 平分线 voronoi图 凸多边形中轴算法 计算几何 

单位：上海交通大学; 机械与动力工程学院; 上海; 200030