Construction And Visualization Methods And Implementation For Elaunay Triangulation

TIN (Triangulated Irregular Network) is a series of consecutive triangular network byusing the scattered points, the size and shape of the triangular network depends on thelocation and density of scattered points. The Delaunay Triangulation was regarded as thebest network in the TIN modeling, it can adapt to the regular and irregular distribution data,and can process special terrain flexibly. Therefore, this thesis mostly researched on theconstruction of commonly Delaunay Triangulation and Constrained DelaunayTriangulation, three-dimensional terrain visualization based on the Delaunay triangulationand terrain mesh simplification based on triangle collapse.At the aspect of the algorithm of Delaunay Triangulation based on scattered points,this thesis focused on the incremental insertion algorithm, introduced and improved thefast point location algorithm in order to solve the insertion point positioning problem, sothat the high efficiency of constructing can be guaranteed.At the aspect of Constrained Delaunay Triangulation, this thesis used the previouschapter’s algorithm to construct initial triangulation, then inserted the constrained edges init. For lacks of the "Insert-Exchange" algorithm, this thesis added processing of tangentpoint to make it more robust.Because of Delaunay Triangulation can not vividly and intuitively express the terrain,this thesis completed three-dimensional terrain visualization based on the DelaunayTriangulation, by using Direct3D graphics library based on VC++developmentenvironment.Finally, at the aspect of terrain mesh simplification, this thesis introduced normalvector metric, and added a boundary judgment to achieve a simplified terrain model byusing the Direct3D function of calculating the normal vector automatically.