基于TIN地形模型生成与简化算法研究与实现

摘要

数字高程模型作为“4D”产品之一已经在测绘、遥感、环境规划、土木水利工程、地学分析等领域有了广泛的应用。针对数字高程模型现有的等高线模型、规则网模型和不规则三角网模型等三种建模方法，实际应用中不规则三角网模型能够更好的可视化地形特征。对地形建模归结于 Delaunay三角网(以下简称D-TIN)构网，选择D-TIN中逐点插入算法在应对高速地形模型建模以及随机添加离散数据点构网具备更好的灵活性，然而其算法实现效率低，本文对地形模型生成算法与简化算法进行改进提高其渲染效率。本文的主要研究工作包括：
　　（1）在离散数据点的 Delaunay三角网生成方面，采用基于初始包容壳的改进凸包方法，建立最优初始包容壳，提出双凸包技术。对原始离散点进行多级网格自适应分块，研究了“网格-点-三角网”的索引方法，优化离散点的插入顺序，并设计了快速定位算法。在建立初始包容壳算法上，更加完善郝建强提出的利用正负划分建立凸壳；在定位点在三角网格中的位置时采用快速点定位算法；通过以上改进明显提高了D-TIN的构建效率。
　　（2）地形模型简化方面，采用基于渐进网格（PM）算法，对边折叠后新顶点位置的确定、网格模型中边界顶点和边界边的处理以及累进网格二义性的判断做出了改进，同时，在二次误差度加入曲线曲率的权值作为新的误差测度。改进后的网格模型简化算法能够有效保持原始网格模型的细部特征，保证了简化过程中网格拓扑关系的正确性，提高了简化后网格模型的质量。
　　（3）对本文改进的地形模型生成与简化算法分别进行系统仿真实验，分析并验证其有效性、高效性。

目录

封面

声明

中文摘要

英文摘要

目录

第1章 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.3 研究组织结构

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

2.1 Delaunay三角网的定义和性质

2.2 经典的Delaunay三角网生成算法

2.3 基于双凸壳技术的Delaunay三角网生成算法

2.4 改进算法的主要数据结构与算法实现

2.5本章小结

第3章基于PM算法的网格简化算法研究

3.1 地形模型简化技术

3.2 PM简化算法实现过程

3.3 改进的PM算法

3.4 改进算法的主要数据结构与算法实现

3.5 本章小结

第4章 系统仿真及实验

4.1 改进地形模型生成算法的仿真及实验

4.2 算法的时间复杂度分析

4.3 改进地形模型简化算法的仿真及实验

4.4 本章小结

第5章 总结与展望

5.1 总结

5.2 展望

致谢

参考文献