Study And Application Of Three-dimensional Delaunay Triangulation Algorithm

Delauany, as one of the research contents in the computation geometry, has been widely applied into the filed of medical visualization, GIS and Computer Graphics. At present, Delauany in 2d has already made some progress, however, many algorithms cannot be directly spread to 3d field. Therefore, the research and improvement aimed at Delauany algorithm not only has the great theoretical significance but also the great application value.On the basis of understanding the related theories to 3d Delauany, this thesis aims at making research on the generating algorithm by the method of comparison and analysis of the advantage and disadvantage of the present Delauany Triangulation algorithm. At the same time, a detail explanation is given to the process of adopting the combining algorithm in order to overcome the defect existed in the classical generating algorithm. This thesis also puts forward the improvement method of algorithm of local optimization by making use of 3D Flip in the process of Delauany Triangulation. Meanwhile, after making research on the 3d Delauany flip algorithm, the thesis proposes an improved points location search method,and designs a reasonable and effective data structure,so that the internal memory is saved. Overall the performance of algorithm is also improved.In order to verify the feasibility and effectiveness of the algorithm, this thesis takes use of the application examples of three-dimensonal space of Delauany in the aspect of graphic process,based on the VTK+VC++6.0 development platform to achieve the whole algorithm and give a explicit analysis to the reasults of algorithm. The results show that the improved algorithm is practicable.