带约束三角剖分算法的研究与实现

论文摘要

地学领域中表达地形信息的数据中包含大量山脊线、山谷线、断裂线、岛屿等地形特征,GIS工作者在充分考虑这类地形特征的情况下,发展了带约束条件的Delaunay三角剖分理论和算法。带地形特征约束的三角剖分是建立高精度数字地面模型的基础,在GIS、地学分析、多分辨率DTM、计算几何等领域中有着广泛的应用。阐述了带约束的Delaunay三角剖分的经典算法,研究了经典算法中的两步法,针对两步法的第一步,非约束Delaunay三角剖分中逐点插入算法的凸包包容盒算法,提出了一种边缘极值点求平面散乱点集凸包的算法。该算法利用极值点将平面点集划分为5个区,边缘4个区包含了所有凸包的凸点。通过求取边缘4个区的边缘子集的极值点,得到一个包含所有凸点的多边形点集,去掉凹点,得到平面点集的凸包。在两步法中的第二步嵌入约束条件的过程中,对约束线段的嵌入过程进行了分类,实现了带约束数据域的Delaunay三角剖分。对带岛屿约束数据域的Delaunay三角剖分算法进行了研究。在总结了前人研究成果的基础上,对带岛屿约束数据域的三角剖分算法进行了改进。改进算法的思想是:首先构建带岛屿多边形内边界约束的约束Delaunay三角网,然后利用边、面、弧段之间的拓扑关系,双向搜索查找岛屿内的三角形,进行相应的处理,完成带岛屿约束的Delaunay三角剖分。通过对实验结果的对比和分析,该改进算法具有更好的执行效率。通过对边缘极值点求平面散乱点集凸包算法和改进的带岛屿约束的Delaunay三角剖分算法的分析及与其它算法的比较,可以看出这两个算法在执行效率和效果上都有所提高,因此对两步法实现带约束三角剖分算法的构网效率有所提高。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 课题背景
• 1.2 研究现状
• 1.3 研究意义及主要工作
• 1.4 论文组织
• 第二章 非约束Delaunay三角剖分
• 2.1 Delaunay三角网及三角剖分
• 2.1.1 Delaunay三角网的有关概念及性质
• 2.1.2 常见Delaunay三角剖分算法
• 2.2 算法选择
• 2.2.1 包容盒的算法
• 2.2.2 离散点内插
• 2.2.3 LOP优化
• 2.3 凸包的改进算法
• 2.3.1 凸包的基本概念
• 2.3.2 凸包的经典算法
• 2.3.3 改进算法的原理
• 2.3.4 算法设计与实现
• 2.3.5 算法分析
• 2.4 本章小结
• 第三章 带约束线段的Delaunay三角剖分
• 3.1 带约束Delaunay三角网的有关概念及性质
• 3.1.1 CDT的数学定义
• 3.1.2 CDT三角网具有的性质
• 3.2 约束线段的嵌入算法
• 3.3 约束线段嵌入过程的分类
• 3.4 本章小结
• 第四章 带岛屿约束的Delaunay三角剖分
• 4.1 岛屿的基本概念
• 4.2 带岛屿约束的三角剖分的经典算法
• 4.3 改进算法的原理
• 4.4 改进的算法设计与实现
• 4.4.1 数据结构设计
• 4.4.2 算法的详细设计与实现
• 4.5 算法分析
• 4.6 本章小结
• 第五章 结论
• 参考文献
• 在学研究成果
• 致谢