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

Voronoi diagrams algorithm based on polygon and in the rapid prototyping applications

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

The article explored the Voronoi diagrams polygon graphic nature, proposed a new Voronoi diagrams of graphic polygon calculation algorithm, Its core idea was to consider each individual object of Voronoi diagram, calculate Voronoi region separtately, then build a Voronoi diagram with topological relations. The algorithm substantially increased the calculation success rate to outperform the other （e. g. divide-and-conquer） algorithm for all. And it was realized in VC＋＋ platform, applied to the rapid prototyping （RP） trajectory scanning technology. The algorithm had high speed in calculating Voronoi diagrams of plane slice and generating trajectory scanning lines, can generate all the equidistance lines of slice profiles real-timely. Experiements also proved the scan process can reduce the deformation of slice especially large plane after applied the algorithm, and improve the overall quality of parts.