基于凸壳技术的Delaunay三角网生成算法研究

摘要

As an important expression of DEM, the generation algorithm of TIN drew people' s attention. the principle of traditional generation algorithms according are summarized and analyzed to there characteristics, described the principle and method to establish TIN with the convex hull. In accordance with the state that many of computational geometry books simplified the process of building the convex hull by limiting points, this paper shows an improvement in the process of forming a convex hull. The improved algorithm, which eliminates the repeat point when the points are sorting; it also eliminate co-line in the process of constructing new convex hull. When all the points are contained in the convex hull, the process of establishing the triangulation is completed. LOP optimization based on the triangle public edge which makes all the triangles satisfy the rule of the Delaunay triangulation.Through tests, its running speed faster than the traditional generation algorithms, at the sane time, the improved algorithm can deal with some particular cases, such as repeat points, three points are on a straight line.%TIN作为DEM的一种重要表达模型,其生成算法一直备受关注.首先对传统的生成算法原理进行总结,并针对其特点进行了分析,对利用凸壳建立TIN的原理和方法进行简单描述.由于许多计算几何学对点集进行限制以简化凸壳的建立过程,对凸壳的生成过程进行了改进.在点集的排序过程中剔除重复点,将点联入原凸壳过程中,排除共线这一特殊情况,建立新的凸壳,直至所有点都被包含在凸壳中.至此,三角网建立完毕.通过对三角形公共边进行LOP优化,使其满足Delaunay三角网的特性.当所有三角形满足特性时,Delaunay三角网构建完毕.该算法的优势在于构网速度较快,并能够对重复点进行处理,同时在生成网的过程中对共线这种特殊情况进行处理.