The Construction of Delaunay Triangulation Using Point-insertion Method Based on Qi Algorithm

Delaunay Triangulation has a wide range of application in various fields,and it is very important to generate Delaunay Triangulation efficiently.After analyzing the procedure of construction of Delaunay Triangulation without control boundary using point-insertion method,the authors introduced the Qi algorithm to the key step of building node-topology.The Qi algorithm was adopted again when inserting constrained boundaries into the Delaunay Triangulation to improve the efficiency.In order to verify the algorithm presented in this paper,the authors implemented algorithms using C in VS.NET.The experiment shows that the introduction of the Qi algorithm can improve the efficiency of building Delaunay Triangulation using point-insertion method.