Delaunay三角形网络逐点插入法的优化算法

Delaunay三角形网络逐点插入法虽简单易行,但效率低下。针对其效率低下原因,提出一种改进的Delaunay三角形网络逐点插入生成算法。将已知插入点X坐标大小排序,当X坐标相等时,以Y坐标大小顺序排序构建新的插入点顺序,并得到插入点坐标集合中的最大值和最小值。适当放大插入点坐标中最大值、缩小坐标最小值后,得到X、Y坐标新的两个最大值和两个最小值,用4个值构建4个临时新插入点,可以构建出Delaunay三角形网络矩形的凸壳。按照新的插入点顺序逐点插入构建三角形网络,只判断插入点与以X坐标最大的两个边界矩形顶点为顶点的三角形位置关系。生成三角形网络后删除与4个临时顶点相关的三角形,就是所需要的三角形网络。通过证明每个插入点必定落在X坐标最大的两个边界矩形顶点为顶点构成的三角形上,可以减少插入点与已生成三角形位置关系的判断次数,较大程度提高逐点插入法的效率。将新算法与常规算法计算复杂度比较,结果表明,改进的算法能提高逐点插入效率,运算量稳定,达到逐点插入法的最好水平。

Optimization Algorithm for Delaunay Triangulation Point Insertion Method

Although Delaunay triangulation network insertion is simple, but inefficient. As the low efficiency concerned, an improved Delaunay triangulation incremental insertion is proposed. Sort known insertion by size on X coordinate, when equaled on X coordinate, new insertion sequence is set up by size on Y coordinate, maximum and minimum on insertion coordinates collection are obtained. Appropriately enlarge the maximum and reduce the minimum on insertion coordinates, two new maxima and minima are obtained on X, Y coordinates, Delaunay triangle network rectangular convex hull can be constructed with four new temporary insertion point by using of the former four extreme values. A triangle network is built in the new insertion order to determine the triangular position relationship between the insertion point and the two largest on the X coordinate of the vertex of the bounding rectangle vertices. After deleting the generate triangle vertices associated with the four temporary triangle, triangle network we needed is obtained. By proving each insertion point absolutely fall on the two largest X coordinates of the bounding rectangle vertices of the triangle vertices, the times that determine the positional relationships between insertion point and generated triangles is reduced and the efficiency is improved greatly. By comparing the computational complexity of the new and traditional algorithms, results show that the improved algorithm makes incremental insertion more efficient, operation more stable and by which the best effect of incremental insertion can be achieved.