论文摘要
三角网格数字高程模型（Digital Elevation Model,DEM）是DEM众多表达形式中最科学的表述方法之一,但由于其相关理论和软件实现的复杂性,导致应用受限。如大部分国内数字摄影测量系统中的三角网格DEM立体“在线”动态采集、编辑就是一个亟待解决的问题。本文正是从这类应用需求出发,开展的主要研究内容和创新点如下;1.阐明了三角网格的概念、特点和应用范围。总结了Delaunay三角网格构建算法的现状和存在的问题;现有相关算法普遍为概念性算法,实用性不强,不能同时满足对大数据量、点位随机分布的适应性,不满足高效动态编辑等实用要求。2.对涉及三角网格,尤其是Delaunay三角网格的相关理论进行了深入研究,总结出了Delaunay三角网格的三大特性;最小角最大（max-min angle）,几何位置退化点集仍满足最小角最大,冲突区域（conflict area）与局部重连（local reconnection）。这对后序的算法设计具有理论指导意义,其中局部重连特性为影响算法执行效率的瓶颈部分给出了优化方法的理论依据。3.根据需求要点,针对如何快速构建空间结构最优的Delaunay三角网格以及在已有三角网格上如何高效编辑（增加、删除顶点）,结合几何理论和随机算法理论,提出了一种增量式随机动态Delaunay三角网格构建算法,算法过程完整而翔实。该算法具有大数据量适应性,随机性,高效动态编辑等特性,并对算法的性能进行了全面分析;算法中所涉及的数据结构空间复杂度为“线性阶”O（n）;网格构建算法时间复杂度为“次方阶”O（n log n）,三角形单元或网格顶点检索时间为“对数阶”O（log n）,这一复杂度是“查询检索”这一类问题的最优解。分析结果表明;算法具有实现价值。4.编写程序对算法予以实现,设计、开发了Delaunay三角网格相关功能软件包,并对软件进行了全面严格的测试实验,测试结果印证了算法分析结论的正确性。实验中选用三维空间中的10,000～100,000随机分布点集测试了构网速度,统计了单点插入和删除时间;用点位分布符合圆等特殊函数曲线的点集测试了软件对几何退化情况的适应性,结果正确,整个测试过程验证了软件的健壮性。5.介绍了有关软件包的两个应用示例——立体在线三角网格DEM动态采集、编辑和DEM格式转换,并与现有商用软件相关功能进行了比较,精度和执行效率均不亚于现有商用软件,初步展现了所开发软件包的应用价值。6.总结研究内容,对进一步的限定Delaunay三角网格剖分技术研究方向给予展望,对下一步软件开发所要实现的功能给予说明。