平面点集Delaunay三角剖分的分治算法

Divide-and-conquer algorithm for constructing Delaunay triangulation of planar points

为发展图形网格化技术,研究了平面点集的三角剖分算法。根据经典算法中在实际应用中遇到的共性问题,提炼了3个工具算法;为了更好地表示平面区域划分的拓扑信息,引入了双链接边表(DCEL)的数据结构。在此基础上,设计并实现了平面集Delaunay三角剖分分治算法,并对特殊退化情况进行了处理,通过计算表明了该算法时间复杂度为O(N*logN)。实验数据结果验证了该算法的正确性、健壮性。

To develop graphic mesh generation technology, algorithms of triangulation in 2d is studied. According the common problems encountered in the practical application by using classical algorithm, 3 auxiliary sub-algorithms are refined. In order to represent topology information of surface region efficiently, a data structure named doubly-connected edge list （EX]EL） is intro- duced. On this basis, a Delaunay triangulation algorithm based on strategy of divide-and-conquer is illustrated in detail. Special degenerate cases are also taken into consideration, and the conclusion that the algorithm will take O （N ＊ logN） time in total is proved. The experimental results verify the correctness and robustness of the algorithm