中文摘要：

为发展图形网格化技术，研究了平面点集的三角剖分算法。根据经典算法中在实际应用中遇到的共性问题，提炼了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