Research And Implementation Of The Delaunay Suturing Algorithm On Contour Lines

In the recent years, with the rapid development of Geographical Information System(GIS), Digital Elevation Model (DEM) has been widely applied in sorts of fields likeengineering construction, environment resources and military as an important part of3Dspatial information system. DEM is the core data in terrain analysis. And the demand of itsacquisition, storage and processing speed is getting higher and higher. There are mainly threemodels of DEM such as Regular Grid model, Irregular Triangulation Network model (TIN)and Contour model. Among these three models, TIN model has become the common model toestablish DEM because it could avoid data redundancy in the flat terrain, and in the mean timeexpress the characteristics of elevation according to the features and variation of the terrain.Thus, to create an efficient DEM, making it not only apply to massive data but also meet thepractical need of people and using it in more extensive geological areas, the research of TINgeneration method is vital important.This thesis mainly focuses on the discrete points based generation algorithm of DelaunayTriangulation Network to establish TIN model. A method was put forward in this paper, whichwas to establish the network block by block with the improved Incremental InsertionAlgorithm, and to suture the blocked networks. What’s more, the model was applied toimplement the visualization of3D terrain which was based on OpenGL.Firstly，the experimental data was obtained through DXF-file. The3D data on thecontour lines was read and homogenized. Then the block-number was selected or input by thedialog interface. And the blocked data was stored in txt files block by block. Secondly,Delaunay Triangulation Networks were built according to the blocks, and the flat triangles ofevery network were converted after that. Thirdly, by searching and accessing the suturingedges, the suturing points were clockwise stored and divided into four parts according to fourdirections like top, right, bottom and left. In addition, the up and down blocks were sutured inthe horizontal direction, after which the left and right blocks were sutured in the verticaldirection. Finally, by optimizing the sutured triangulation network with the Local OptimalProcedure (LOP) algorithm, and converting the flat triangles, the Delaunay Triangulationmodel was established at last. To sum up, the research showed that the method presented in the thesis combined the advantages ofthe Incremental Insertion Algorithm and Divide-and-conquer Algorithm. The method is easyto understand and its time complexity is close to linear. In conclusion, it’s a really practicalalgorithm.