二维Delaunay网格生成算法研究

论文摘要

众多科学与工程实践中的复杂的物理现象都会用偏微分方程描述。当方程的初、边值条件过于复杂或计算区域过于复杂使我们无法得到真实解时,得到一个可靠的数值近似就很重要。在偏微分方程的数值计算方法中,从有限差分、有限体积到有限元都要依赖网格剖分。网格依据其拓扑结构的规律性可分为结构网格与非结构网格。结构网格在存储、操作上的简单性以及在计算中的高效性并不能弥补其对复杂区域的不适应性,因此非结构网格是复杂区域剖分的一个常用选择,其生成算法可大体分为Delaunay、阵面推进、四叉树三类。不是所有的网格都适合进行数值计算,质量很差的网格能导致计算的速度很慢甚至计算崩溃。因此,研究高质量、高效率的网格生成算法很有必要。Delaunay类型的网格及其生成算法具有坚实的数学理论基础,故选择该方法进行深入分析与研究,所做工作如下:1、深入讨论了二维Delaunay网格生成过程的各主要步骤的不同算法,并针对约束边的恢复问题设计了一个约束边恢复算法,证明其收敛性,还进行了计算复杂度估计,理论与实验均证明该算法可以有效减少高代价的相交测试的次数。2、对网格生成过程中解决同一问题的不同算法进行分析评价,并编写代码进行了实验比较,根据实验结果选择较好的算法添加进我们最后的程序中,得到了比较高效、稳健的二维Delaunay网格生成程序。3、开发了一个从数字图像中提取感兴趣区域,并对得到的图形生成二维Delaunay网格的算法。实验表明该算法能成功捕捉由图像表示的复杂区域的重要特征,并对得到的区域生成高质量的二维Delaunay网格。4、本文第四章还将自己的工作与别人的类似工作进行了实验对比。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 数值方法与非结构网格
• 1.2 Delaunay 网格及其生成算法的历史、现状与应用
• 1.3 研究的方法与思路
• 1.4 本文的主要工作
• 第二章 二维Delaunay 网格生成
• 2.1 基本概念与问题的描述
• 2.1.1 基本概念与性质
• 2.1.2 网格生成问题的表述约定
• 2.2 网格生成程序的稳健性
• 2.3 Delaunay 三角网格生成算法
• 2.3.1 点集的Delaunay 三角剖分算法
• 2.3.2 约束边的恢复算法
• 2.3.3 域外三角形的剔除与Steiner 点的添加
• 2.4 二维Delaunay 网格生成中的其它问题
• 2.4.1 平面直线图的离散与狭小角的处理
• 2.4.2 网格的后续优化与处理
• 第三章 基于数字图像的二维Delaunay 网格生成
• 3.1 相关基本概念
• 3.2 从数字图像到PSLG
• 3.2.1 全局阈值的计算
• 3.2.2 平面直线图的获取
• 第四章 网格生成数值实验
• 4.1 第二章 算法程序的实践表现
• 4.2 第三章算法程序的实践表现
• 结论与展望
• 致谢
• 参考文献
• 作者在学期间取得的学术成果