基于二叉排序树的约束Delaunay三角网局部调整算法

Local Adjustment Algorithm for Constructing Constrained Delaunay Triangulation Based on Binary Sort Tree

在两步法构建约束Delaunay三角网过程中,向现有三角网中嵌入约束边时需要进行三角网的局部调整,对这一过程进行了研究,给出了一种对影响域进行重新剖分的二叉排序树算法。使用该算法在向三角网内嵌入约束边时,只需以影响域边界点在边界数组中的序号来构造一棵二叉排序树即可完成对影响域的剖分,并且可以利用生成的二叉树中各节点之间的关系迅速重构三角形之间的拓扑关系从而完成一次调整,该算法使用递归思想,简洁而高效。

Local adjusting is needed in two-step constructing constrained Delaunay Triangulation when inserting constrained segments into existing Delaunay triangulation. Some investigations on that process are made and a algorithm is proposed on binary sort tree which is using for reconstructing impacted areas. With this algorithm, the impacted area can be spitted easily by generating a binary sort tree with indexes of the points stored in a segments array, and after reconstructing the topological relationship of triangles according to the relationship of binary tree nodes, the adjustment is completed. Recursive logic makes the algorithm brief and effective.