基于格网和方向法索引的Delaunay三角网生成算法

A method of Delaunay triangulation based on grid and direction index

Delaunay三角网在地形表达、表面对象重建、数字城市等GIS领域有着广泛的应用。常见的三角网构建算法中的逐点插入法算法简单、灵活,但是其效率受查找三角形的约束。文中提出一种用虚拟格网索引和方向法相结合的方法,改进对三角形的索引、对点定位的算法,能有效提高构建三角网效率。通过实验证明,这种方法对计算机硬件配置要求较低,且效率高,构建Delaunay三角网的效果好。

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.