Research on Algorithm of Target Triangles Fast Locating in Delaunay Triangulation

摘要

Delaunay triangulation construction is a hotspot but hard problem in 3D terrain visualization field. Based on an incremental insertion algorithm and block management of discrete points, discrete points of every block were pre-processed by sorting with rows in this paper. A method of using directional line that linked current and next inserted point was introduced to judge quickly which were the target triangles. By this method, triangles which directional line went through were decreased, and the situations that directional line went through vertexes and overlapped with edges of triangles were avoid. The results of experiment show that the algorithm, which has advantages of less calculation and short time consumption, effectively improves the efficiency of constructing Delaunay triangulation.