A method of Delaunay triangulation based on grid and direction index

Delaunay triangulation has been widely used in terrain expression,surface reconstruction,digital city and other GIS areas.In Delaunay triangulation network construction algorithm the common-seen point by point interpolation algorithm is simple and flexible,but its efficiency is bound by looking for triangle. A method based on virtual grid index and direction method is used to improve the index of triangle and point positioning algorithm,which can effectively improve the efficiency of triangulation building. Experiments prove that this method needs a lower computer hardware configuration,but outputs high efficiency,and builds the Delaunay triangulation effectively.