改进的约束数据域三角剖分算法及应用

在逐点插入算法的基础上,通过深入研究影响算法效率提高的因素,对其中的包容盒、空外接圆检测算法、快速查找点所在的三角形算法、快速查找与约束线段相交的边算法进行优化和改进,提出一种改进的约束数据域三角剖分算法,使得构网效率接近或高于现行的大多数算法,且基于此算法能同时处理约束线段和约束区域相关的多种约束数据类型.

On Application of Improved Triangulation Algorithm of Constrained Dataset

Based on studying the factors which influence the efficiency of point-by-point-inserting algorithm, this article optimizes the algorithm about enveloping box, empty circum-circle test algorithm, the algorithm of fast finding the triangle which the point is in and the algorithm of fast finding the edge which is intersected with the constrained line. And an optimized algorithm, whose the efficiency is close to and is higher than the others, is presented. Meanwhile based on the optimized allgorithm, more constrained data about constrained line and constrained region can be disposed.