An Algorithm for Building Delaunay Triangulation of High Efficiency

An algorithm for building delaunay of high efficiency on the ground of terrain application is presented.At first,the large scale discrete points are divided by quad tree with a special scope.Secondly,for the every child block whose attribute is leaf type to construct the triangulation net based on convex technology,then the child blocks which have the same parent are combined.Lastly,through optimizing the triangulation net,the triangulation has been to delaunay triangulation,result indicates between the policy of quad tree and the policy of average to divided the points,the former has the higher efficiency in the same algorithm.