Digital Elevation Model Tin And Contour Modeling

With the development of Geographic Information System (GIS), Digital Elevation Model (DEM) has become an important part of spatial information system, and one of the best important and basic data in these fields, such as constructing project and emulating battlefield environment. DEM includes Grid, Triangulated Irregular Netting (TIN) and Contour. Because TIN can present the surface of terrain by different resolutions, TIN is regarded as the most important and basic model in GIS. Moreover, TIN to Contour and Contour to TIN are basic methods of modeling DEM. This thesis mostly researched on the algorithm of Delaunay Triangulation, the algorithm of constructing and disposing contours based on TIN, and the algorithm of constructing TIN based on contours.At the aspect of the algorithm of Delaunay Triangulation based on scattered points, the Delaunay triangulation algorithm whose time complexity is O(nlogn) was presented based on optimizing the constructing method of convex hull. The algorithm firstly makes the discrete points sorted, and secondly it constructs convex hull and triangulates the sorted points by the relation between new inserted point and the convex hull constructed, and finally it optimizes triangles utilizing topological structures of directed edges. The algorithm avoids the intersection test of point, and moreover, the average testing times of a newly added point is under 4, so that the high efficiency of triangulation can be guaranteed.At the aspect of the algorithm of extracting and disposing contours based on TIN, this thesis carried out the process of extracting contours in an area with arbitrary boundaries based on TIN with complete topological structure, and perfected the algorithm of adding elevation annotation automatically to contour map by studying the location and density of annotations based on the people's habit of reading maps, and dealt with the problem of smoothing contours by using Tension Spline Function which can dealt with the intersection problem of contours. At the aspect of the algorithm of constructing TIN based on contours, in the purpose of guaranteeing that TIN can contain information of geometry and elevation of high quality, this thesis firstly made contours to discrete points, secondly constructed TIN based on these discrete points, finally inserted contours as constrained edges to original triangulation netting. This thesis presented "Inserting-Swapping" constrained edge algorithm by combining the inserting thoughts and the swapping thoughts. A corrective algorithm of flat areas presented replenishes the corrective algorithm of searching flat areas, and can guarantee that TIN whose flat areas were corrected simulate the real shape of the surface farthest and can improve the speed of correcting flat areas by the method of divide inner flat triangles at the instance of having no use of terrain characteristic lines.The results of many groups of terrain data which were computed by the software which was programmed by the author prove that these processes and algorithms presented in this thesis can realize the purpose of modeling TIN and contours at high speed and high precision.