基于二维凸壳的平面点集Delaunay三角网算法

Planar Delaunay Triangulation Algorithm Based on 2D Convex Hull

提出了一种基于并行二维凸壳算法的平面点集的Delaunay三角网生成算法。该算法基于颜坚等在文献[20]中提出的并行二维凸壳算法,在构建凸壳时记录被替换的边和被删除的点,形成一个初始三角网;再在初始三角网的各个三角形内部,采用逐点插入法构建局部的Delaunay三角网;最后,对各个局部Delaunay三角网的边界边进行局部优化,得到原点集的Delaunay三角网。文中给出了算法的正确性说明,实验结果也表明该算法稳定高效。

This paper proposed a planar Delaunay triangulation algorithm based on parallel 2D convex hull algorithm. The proposed algorithm is based on the parallel 2D convex hull algorithm proposed in literature [20] by Jian Yah, etc. It constructs an initial triangulation by recording the grown edges and the removed points during the convex hull building, then constructs partial Delaunay triangulation through point by point method inside each triangle of the initial triangulation, finally locally optimizes the boundary edges of the local Delaunay triangulations to get the Delaunay triangulation of the whole origin set. The correctness of the algorithm was discussed. And the experiment results show that the algorithm is efficient and stable.