三维点集Voronoi图的算法实现

Implementation of Voronoi diagram algorithms for 3D point set

对现有三维点集Voronoi图的生成算法进行深入研究,提出并实现由Delaunay三角剖分构建Voronoi图的算法.首先采用随机增量局部转换计算Delaunay三角剖分,然后再根据对偶特性构建Voronoi图.该算法健壮性很高,适用于处理各种非完全共面三维点集.

Based on the deep research on the construction algorithms of 3D Voronoi diagram, the algorithm of constructing the Voronoi diagram from a Delaunay triangulation is proposed and implemented. Delaunay triangulation is achieved by using randomized incremental local transformation. Then its Voronoi diagram is created according to the dual property. The algorithm is highly robust and adapt to any non-coplanar 3D point set.