基于最小正切值的约束Delaunay三角剖分

Constrained delaunay triangulation based on the minimal tangent value

以TIN生长算法和分治算法的思想为基础,提出一种改进的构建约束Delaunay三角网(CDT)的算法.该算法在生长算法和分治算法思想的基础上,以约束边为基边分别向两侧重新构网.以基边与离散点形成的三角形的最小正切值为判断条件确定基点,实现对约束边影响域的三角剖分.实验对比表明该算法减少了搜索基点的时间,提高了构网速度.因此得到最小正切算法优于传统算法的结论.

Traditional methods of the construction of constrained delaunay triangulation were studied combined with our algorithm,an improved algorithm of the construction of constrained delaunay triangulation（CDT） was presented.Based on the growth algorithm and divides and conquer algorithm,the advanced ＂two-step method＂ for reconstructing network from constrained edge toward both sides was proposed.The basic point was determined by the tangent value of the minimal angle in the triangle formed by discrete points and basic edge,and triangulation of influence domain of constrained edge was realized.The algorithm reduced the time of searching basic point and enhanced the speed of network constructing.Thus it could obtain the conclusion of minimal tangent algorithm better than the traditional algorithm.