《二维delaunay网格生成算法研究》由会员分享，可在线阅读，更多相关《二维delaunay网格生成算法研究（82页珍藏版）》请在金锄头文库上搜索。
1、 分类号 O24 学号 09020037 密级 公 开 理学硕士学位论文 二维二维 Delaunay 网格生成算法研究网格生成算法研究 硕士生姓名 梁 虎 学 科 专 业 数 学 研 究 方 向 Delaunay 网格生成算法 指 导 教 师 宋松和 教授 国防科学技术大学研究生院 二一一年九月 国防科学技术大学研究生院 二一一年九月 二维 D e l a u n a y 网格生成算法研究 国防科学技术大研究生院 A Study of 2D Delaunay Mesh Generation Algorithms Candidate：Liang Hu Supervisor：Song Songhe
2、 A dissertation Submitted in partial fulfillment of the requirements for the degree of Master of Science in Computational Mathematics Graduate School of National University of Defense Technology Changsha，Hunan，P.R.China September，2011 国防科学技术大学研究生院硕士学位论文 第 I 页 目 录 摘 要 i Abstractiii 第一章 绪 论 1 1.1 数值方法
3、与非结构网格.1 1.2 Delaunay 网格及其生成算法的历史、现状与应用.4 1.3 研究的方法与思路.6 1.4 本文的主要工作.7 第二章 二维 Delaunay 网格生成 9 2.1 基本概念与问题的描述.9 2.1.1 基本概念与性质.9 2.1.2 网格生成问题的表述约定.12 2.2 网格生成程序的稳健性.13 2.3 Delaunay 三角网格生成算法.15 2.3.1 点集的 Delaunay 三角剖分算法 .15 2.3.2 约束边的恢复算法.17 2.3.3 域外三角形的剔除与 Steiner 点的添加 .25 2.4 二维 Delaunay 网格生成中的其它问题30
4、 2.4.1 平面直线图的离散与狭小角的处理.31 2.4.2 网格的后续优化与处理.32 第三章 基于数字图像的二维 Delaunay 网格生成37 3.1 相关基本概念.38 3.2 从数字图像到 PSLG39 3.2.1 全局阈值的计算.39 3.2.2 平面直线图的获取.41 第四章 网格生成数值实验.45 4.1 第二章算法程序的实践表现.45 4.2 第三章算法程序的实践表现.52 结论与展望 63 致 谢65 参考文献67 作者在学期间取得的学术成果70 国防科学技术大学研究生院硕士学位论文 第 II 页 图 目 录 图 1 两类质量极差的三角形2 图 2 典型的阵面推进算法过程
5、2 图 3 典型的基于四叉树的算法过程3 图 4 典型的 Delaunay 网格及其局部放大.4 图 5 Quake project 的并行有限元系统计算流程（Shewchuk and Hallaron）6 图 6 点集的 Delaunay 三角剖分与空圆特性.9 图 7几个PSLG的例子.10 图 8 局部特征尺度的例子 （Steven Elliot Pav） 10 图 9 一个 PSLG、 相应点集、 Delaunay 三角剖分、 约束 Delaunay 三角剖分.11 图 10 一条被侵蚀的线段.11 图 11 命题 2 证明过程示意图 12 图 12 本章网格生成问题的输入与输出 13
6、 图 13 Locate()过程. 16 图 14 按照空圆准则插入点的过程 Insert() 17 图 15 扫描线的状态 18 图 16 拥有相同上端点线段的排序 19 图 17 不会存在的情况. 19 图 18 接近线段交点的扫描线 . 21 图 19 待恢复约束边“穿过”的三角形 24 图 20 约束边恢复算例 24 图 21 质量指标的示意图 . 26 图 22 两种情况下的偏心与偏心圆（Alper Ungor）. 27 图 23 简化的美国地图 PSLG . 28 图 24 Delaunay refine 之前的约束 Delaunay 三角剖分，共 294 个三角形 28 图 25
7、 Ruppert 的 Delaunay refine 算法生成的网格图形，共 2743 个三角形. 29 图 26Alper Ungor 的 Delaunay refine 算法生成的网格图形，共 1566 个三角形. 29 图 27 一个使 Delaunay refine 算法失败的 PSLG（Steven Elliot Pav）. 31 图 28 小角度的预处理剖分 32 图 29 一个含有小角的 PSLG 及其 Delaunay 网格的例子 32 图 30 Laplacian 光顺 33 图 31 几类拓扑变换，从上到下依次为边翻转、边分裂、边压缩. 34 图 32 点的删除(Devil
8、lers) 34 国防科学技术大学研究生院硕士学位论文 第 III 页 图 33 本章算法流程 38 图 34 数字图像与图像分割的例子（Jepson and Fleet） 39 图 35 4 链接与 8 链接 . 41 图 36 数字边界的最小周长多边形示意图 . 42 图 37 从世界地图中提取的亚欧非大陆边界与最小周长多边形 . 43 图 38 一个有许多小角的 PSLG鹰. 45 图 39 鹰的网格图形及质量统计. 46 图 40 Michael Jackson 侧影的 PSLG 与网格图形及质量统计 47 图 41 美女背影的 PSLG 与网格图形及质量统计. 48 图 42 融合的
9、万花筒写轮眼 PSLG 与网格图形及质量统计. 49 图 43 Mesh2d 生成的网格图形 52 图 44 苏必利尔湖卫星照片、分割的二值图像、PSLG、网格图形及质量统计. 54 图 45 蝴蝶照片、图像分割、PSLG、网格图形及质量统计56 图 46 亚欧非大陆、网格图形及质量统计.58 图47亚欧非大陆MPP的网格图形及质量统计59 图 48 世界地图 PSLG 与网格图形.60 图49图48的两个局部放大.61 图50第三章算法与Persson的结果的一个比较.62 国防科学技术大学研究生院硕士学位论文 第 i 页 摘 要 众多科学与工程实践中的复杂的物理现象都会用偏微分方程描述。当
10、方程的 初、边值条件过于复杂或计算区域过于复杂使我们无法得到真实解时，得到一个 可靠的数值近似就很重要。在偏微分方程的数值计算方法中，从有限差分、有限 体积到有限元都要依赖网格剖分。网格依据其拓扑结构的规律性可分为结构网格 与非结构网格。结构网格在存储、操作上的简单性以及在计算中的高效性并不能 弥补其对复杂区域的不适应性，因此非结构网格是复杂区域剖分的一个常用选择， 其生成算法可大体分为 Delaunay、阵面推进、四叉树三类。不是所有的网格都适 合进行数值计算，质量很差的网格能导致计算的速度很慢甚至计算崩溃。因此， 研究高质量、高效率的网格生成算法很有必要。Delaunay 类型的网格及其生
11、成算 法具有坚实的数学理论基础，故选择该方法进行深入分析与研究，所做工作如下： 1、深入讨论了二维 Delaunay 网格生成过程的各主要步骤的不同算法，并针对 约束边的恢复问题设计了一个约束边恢复算法，证明其收敛性，还进行了计算复 杂度估计，理论与实验均证明该算法可以有效减少高代价的相交测试的次数。 2、对网格生成过程中解决同一问题的不同算法进行分析评价，并编写代码进 行了实验比较,根据实验结果选择较好的算法添加进我们最后的程序中，得到了比 较高效、稳健的二维 Delaunay 网格生成程序。 3、开发了一个从数字图像中提取感兴趣区域，并对得到的图形生成二维 Delaunay 网格的算法。实
12、验表明该算法能成功捕捉由图像表示的复杂区域的重要 特征，并对得到的区域生成高质量的二维 Delaunay 网格。 4、本文第四章还将自己的工作与别人的类似工作进行了实验对比。 关键词：非结构网格；二维关键词：非结构网格；二维 Delaunay 网格；数字图像网格；数字图像 国防科学技术大学研究生院硕士学位论文 第 ii 页 国防科学技术大学研究生院硕士学位论文 第 iii 页 Abstract Many complicated physical phenomena in science and engineering can be modeled by partial differential
13、 equations(PDEs).When we cant get a real solution because of the complicated boundary conditons of the equations or the complicated shape of the domain,a numerical approximation of the solution is important. Numerical methods for sloving PDEs such as finite different method finite volume method and
14、finite element method all depend on mesh generation. Meshes can be categorized as structured or unstructured by the topology. Althrough structured mesh can be easily stored and manipulated,it is not suitable for the complicated domain. Unstructured mesh is a common option for the subdivision of comp
15、licated domains.The generation algorithms of unstructured mesh can be divided into three classes:Delaunay triangulation methods advancing front methods and methods based on quadtrees.Not all meshes are suitable for numerical computation.Some meshes with poor quality can lead to a low speed in computation or even crash.So,its necessary to research mesh generation algorithms that produce high quality meshes and run quickly. Delaunay mesh and it
