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

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

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

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 O(N*logN) time in total is proved.The experimental results verify the correctness and robustness of the algorithm.