Study on the Algorithm for Two-Dimensional Random Point Insertion of Delaunay TIN
Dong Han-jun · Geography and Geo-Information Science · 2009
At present,there are many algorithms for the point insertion of Delaunay TIN,but their efficiency is low.There are many factors that restrict the speed of point insertion.The most important reason is how to locate point in the triangle.According to the number of arithmetic steps in the algorithm,the operating efficiency can be measured quantitatively.Firstly,in this paper,the point location algorithm of the shortest path was analyzed by using of the advantages of existing algorithms.The point location was done using harmonious blend algorithm,which is designed according the relation of point and directed line segment,center of gravity and coordinate of triangle area.Then,using the point location algorithm,the point would be inserted into Delaunay TIN.Finally,the analysis and test showed that the application of point location algorithm greatly improved the efficiency of point insertion.