基于平面多边形Voronoi图的算法与快速成形应用

摘要

探讨了平面多边形的Voronoi图的性质,提出了一种新的求解平面多边形的Voronoi图的算法,其核心思想是单独考虑每个Voronoi图对象,分开计算其分治区,然后再构成一个具有拓扑关系的Voronoi图.这种计算方法较其他现有算法(比如二分法)大幅度提高了求解Voronoi图的成功率,在VC++平台上得到了实现,并应用于快速成形的等距线扫描工艺中.该算法求解平面切片的轮廓的Voronoi图和生成等距线速度快,可以实时生成切片轮廓的全部等距线.试验证明:算法可以减少制件特别是类似大平面制件的翘屈变形,提高制件整体质量.