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

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