Create TIN Base On The Discrete Points With Constraints

DEM can be expressed in three kinds of methods which are grid, Triangulated Irregular Netting (TIN) and Contour. Because TIN can present the surface of terrain by different resolutions, it is the most important and basic model in GIS. So the algorithm of Delaunay Triangultion based on scattered points in some constricted condition is studied in this article.First of all , the article contrasts with research on all kinds of algorithms of Triangulated Irregular Netting (TIN) .Among the possible triangular net, the Delaunay triangular net is Consided as the best Triangulation triangular net in the terrain fitting aspect. It is one kind of next mutually and mutually not overlap triangle set, in which any triangle's circumcircle does not contain other triangles' spot. So the article uses TIN to model DEM.Secondly, a composition algorithm to create Delaunay triangular network is raised ,which combining advantage of the Divide-Conquer Algorithm and advantage of Convex hull algorithm . in the algorithm, we make the discrete points sort in scan manner, in each leaf node's data set of points, uses Convex hull algorithm to create the Triangulated Irregular Netting , And then , Merges all node region according to the order of hierarchy traversa. By analysis, The time s complexity of this algorithm is O(nlogn).Finally, inserting constrained edge is used to Expresses Delaunay Triangulation in the constrained data field. Two steps are widely used at present; it's a one kind of efficiency method in inserting constrained edge.