有限元分析中的二维Delaunay三角网格剖分
- 格式：doc
- 大小：702.26 KB
- 文档页数：17
下载文档原格式
合集下载
上下扫描线的delaunay三角剖分算法
上下扫描线的delaunay三角剖分算法Delaunay三角剖分是一种广泛应用于计算几何和数值分析的算法，它主要用于生成二维平面上的三角形网格。
Delaunay三角剖分具有很多优良的性质，例如空外接圆性质和最小角最大性质等。
上下扫描线的Delaunay三角剖分算法是一种高效的Delaunay三角剖分算法，其基本思想是利用扫描线从上到下或从下到上扫描整个区域，并在扫描过程中对点进行插入和删除操作，从而生成Delaunay三角剖分。
具体步骤如下：
1. 将所有点按照y坐标从大到小排序。
2. 从上到下扫描整个区域，对于每个扫描到的点，将其插入到Delaunay三角剖分中。
具体做法是：找到该点的最近点，然后删除该点，并将该点和最近点之间的线段加入到Delaunay三角剖分中。
3. 重复步骤2，直到扫描完所有点。
该算法的时间复杂度为O(nlogn)，其中n为点的数量。
这是因为需要将所有点排序，并且每次插入一个点都需要在已排序的点中进行二分查找。
需要注意的是，该算法只能处理凸多边形的边界，如果存在凹多边形或自相交的情况，需要使用其他算法进行处理。
delaunay方法
delaunay方法
Delaunay方法，又称为Delaunay三角剖分，是前苏联数学家Delaunay在1934年提出的一种三角剖分方法。
该方法满足所谓的“最大-最小角”优化准则，即所有最小内角之和最大，从而使得划分的三角形不会出现某个内角过小的情况。
这种方法在二维情况下可以描述为：对于给定的平面点集，只存在着唯一的一种三角剖分方法，满足Delaunay三角剖分的条件，即任意一个三角形的外接圆内不包括其他结点。
Delaunay三角剖分方法在各种二维三角剖分中具有全局和局部最优性。
它可以应用于数值模拟的网格生成，尤其在复杂外形的非结构网格生成中有广泛应用。
此外，Delaunay 三角剖分方法还可以推广至多维问题，例如在三维情况下，四面体的外接球内不包含其他节点。
在具体实施过程中，三维情况下的Delaunay三角化可以包括以下步骤：在三维空间内定义一个大的凸壳区域以覆盖所有将要插入的点；根据网格步长分布要求在凸壳区域内引入一个新点；标记将被删除的四面体（其外接球包含新点的所有四面体）；建立空洞边界（由被标记的四面体组成的凸壳的外边界）；在剩余四面体中查找被标记四面体的邻居以
建立有效的空间连续性；利用空洞边界上每个三角形的三个顶点与新点组成新的四面体；建立空洞外原四面体和新生成的四面体的邻居关系。
一种改进的2D-Delaunay三角剖分算法
１ 分治算法均 匀划分空 间数 据
在实 际 的工程 中 ， 由于 物体 结构 的不 规则 性 ，
定位 该 点所 在 的 目标 三 角形 ， 体 算法 如下 ． 具 １ ）由图 １ ａ可 知 ， （） 设插 入 点 尸在 Ａ Ｂ Ａ Ｃ内 ， 则
空 间数据 点 的采集 并 非 十分 均匀 ，而且 在逐 点插
一
个 初始 的三角 网， 然后 将余 下 的点 逐个 插入 ， 采
用 Ｌ Ｐ算法 或 Ｗａ ｏ Ｏ ｔ ｎ的空 外接 圆算 法 优化 ， ｓ 确保
其 成为 Ｄ ｌ ｎ ｙ 角 网．针对 实 际工程 运用 中大 ｅ ｕａ 三 ａ
更 新 的三角 形所 在 网格 号 ， 三角 形更 新 的先后 按 顺序 实 时修 改对 应 网格 中存 储 的三 角形标 识 ．该
交 互 为每块 的平均 点数 选定 一个 阈值 Ｄ， 来实 现 数 据 点 的均 匀 分块 ；在三 角 网格 的构 建 过程 中 ， 根 据 设 定 的 阈值 Ｄ 采 用 分 治算 法 进 行 数据 块 划 分 ． 过程 首 先 以 为 主 】为 辅将 空 间数 据进行 该 ，
于剖 分算法 的研究 ， 内外 很多 文献都有 相应 的论 国 述， 主要 算法 有分 治算 法 、 点插 入算 法 、 逐 三角 网
一
种改进 的 ２ — ｅ ｕ ａ － Ｄ Ｄ ｌ ｎｙ． ａ
分算法
施友道 ，何 曙光 ，傅 琼波 ，靳俊 霞
（． １福州市公 安局， 福州 ３０１； ２长江 日报报业集 团， ５０ １ ． 武汉 ４０ １； ３０５ ３ 湖北省农村信 用社联合社 ， ． 武汉 ４ ０ １； ４ 武汉理工大学， ３０５ ． 武汉 ４ ０ ７ ） ３００
delaunay 三角剖分 步骤
delaunay 三角剖分步骤1. Delaunay三角剖分是用于将点集分割成不规则三角形的方法。
The Delaunay triangulation is a method for dividing a set of points into irregular triangles.2.首先选择一个点作为起始点。
First, select a point as the starting point.3.然后选择另外两个点与起始点构成一个三角形。
Then select two other points to form a triangle with the starting point.4.接着选择一个未被包含在任何三角形内的点。
Then select a point that is not included in any triangle.5.在所有的三角形中寻找能将这个新点包含进去的三角形。
Find a triangle among all the triangles that can include this new point.6.如果找到了这样的三角形，将这个三角形和新点围成的区域删除。
If such a triangle is found, remove the area enclosed by this triangle and the new point.7.在新的边缘上寻找新的三角形。
Find new triangles on the new edges.8.重复以上步骤，直到所有的点都被包含在三角形内。
Repeat the above steps until all points are included in triangles.9. Delaunay三角剖分具有无重叠、最小化夹角和最大化最小角的性质。
Delaunay triangulation has the properties of non-overlapping, minimizing angles, and maximizing minimum angles.10.可以使用Delaunay三角剖分来进行网格生成和空间分析。
三维空间Delaunay三角剖分算法的研究及应用
三维空间Delaunay三角剖分算法的研究及应用一、本文概述随着计算几何和计算机图形学的发展，三维空间Delaunay三角剖分算法已成为一种重要的空间数据处理和分析技术。
本文旨在全面深入地研究三维空间Delaunay三角剖分算法的原理、实现方法以及应用领域。
本文将对三维空间Delaunay三角剖分算法的基本概念和性质进行详细的阐述，包括其定义、性质、特点以及与其他三角剖分算法的比较。
接着，本文将重点探讨三维空间Delaunay三角剖分算法的实现方法，包括增量法、分治法和扫描转换法等，并分析它们的优缺点和适用范围。
本文还将对三维空间Delaunay三角剖分算法在各个领域的应用进行详细的介绍和分析。
这些领域包括计算机科学、地理信息系统、地质学、气象学、生物医学等。
通过具体的应用案例，本文将展示三维空间Delaunay三角剖分算法在实际问题中的应用价值和效果。
本文还将对三维空间Delaunay三角剖分算法的未来发展方向进行展望，探讨其在新技术和新领域中的应用前景和挑战。
本文旨在全面系统地研究三维空间Delaunay三角剖分算法的理论和实践，为其在实际问题中的应用提供有力的支持和指导。
二、三维空间Delaunay三角剖分算法的基本原理Delaunay三角剖分算法是一种广泛应用于二维空间的数据处理算法，它的核心目标是将一组离散的二维点集剖分为一系列互不重叠的三角形，且这些三角形满足Delaunay性质。
简单来说，Delaunay 性质要求任何一个三角形的外接圆内部不包含该三角形之外的任何数据点。
初始化：为每个点分配一个初始的三角形。
这通常是通过连接每个点与它的两个最近邻点来完成的，形成一个初始的三角形网格。
合并三角形：接下来，算法会尝试合并相邻的三角形，以形成更大的三角形。
在合并过程中，算法会检查新形成的三角形是否满足Delaunay性质。
如果满足，则合并成功；如果不满足，则放弃合并，并标记这两个三角形为“已处理”。
delaunay-三角剖分算法
一、概述Delaunay 三角剖分算法是计算机图形学领域中常用的一种算法，它可以将给定的点集进行高效的三角剖分，用于构建网格、进行地理信息系统分析、建立三维模型等应用。
本文将对该算法的原理、实现和应用进行介绍。
二、算法原理1. 待剖分点集在进行Delaunay三角剖分之前，需要准备一个点集，这个点集是待剖分的对象。
点集的数量取决于具体的应用，可以是二维平面上的点，也可以是三维空间中的点。
2. Delaunay 三角形在进行三角剖分时，Delaunay 三角形是一种特殊的三角形，满足以下性质：a. 任意一个点要么位于Delaunay 三角形的外接圆内部，要么位于外接圆的边上；b. 任意两个Delaunay 三角形之间的外接圆不相交。
3. Delaunay 三角剖分Delaunay 三角剖分是将给定点集进行三角剖分的过程，它的目标是构建满足Delaunay 三角形性质的三角形集合。
三、算法实现1. 基于增量法的实现增量法是Delaunay 三角剖分的一种经典算法，它的基本思想是逐步增加点，并根据Delaunay 三角形的性质进行调整。
具体步骤如下： a. 初始化：选择一个超级三角形包含所有点集，作为初始三角剖分；b. 顺序插入点：逐个将待剖分点插入到当前三角剖分中，并进行调整；c. 边界检测：检测新增的边界是否需要进行修正；d. 优化处理：对新增点周围的三角形进行优化调整。
2. 时间复杂度分析增量法的时间复杂度主要取决于点集的数量和点的分布情况，一般情况下，其时间复杂度可以达到O(nlogn)。
四、算法应用1. 图形渲染在计算机图形学中，Delaunay三角剖分常用于构建网格、进行三维渲染等。
它可以有效地分割空间，使得渲染效果更加真实。
2. 地理信息系统地理信息系统中常常需要对地理数据进行空间分析，Delaunay三角剖分可以帮助构建地理网格，进行地形分析、资源评估等。
3. 三维建模在三维建模领域，Delaunay三角剖分可以用于构建复杂的三维模型，并支持模型的分析、编辑等功能。
结构有限元分析中的网格划分技术及其应用实例
结构有限元分析中的网格划分技术及其应用实例一、前言有限元网格划分是进行有限元数值模拟分析至关重要的一步，它直接影响着后续数值计算分析结果的精确性。
网格划分涉及单元的形状及其拓扑类型、单元类型、网格生成器的选择、网格的密度、单元的编号以及几何体素。
从几何表达上讲，梁和杆是相同的，从物理和数值求解上讲则是有区别的。
同理，平面应力和平面应变情况设计的单元求解方程也不相同。
在有限元数值求解中，单元的等效节点力、刚度矩阵、质量矩阵等均用数值积分生成，连续体单元以及壳、板、梁单元的面内均采用高斯（Gauss）积分，而壳、板、梁单元的厚度方向采用辛普生（Simpson）积分。
辛普生积分点的间隔是一定的，沿厚度分成奇数积分点。
由于不同单元的刚度矩阵不同，采用数值积分的求解方式不同，因此实际应用中，一定要采用合理的单元来模拟求解。
CAD软件中流行的实体建模包括基于特征的参数化建模和空间自由曲面混合造型两种方法。
Pro/E和SoildWorks是特征参数化造型的代表，而CATIA与Unigraphics等则将特征参数化和空间自由曲面混合造型有机的结合起来。
现有CAD软件对表面形态的表示法已经大大超过了CAE软件，因此，在将CAD实体模型导入CAE软件的过程中，必须将CAD模型中其他表示法的表面形态转换到CAE软件的表示法上，转换精度的高低取决于接口程序的好坏。
在转换过程中，程序需要解决好几何图形（曲线与曲面的空间位置）和拓扑关系（各图形数据的逻辑关系）两个关键问题。
其中几何图形的传递相对容易实现，而图形间的拓扑关系容易出现传递失败的情况。
数据传递面临的一个重大挑战是，将导入CAE程序的CAD模型改造成适合有限元分析的网格模型。
在很多情况下，导入CAE程序的模型可能包含许多设计细节，如细小的孔、狭窄的槽，甚至是建模过程中形成的小曲面等。
这些细节往往不是基于结构的考虑，保留这些细节，单元数量势必增加，甚至会掩盖问题的主要矛盾，对分析结果造成负面影响。
delaunay三角剖分算法流程
delaunay三角剖分算法流程下载温馨提示:该文档是我店铺精心编制而成，希望大家下载以后，能够帮助大家解决实际的问题。
文档下载后可定制随意修改，请根据实际需要进行相应的调整和使用，谢谢!并且，本店铺为大家提供各种各样类型的实用资料，如教育随笔、日记赏析、句子摘抄、古诗大全、经典美文、话题作文、工作总结、词语解析、文案摘录、其他资料等等，如想了解不同资料格式和写法，敬请关注!Download tips: This document is carefully compiled by theeditor.I hope that after you download them,they can help yousolve practical problems. The document can be customized andmodified after downloading,please adjust and use it according toactual needs, thank you!In addition, our shop provides you with various types ofpractical materials,such as educational essays, diaryappreciation,sentence excerpts,ancient poems,classic articles,topic composition,work summary,word parsing,copy excerpts,other materials and so on,want to know different data formats andwriting methods,please pay attention!Delaunay三角剖分算法的流程详解Delaunay三角剖分是一种在二维空间中将点集划分为三角形的方法，使得没有任何一个点位于其相邻三角形的内切圆内。
有限元网格剖分原理
有限元网格剖分原理： 1. 引言有限元法是求解复杂工程问题的一种近似数值解法，现已广泛应用到力学、热学、电磁学等各个学科，主要分析工作环境下物体的线性和非线性静动态特性等性能。
有限元法求解问题的基本过程主要包括：分析对象的离散化?有限元求解?计算结果的处理三部分。
曾经有人做过统计：三个阶段所用的时间分别占总时间的40%~50%、5%及50%~55%。
也就是说，当利用有限元分析对象时，主要时间是用于对象的离散及结果的处理。
如果采用人工方法离散对象和处理计算结果，势必费力、费时且极易出错，尤其当分析模型复杂时，采用人工方法甚至很难进行，这将严重影响高级有限元分析程序的推广和使用。
因此，开展自动离散对象及结果的计算机可视化显示的研究是一项重要而紧迫的任务。
可喜的是，随着计算机及计算技术的飞速发展，出现了开发对象的自动离散及有限元分析结果的计算机可视化显示的热潮，使有限元分析的“瓶颈”现象得以逐步解决，对象的离散从手工到半自动到全自动，从简单对象的单维单一网格到复杂对象的多维多种网格单元，从单材料到多种材料，从单纯的离散到自适应离散，从对象的性能校核到自动自适应动态设计/分析，这些重大发展使有限元分析摆脱了仅为性能校核工具的原始阶段，计算结果的计算机可视化显示从简单的应力、位移和温度等场的静动态显示、彩色调色显示一跃成为对受载对象可能出现缺陷(裂纹等)的位置、形状、大小及其可能波及区域的显示等，这种从抽象数据到计算机形象化显示的飞跃是现在甚至将来计算机集成设计/分析的重要组成部分。
2. 有限元分析对网格剖分的要求有限元网格生成就是将工作环境下的物体离散成简单单元的过程，常用的简单单元包括：一维杆元及集中质量元、二维三角形、四边形元和三维四面体元、五面体元和六面体元。
他们的边界形状主要有直线型、曲线型和曲面型。
对于边界为曲线(面)型的单元，有限元分析要求各边或面上有若干点，这样，既可保证单元的形状，同时，又可提高求解精度、准确性及加快收敛速度。
Delaunay三角剖分的问题
Delaunay三⾓剖分的问题最近接触到计算Delaunay三⾓剖分的问题，也算是计算⼏何的⼀个经典问题了。
按照别⼈的算法，也⾃⼰实现了个，发现点集⼤的时候，程序计算起来特慢。
后来分析发现，别⼈程序号称的都是O(nlogn)的，我的却成了O(n*n)的，算法都是⼀样，后来才发现是数据结构的问题，看来程序＝算法＋数据结构，有道理。
闲着，就整理了些相关知识，组织如下：1.Delaunay三⾓剖分&Voronoi图定义2.计算Delaunay三⾓剖分的算法及分析3.例⼦程序&代码⼤话点集的三⾓剖分（Triangulation），对数值分析（⽐如有限元分析）以及图形学来说，都是极为重要的⼀项预处理技术。
尤其是Delaunay三⾓剖分，由于其独特性，关于点集的很多种⼏何图都和Delaunay三⾓剖分相关，如Voronoi图，EMST 树，Gabriel图等。
Delaunay三⾓剖分有⼏个很好的特性：1.最⼤化最⼩⾓，“最接近于规则化的“的三⾓⽹。
2.唯⼀性（任意四点不能共圆）。
概念及定义⼆维实数域(⼆维平⾯)上的三⾓剖分定义1：假设V是⼆维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段, E为e的集合。
那么该点集V的⼀个三⾓剖分T=(V,E)是⼀个平⾯图G，该平⾯图满⾜条件：1.除了端点，平⾯图中的边不包含点集中的任何点。
2.没有相交边。
3.平⾯图中所有的⾯都是三⾓⾯，且所有三⾓⾯的合集就是点集V的凸包。
那什么是Delaunay三⾓剖分呢?不过是⼀种特殊的三⾓剖分罢了。
从Delaunay边说起。
Delaunay边定义2：假设E中的⼀条边e（两个端点为a,b），e若满⾜下列条件，则称之为Delaunay边：存在⼀个圆经过a,b两点，圆内不含点集V中任何的点，这⼀特性⼜称空圆特性。
Delaunay三⾓剖分定义3：如果点集V的⼀个三⾓剖分T只包含Delaunay边，那么该三⾓剖分称为Delaunay三⾓剖分。
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
有限元分析中的二维Delaunay三角网格剖分摘要本文从有限元分析出发，引出三角网格剖分的概念。
随后着重介绍了二维平面点集的Delaunay三角剖分。
给出了一些重要的Delaunay三角形的定理和性质，也体现出了Delaunay三角剖分的优点。
接着重点分析了构造二维Delaunay三角形的空洞算法，并用程序完成了它。
最后又分析了算法中的不足，并给出论文改进的方法。
关键词：Delaunay三角形，V oronoi图，网格剖分III1 第一章绪论1.1网格剖分的背景有限元分析是数学的一个分支。
其思想是将复杂的问题简单化，然后进行处理。
处理办法是将整个研究对象分成一些有限的单元，然后对每个小单元做相应的处理，最后整合起来去逼近原来的整个对象。
所以我们可以看到，有限元分析中将单元剖分的越小，得到的近似值就会越逼近真实值。
但是往往我们需要处理的对象很复杂，需要的计算量也很大，人工很难完成。
在早起年代，这个问题也阻止了有限元分析的发展。
近年来，随着计算机的发展，带动了一些需要大量计算的科学领域的发展。
有限元分析就是其中一种，因为当计算机取代人力之后，其快速的计算能力作用愈发凸显，人们只需要控制相应的算法即可。
作为最常用的处理手段，被大大的发展了之后，有限元分析也被应用于诸多方面。
早期的有限元分析主要应用与航空航天和地质、地球物理方面，现在越来越多的在工程分析计算和计算流体力学中看见。
图 1.1图 1.2常见的有限元分析可以分为六大步骤：问题及求解域的定义、求解域的网格剖分、确定状态变量及控制方法、单元推导、总装求解和结果解释。
上述步骤又可被分为三大阶段：前置处理、计算求解和后置处理。
而在前置处理中网格剖分作为最重要又最复杂的一个步骤，其处理结果制约着有限元的最后逼近结果。
网格剖分有很多形式：二维的主要剖分形状有三角形、四边形，三维的有四面体、六面体。
在有限元分析中网格剖分有如下要求：1、节点合法性。
指每个单元的节点最多只能是其他单元的节点或边界点，而不能是内点。
2、单元相容性。
指每个单元必须在求解域的内部。
3、良好的单元形状。
指每个单元尽量最好是正的，比如二维是正多边形，三维是正多面体。
4、自适应性。
是指在剖分域中曲率大或其他参数变化较大的地方剖分越密，单元越小，越平滑或其他参数变化不大的地方单元可以稍微稀疏。
这样，既可以提高计算收敛速度，又可以提高逼近精度。
网格剖分的对象越是复杂，剖分的要求越高。
对于复杂三维实体，现在还没有成熟的算法。
1.2 网格剖分的发展网格剖分是几何模型和数值计算之间的桥梁。
1974年网格剖分首次被Thompson等人用椭圆方程方法构造出来。
之后Steger等人又提出了用双曲型方程来构造出网格。
在20世纪90年代，非结构网格和自适应笛卡尔网格等技术相继被提出，大大推动了CFD的发展。
直到如今，网格技术已产生好多方法，非结构网格、结构网格以及自适应网格等，其中最为常用的是非结构网格技术和结构网格技术。
结构网格是指正交的排列规则的网格。
它的特点是相邻的节点不需要遍历寻找就可以被计算出来。
生成结构网格的方法主要有：贴体坐标法和块结构化网格。
非结构网格和结构网格对应，是指内部节点没有毗邻单元。
其主要的方法有阵面、Delaunay三角剖分、四叉树和八叉树法。
本文主要针对于二维平面上的Delaunay三角剖分。
2第二章问题分析我们假设有这样有这样一个场景，当你拿着新买的碟子的边在盛食物，刚加了两个饼突然碟子沿中间裂开了。
我们知道这是碟子的质量问题，捡起来重买一个就可以。
但是在现实生活中我们遇到的好多工程，如桥梁、高楼等，他们对质量要求很高，在建筑之前必须对整个建筑做相应的应力分析，否则后果不堪设想。
我们以这个盘子为例，若有工程师愿意对此盘子做有限元分析，我们首先来看看它的单元怎么生成。
首先我们看第一步：问题及求解域。
很明显这个问题中我们是要研究整个盘子的应力分析，而其求解域就是整个盘子，我们可以简化一下，它就是一个数学圆，或者里面又套了一个小圆，其为底部的边界。
第二步：网格剖分。
这一步是关键，也是难点。
我们遇到的首个问题是，怎么把实物，此处为碟子，描述到计算机中，变成可用于计算的对象？我们有两种方法。
第一种：我们可以现实中丈量实物的长宽等尺寸；第二种：对实物进行拍照，然后对其图像处理，进行像素提取、边界提取、纹理处理等操作。
显然第一种简单，第二种很麻烦。
但是工程中，我们所面对的都是庞大有复杂的对象，或是测量成本很大，或是根本不能进行现实测量的，如山体卫星图等。
所以第二种方法虽然复杂，但是可以推广且尤为重要，故本文重点用第二种方法来完成此实物的网格剖分。
图 2.1所以我们首先要进行边界提取。
边界提取目前有成熟的算法，对于本文中的实物，我们采用有向边缘法，其算法理论在算法设计环节中重点介绍。
3其次我们需要对边界进行多边形逼近，所幸的是，我们得用计算机到的边界其实已经离散化了，所以这一步我们可以省略。
最后我们的重点到了，就是对上述的边界，或是点的集合进行三角网格剖分。
我们采用已经成熟的空洞算法，又名增量算法，来生成有限点集的Delaunay三角形。
下面是Delaunay三角形剖分的理论基础。
45 第三章 理论介绍3.1 Delaunay 三角形定义及性质在数学中我们有对偶图的概念。
即图二以图一的面为顶点，图一中共边的两面对应的图二中顶点为相邻的两点，则图二为图一的对偶图。
图 3.1而Delaunay 三角形是Voronoi 图的对偶图。
所以为定义Delaunay 图，我们首先定义Voronoi 图，这又需要用到点的领域的概念。
定义1、点的领域。
点的领域是指在平面的有限区域内，给定一些有限的点集}p ,p ,p ,{p n 321 ，对每个点n i p i ,2,1,=，其领域是指这样的点的集合},2,1),)(,(min ))(,(|),{(n j P y x d P y x d y x V j i i ===。
即每个点的领域中的点到其他给定点的距离大于或等于到该点的距离。
定义2、Voronoi 图。
在平面上给定有限的点集，每个点和相邻点之间线段的垂直平分线彼此相截围成的图是Voronoi 图。
所以我们看到，Voronoi 图实际上就是点集的领域图。
定义3、Delaunay 三角形。
Voronoi 图的对偶图就是Delaunay 三角形图。
在上述中我们会发现有些问题存在。
当所给的点集中存在四点共圆，且圆中无其他给定点，则Voronoi 图中会有四线共点，对应的Delaunay 三角形中会出现四边形。
如右上图。
但是不影响，此时我们链接四边形的任意一条对角线分成两个三角形即可。
下文中我们会看到这么处理不会影响Delaunay 三角形的性质，符合其空外接圆准则。
图 3.2图 3.3性质1、空外接圆准则。
所给的点集生成Delaunay三角形中，每个三角形都不会以其他给定点为内点，最多以其为边界点。
1定理1、给定点集所生成的Delaunay三角剖分中，每个单元都符合上述准则。
定理2、所给定点集的某一三角剖分，若每个单元都符合Delaunay三角准则，则这个三角剖分一定是Delaunay三角剖分。
3.2 Delaunay三角形的优点性质2、最小角最大准则。
即在给定点集的所有三角剖分中，我们会有Delaunay三角形中的最小角比其他剖分中最小角大。
这个准则和Delaunay三角形的空外接圆准则是一致的，但这条准则也让我们看到Delaunay三角剖分均匀的这一优点。
最小角最大准则，可以有效的降低1杨钦.限定Delaunay三角网格剖分技术6剖分中不规范的三角形出现的次数，有利于有限元分析时单元光滑、均匀，符合实际要求，从而提高逼近的精度。
所以，这也足以说服我们剖分时采用Delaunay 三角剖分。
性质3、局部重连（加点）。
当在点集中增加点时，只需做局部的改动，就能保证整体是Delaunay三角形。
为了说明这种局部改动，可以参考下图。
图 3.4性质4、局部重连（删点）。
当点集Delaunay三角化之后需要删去一个点，只需删去以此点为顶点的三角形，剩余的仍然是剩余顶点的Delaunay三角形。
以上的定理深刻的描述了Delaunay三角形的本质，也提供了构造Dlaunay 三角剖分的方法论。
我们在构造Delaunay三角剖分时，也就不走定义的那条路，即先构造Voronoi图，然后根据Delaunay三角形式Voronoi图的对偶图，从而得到Delaunay图，转而寻找符合空外接圆准则的三角剖分图，这样就保证了最终的确是Voronoi图。
而这样操作容易操作，算法的时间复杂度也会降低。
下面我们介绍构造点集Delaunay三角剖分的算法。
3.3 二维点集Delaunay三角剖分算法生成二维点集的Delaunay三角剖分算法经典的有两种：空洞算法和换边法。
783.3.1 空洞算法（增量算法）空洞算法的思想源于数学归纳法。
我们都知道数学归纳法的三大步骤：首先证明初始时命题成立，其次证明当目前命题成立时，下一步命题也成立，最后得到最终结果。
空洞算法也是这样：初始时，当给定4个点时可以生成2个Delaunay 三角形，然后增加一个点时，也可以生成Delaunay 三角形，最后一直加点，知道所有点集中的点被加入。
我们已经看到，增加点时由局部重连性质可以保证第二步确实成立。
那么问题只剩开始的四个点能够生成三角剖分吗？其实只要四点不共线就能保证，如下图。
图 3.53.3.2 换边法（局部变换法）换边法的原理仍然是空外接圆准则。
他要求先对所给点集做初始三角剖分，然后逐一检验每个三角形是否符合空外接圆准则，否则就四边形进行换边。
如下图：图 3.6则问题是，换掉对角线能保证局部是Delaunay 三角形吗？ 为此，我们需要以下引理。
9 引理1、圆上一条弦对某点所张开的角度，若点在圆内，则大于对应的圆周角；若在圆上，则等于对应的圆周角；若在圆外，则小于对应的圆周角。
回到原问题，我们假设ADC ∆的外接圆ABC O 包含点B ，则由上面引理，有 DAC DBC ∠>∠,ACD ABD ∠>∠。
那么在ABD ∆的外接圆ABD O 中，点C 肯定在其外，否则ABD ACD ∠≥∠， 同理，点A 在BCD ∆的外接圆BCD O 外，否则CBD CAD ∠≥∠。
从而换边之后符合Delaunay 三角剖分的空外接圆准则。
第四章算法设计本节中着重对边界提取和空洞算法详细介绍和进行分析。
4.1 边界提取。
我们的主要工作是确定图中满足灰度值要求象素群的边缘线或轮廓线。
由m*n个点组成的二值点阵图形在上一步我们已经实现。
这阶段主要来将其轮廓提取出来。
一般的，我们面对的二值图如下图所示：图 4.1若定义黑色和白色的公共边所连接构成的线为边缘线，这时我们可以看到边缘线将图片的轮廓完全描绘出来。