Abstract: Local adjusting is needed in two-step constructing constrained Delaunay Triangulation when inserting con-strained 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.

Key words: constrained delaunay triangulation (CDT), triangulation, local adjustment algorithm, binary sort tree

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

关键词: 约束Delaunay三角网, 三角剖分, 局部调整算法, 二叉排序树