基于最大外接圆的约束Delaunay三角剖分算法  

Constrained Delaunay Triangulation Division Algorithm Based on Maximal Circumcircle

作　　者：宋晓宇[1] 戚爰伟[1] 王永会[1] 

机构地区：[1]沈阳建筑大学信息与控制工程学院,辽宁沈阳110168

出　　处：《沈阳建筑大学学报（自然科学版）》2008年第6期1094-1098,共5页Journal of Shenyang Jianzhu University：Natural Science

基　　金：国家十五科技攻关项目(2006BAJ06B08-03)

摘　　要：目的研究构建约束Delaunay三角网的方法,提高构建约束Delaunay三角网的速度.方法基于生长法并利用分治法的思想,以约束边为基边分别向两侧重新构网,先构建Delau-nay三角网,然后插入约束边并删除与约束边相交的边,按照构网条件对约束边两侧的空腔构网,直至约束边两侧构建成三角网,最后使其成为约束Delaunay三角网.结果实验测试表明,在地形点数为5 000时,传统算法构建CDT时间为6 195 ms,笔者算法构建CDT时间为6 007ms,速度明显优于传统算法.结论算法简单、运算速度快、内存开销小且易于实现.In order to research the method of constructing constrained Delaunay triangulation and enhance the speed of constructing, based on the growth method and the divide-and-conquer strategy, the triangulation was reconstructed through constrained edges that were considered based edges. Delaunay triangulation was constructed first. Then the constrained edges were inserted; edges which intersected on constrained edges were deleted and the net of space beside constrained edges were constructed based on the conditions of construction net until both sides of constrained edges had constructed triangulation. Finally, the constrained Delaunay triangulation was established. The simulation results showed that the time of constructing CDT with traditional algorithm was 6 195 ms, but our algorithm needed 6 007 ms when the number of terrain points was 5 000. The algorithm is more effective, less expensive with less memory and it can be achieved simply.

关 键 词：约束 DELAUNAY三角网 基点 基边1 

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