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

目的 研究构建约束Delaunay三角网的方法 ,提高构建约束Delaunay三角网的速度.方法 基于生长法并利用分治法的思想,以约束边为基边分别向两侧重新构网,先构建Delaunay三角网,然后插入约束边并删除与约束边相交的边,按照构网条件对约束边两侧的空腔构网,直至约束边两侧构建成三角网,最后使其成为约束Delaunay三角网.结果 实验测试表明,在地形点数为5 000时,传统算法构建CDT时间为6 195 ms,笔者算法构建CDT时间为6 007ms,速度明显优于传统算法.结论 算法简单、运算速度快、内存开销小且易于实现.

Constrained Delaunay Triangulation Division Algorithm Based on Maximal Circumcircle

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.