An Improved Incremental Insertion Algorithm for Delaunay Triangulation

In this paper, we introduced the Delaunay triangulation network generating algorithm-incremental insertion-in detail. Then, we improved the most crucial steps of the algorithm via two aspects. The first one is to locate the point position by leveraging quad tree index and direction searching technique. The second one is to handle the initial network generation and the point insertion process by inserting points into the triangulation network from both internal and external of the convex hull. The experiment shows that the position method not only can accelerate the network generating, but also independent of the total amount of the point set; and the approach that insert points from external of the convex hull makes the insertion process more flexibility. The test result in different amount of the point set shows that the time efficiency of the improved algorithm is nearly linearity.