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

摘要

为发展图形网格化技术,研究了平面点集的三角剖分算法.根据经典算法中在实际应用中遇到的共性问题,提炼了3个工具算法；为了更好地表示平面区域划分的拓扑信息,引入了双链接边表(DCEL)的数据结构.在此基础上,设计并实现了平面集Delaunay三角剖分分治算法,并对特殊退化情况进行了处理,通过计算表明了该算法时间复杂度为0(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 (DCEL) is introduced. 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 0 (N * logN) time in total is proved . The experimental results verify the correctness and robustness of the algorithm.