Algorithm of Delaunay Triangulation Based on Optimal Convex Hull Technology
Jingjing Huang · Jisuanji gongcheng · 2007
A Delaunay triangulation algorithm based on optimal convex hull technology is presented.The algorithm makes the discrete points sort in scan manner,and secondly it constructs convex hull and triangulates the sorted points by the optimal convex hull technology which is proved by the author,and optimizes triangles utilizing topological structures of directed edges.The algorithm avoids the test of point of intersection.Moreover, the average test times of a newly added point is under 4,so that the high efficiency of triangulation can be sure.