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

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

作　　者：谢增广[1] 

机构地区：[1]华北计算技术研究所,北京100083

出　　处：《计算机工程与设计》2012年第7期2652-2658,共7页Computer Engineering and Design

基　　金：国家自然科学基金项目(60672174);民航局科技基金项目(MHRD200807)

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

关 键 词：平面点集Delaunay三角剖分 双链接边表 分治策略 计算几何 

分 类 号：TP311.11[自动化与计算机技术—计算机软件与理论]