一种高准确度的约束Delaunay三角网生成算法研究

Study on a New CDT Algorithm Based on High Accuracy

约束线段的嵌入是CDT两步法的关键步骤之一,目前该方面的研究还不够完善,主要忽视了影响区域是凹多边形和影响区域内包含悬挂点的情况。该文研究带有约束条件的Delaunay三角网的生成问题,考虑了约束线段影响区域的特殊情况,采用递归割耳法嵌入约束线段,先将影响区域调整为简单多边形,再递归寻找并割去多边形的耳,最终将影响区域重新三角剖分。该方法可有效提高约束Delaunay三角网的质量。

Embedding bound lines is one of the key steps in the two-step algorithm, but the research is not yet adequate, which ignores the case that the affected region is a concave polygon or the affected region contains hoisted points. The recursive cutting-ear method is presented for embedding bound lines in this paper. The affected region is adjusted to a simple polygon first of all. Then ‘polygon-ears＇ are searched out and cut recursively. At last the affected region is cut into some triangles. Taking into account the special circumstances of the affected region, the recursive cutting-ear method is applied to CDT two-step algorithm. The results of experiments show that the algorithm can effectively improve the quality of CDT network.