带特征线约束的Delaunay三角剖分最优算法的研究及实现

Delaunay Triangulation Dividing Optimal Algorithm with Constraint Line

为提高带特征线约束的Delaunay三角剖分的速度和效率，从两个方面进行改进：一是生成无约束的Delaunay三角网时，采用并行剖分算法；二是在约束线上插入点时，应用取三角形外接圆与特征线交点的方法。并行剖分算法具有较好的加速性能；"交点"插入算法考虑了特征线的影响域及Delaunay三角形规则的边界条件，在满足全局Delaunay三角剖分的前提下，使插入的点最少，对原有的网格影响最小。

To improve performance of Delaunay triangulation dividing with constraint line,the paper gives the following method: (1)To generate Delaunay triangulation grid without constrain by parallel algorithm;(2)To insert new points by getting intersection point of circle defined by the triangulation's three vertices and constraint line. The parallel algorithm executes with higher performance. Considering affecting region of the constraint line and edge conditions of Delaunay triangulation rule, the 'intersection point' inserting algorithm makes points which need inserted the fewest and affects less, on basis of satisfying overall Delaunay triangulation characteristic.