An Improved Delaunay Triangulation Algorithm

The Delaunay triangulation is an important content of data expression, management and integration of Geographical Information System(GIS), and it is also an effective method and tool for terrain visualization. The majority of scholars are attracted to doing research on it because of its significance and important role, such as visualization in scientific computing, geo-analysis, map generalization, virtual reality, computer vision and so on. However, the efficiency becomes a bottleneck for Delaunay triangulation.Due to good properties such as empty circumcircle and maximizing the minimum angle, the Delaunay triangulation was regarded as the best one during the modeling of Triangulated Irregular Network(TIN). And it can adapt to the regular and irregular distribution of data, and can also handle special terrain flexibly. A new fast Delaunay triangulation algorithm is proposed after the traditional algorithms are compared and analyzed in this paper, mainly focusing on the point location algorithm and the incremental inserting algorithm of Delaunay triangulation. The key contributions of our work can be summarized as follows:(1) Through research and analysis of drawbacks of the existing insertion point location algorithms, a new hybrid point location algorithm is proposed to solve the problem of low efficiency in point location. Merging the coordinate of triangle area algorithm and the walking straight algorithm, the searching path can be shortened significantly in the process of point positioning, and the inserting point of target triangle can be navigated quickly.(2) To solve the problem of low efficiency in Delaunay triangulation, a fast algorithm for building Delaunay triangulation based on grid division is proposed. Firstly, a dynamic rectangular bounding box is established. Secondly, the original discrete point data are sorted by grid division, and using the hybrid point location algorithm proposed in this paper to quickly locate target triangle during the process of the Delaunay triangulation. Finally, a simple empty circumcircle test is used to do a LOP(Local Optimization Procedure) so that the Delaunay triangulation is more efficient.Some experiments were done to test and verify the proposed algorithm in this paper. Experimental results show that the improved algorithm is not only simple and effective, but also very useful.