Delaunay三角网中任意约束线段嵌入算法研究

Algorithm of inserting any constrained line into Delaunay triangulation

约束Delaunay三角网在地理信息系统、地学分析、表面对象重建、数字城市、虚拟现实等领域有着广泛的应用。约束线段嵌入是解决由Delaunay三角网转变为约束Delaunay三角网的一种有效的方法。本文重点研究约束线段嵌入Delaunay三角网的问题,通过分析约束线段与原三角网之间的关系,给出各种情况的约束线段的预处理方法,以迭代算法为基础,描述了任意约束线段嵌入Delaunay三角网的过程。

Constrained Delaunay Triangulation is widely used in Geographic Information System, geo-science, surface object re- construction, digital city, virtual reality and other fields. It is an effective method of changing Delaunay Triangulation into Constrained Delaunay Triangulation that constrained line is inserted into Delaunay Triangulation. This paper focused on the problem of inserting constrained line into Delaunay Triangulation, and by analyzing the relationship between the constrained line and the original triangula- tion, gave the pretreatment method of various kinds of constrained lines, and described the process of inserting any constrained line into Delaunay Triangulation based on the iterative algorithm.