Research Of DEM Generation And Visualization Based On Triangulation

Digital Elevation Model (DEM) is one of the important parts of the geographic information systems, which has a wide range of applications in terrain analysis, constructing project, emulating battlefield environment and many other fields. DEM includes Grid, Triangulated Irregular Netting (TIN) and Contour. TIN is regarded as the most basic and important model in the DEM. Revolving around the DEM Generation based on TIN, this thesis researchs mainly on the Algorithm of Delaunay Triangulation for the scattered points, Delaunay Triangulation with constrained edges and Delaunay Triangulation for the arbitrary polygon, as well as the mesh simplification based on triangle collapse.At the aspect of the algorithm of Delaunay Triangulation based on scattered points, this thesis, on the basis of the insert algorithm, sets up a virtual grid, separates the original discrete points into sub-block, and introduces the algorithm of rapid point positioning, so that the high efficiency of triangulation can be guaranteed.As the aspect of Delaunay Triangulation with constrained edges, we insert the constrained edges to original triangulation netting. According to the shortcoming of the diagonal line exchange algorithm which is based on convexo-concave, this thesis proposed an idea of "split -restraint" to improve the robustness of the algorithm.As the aspect of Delaunay Triangulation for the arbitrary polygon, according to the principle of "the biggest angle", this thesis improved an algorithm for the arbitrary polygon Delaunay triangulation based on directed edges, which can rapidly improve the efficiency of the algorithm, avoid the possible wrong results of the "irregular position" and improve the robustness of the original algorithm.At the aspect of the mesh simplification, on the basis of triangle collapse, this thesis presented an algorithm of triangle collapse simplification based on Local Region Area Measure to change the order of the triangle which will be folded,so that the simplified model is more close to the original mesh.