Algorithm of inserting any constrained line into Delaunay triangulation

Constrained Delaunay Triangulation is widely used in Geographic Information System,geo-science,surface object reconstruction,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 triangulation,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.