The Construction And Application Of Triangulated Irregular Network(TIN)

Digital Terrain Modal(DTM) as a technology to identify map information. It is widely applied in GIS, terra study, computer graphics and virtual reality etc. Triangulated Irregular Network(TIN) is one of the most extensive form of DTM, already been deeply studied domestic and foreign. Many experts and scholars had made a large number of studies on the Construction of Delaunay TIN, made several more mature algorithms such as, divide-and-conquer, point-by-point insertion and triangulation growth method. divide-and-conquer method due to the high use of recursive algorithm, the tremendous volume of data, the computer more powerful. The time complexity is poor and the speed is slow with Traditional point-by-point insertion method, when the volume of data is large. Triangulation growth heavily involved with the searching of nearest point to the target point, the efficiency is low with a larger volume of data the same.With the enhance of application requirements, often encounter the need of DTM modeling for a large area or complex terrain, and more and more areas that need a more efficient, more powerful, more expansible digital terrain modeling system.This paper summarized the DTM domestic and foreign research results,analyzed the advantages and disadvantages of various algorithms in detail, improved point-by-point insertion method and achieved better efficiency, through my own innovation of existing research results. It can process with a large area of modeling efficiently, the data volume can reach one billion, the speed can reach processing over 200,000 discrete points per second with ordinary computers. The usage of concise and comprehensive data structure is to ensure a good expansibility. As the triangulation efficiency improvement and the powerful of the DTM system, the scope and level of the application has been enhanced.The innovational points are: 1. The application of stack recursion circumcircle checking in TIN Construction algorithm improved the efficiency of the traditional algorithms.2. STL technology, provides professional and efficient management of computer resources and basic algorithms, focused us on the algorithm improvement research.3. Integrated application of several existing efficient technologies.4. Application of surface fitting in site formation.