约束Delaunay三角网生成算法及其应用研究

论文摘要

三角网剖分技术在地质学、计算几何学、图形图像学和生物医学等众多领域得到广泛的应用。三角网剖分技术能够快速构建模型,在实际工程中有着良好的表现。特别是约束Delaunay三角网是被认为三角剖分中最优的并且它使用原始数据建模,更能准确地客观地反应真实信息,具备了其他算法不可比拟的优越性。一直以来是众多学者研究的热点问题。由于当前构建约束Delaunay三角网的算法在影响域为凹多边形的情况下,算法不是很稳定,甚至失效,对约束的Delaunay三角网生成算法的研究具有重要的意义和应用价值。本文具体研究内容如下：1.本文研究了网格剖分技术的相关知识、凸壳技术、Voronoi图、非约束的Delaunay三角网构造算法以及约束的Delaunay三角网构造算法,分析了当前约束的Delaunay三角网剖分算法的缺陷,提出一种基于对角线交换改进的算法。在利用逐点插入算法构建Delaunay三角网时,采用了STL中类库,有效地缩短了构造三角网的时间。2.研究了约束条件的嵌入过程,通过给出约束点和约束线段的接口能够使约束条件动态插入。3.分析了约束边影响域为凹多边形的算法失效的问题,引入线段的非端点相交判断和凹多边形后置处理的方法,完成构建约束的Delaunay三角网过程。通过实验表明,该算法能够有效地解决影响域为凹多边形的约束Delaunay三角剖分,算法效率高,健壮性强。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 论文背景及其研究意义
• 1.2 国内外研究现状及其前沿发展趋势
• 1.3 本文研究内容与目标
• 第二章 三角剖分相关概念和基本理论
• 2.1 引言
• 2.2 离散点
• 2.3 网格
• 2.4 凸壳
• 2.4.1 凸壳概念
• 2.4.2 凸凹性判断
• 2.5 Voronoi图和三角剖分
• 2.5.1 Voronoi图
• 2.5.2 三角剖分
• 2.6 本章小结
• 第三章 约束Delaunay三角剖分算法研究
• 3.1 引言
• 3.1.1 Delaunay三角网及其特性
• 3.1.2 基本准则
• 3.2 Delaunay三角网生成算法分析
• 3.2.1 分治算法的分析
• 3.2.2 逐点插入法算法分析
• 3.2.3 三角网生长法的分析
• 3.3 约束边嵌入算法分析
• 3.3.1 加入附加点的算法
• 3.3.2 不加入附加点的算法
• 第四章 基于对角线交换的改进算法及其实现
• 4.1 引言
• 4.2 算法流程
• 4.3 数据结构
• 4.4 算法的实现过程
• 4.4.1 数据的预处理
• 4.4.2 构建Delaunay三角网
• 4.4.3 判断线段相交
• 4.4.4 影响域的确定
• 4.4.5 对角线交换过程
• 4.5 算法测试结果
• 4.6 算法分析
• 第五章 三角网系统及其应用
• 5.1 系统简介
• 5.2 系统设计
• 5.3 三角网的应用
• 5.4 三角网系统实验结果
• 5.4.1 扳手模型实现过程
• 5.4.2 半岛的地理位置模型实现过程
• 5.4.3 钥匙模型实现过程
• 第六章 总结与展望
• 参考文献
• 致谢
• 研究成果及发表的学术论文
• 作者和导师简介
• 硕士研究生学位论文答辩委员会决议书