Algorithm for constrained Delaunay triangulation Based on boundary characteristic points acquiring

TIN is used abroad in terrain expression and Delaunay Triangulation is also used. The problem that Delaunay Triangulation in the constrained data field was dissatisfied for DT-characteristic was expatiated and three algorithms for extra points were analyzed. Algorithms just considered how to reduce the number of extra points from the geometrical view, but the final aim of extra points was to acquire actual terrain, so an algorithm for constrained Delaunay triangulation based on boundary characteristic point acquiring was proposed. The essential of algorithm was to acquire all characteristic points which could construct actual terrain and omits extra points, and then construct Delaunay Triangulation to ensure its third dimension.