Triangulation Method. Scattered Data Study

This thesis seeks to validate an effective approach to the method of the triangulation form 3D scattered points. A low computational complexity and high mesh quality algorithm has great application merit in the research of computational geometry, surface reconstruction and visualization of 3D data.At first, the typical 2D and 3D triangulation algorithm of scattered points is discussed in this paper. Then, a space partition strategy with its corresponding data structure and encoding method is proposed by the author in order to improve the triangulating and searching efficiency according to the trend of larger and larger points set. The direct triangulation algorithm from 3D scattered data which greatly improved the triangulating efficiency and mesh quality based on the local incremental mesh generation method is described in the third chapter. The computational complexity of this algorithm is O(N). The concept of inner-connection andout-connection is firstly put forward in this paper. This paper also analyzed some key problems in 3D triangulation from scattered points. New determining principles for the relationship of point and line in space and for convexo-concave vertices of space polygon is discussed which corrected the previous method and can be applied in space triangle mesh. At the end of this papar, the future research areaes of triangluation from 3D scattered points are demonstrated.