A Study Of Efficiently Dynamic Updating Algorithm And Experiments For Tessellation By Triangulation Of Huge Data Sets

There are many means of DEM (Digital Elevation Model) presentation. In these presentations, the tessellation of triangulation for DEM is the best way. Because of the complexities about the theory for tessellation of triangulation and software development, the application is limited. For example, how to collect manually the DEM data in triangulation way under the on-line stereo mode is very difficult to solve.This paper is based on the applications like above. The primary content and creativities are:1. The concept of tessellation generated by triangulation is illustrated, and characteristics, and application range. Actualities and disadvantages of traditional algorithms about Delaunaytriangulation are summed up-the algorithms are prototype of concepts, difficult todevelopment, and are difficult to adapt to the large date-sets, randomized points. Further more the algorithms cannot support efficiently dynamic updating as well as.2. After studying the theory about tessellation of triangulation well, especially about Delaunay triangulation, so the three conclusions of Delaunay triangulation characteristics are: max-min angle, geometry degradation of points fitting max-min angle and Delaunay cavity to local reconnection. The designe of algorithm is based on these conclusions later. Especially the local reconnection could fast the algorithm running.3. Aiming at how to build efficiently a Delaunay triangulation which is a best optimal space structure and to edit the tessellation (adding and deleting a vertex), A randomized incremental algorithm is designed which are flexible to huge data-sets and dynamic editing. The space complexity is O(n), and time complexity is O(n log n). The average for searching a geometry object is O(log n). This conclusion makes out the algorithm is the best optimization in kindred algorithms. So the algorithm is worth to development.4. After coding, the development of Delaunay triangulation software package is completed, and the software package is tested completely. The result of testing is consistent with the analysis of algorithm. The number of randomized generated points is from 10,000 to 100,000. The statistics of running time of building tessellation, time of inserting and deleting a vertex in the tessellation are presented. The algorithm is well flexible to points in an extra function circle, etc. So the software package is robust.5. The two successful use case -DEM data collection in tessellation generation byDelaunay triangulation and DEM format transformation, are well described. Comparing the commercial software, the accuracy and running efficiency are better. So the software performance is worthy to apply. 6. Summarizing the content, Viewing to the qualification of Delaunay triangulation technology and pointing the function of software to development in the future.