Delaunay三角剖分算法.docx

Delaunay三角剖分算法.docx

ID:50811751

大小:91.97 KB

页数:4页

时间:2020-03-14

Delaunay三角剖分算法.docx_第1页
Delaunay三角剖分算法.docx_第2页
Delaunay三角剖分算法.docx_第3页
Delaunay三角剖分算法.docx_第4页
资源描述:

《Delaunay三角剖分算法.docx》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、Delaunay三角剖分算法点集的三角剖分(Triangulation),对数值分析(比如有限元分析)以及图形学来说,都是极为重要的一项预处理技术。尤其是Delaunay三角剖分,由于其独特性,关于点集的很多种几何图都和Delaunay三角剖分相关,如Voronoi图,EMST树,Gabriel图等。Delaunay三角剖分有最大化最小角,“最接近于规则化的“的三角网和唯一性(任意四点不能共圆)两个特点。定义编辑【定义】三角剖分[1]  :假设V是二维实数域上的有限点集,边e是由点集中的点作为端点构成的封闭线段,E为e的集合。那么该点集V的一个三角剖分T=

2、(V,E)是一个平面图G,该平面图满足条件:1.除了端点,平面图中的边不包含点集中的任何点。2.没有相交边。3.平面图中所有的面都是三角面,且所有三角面的合集是散点集V的凸包。在实际中运用的最多的三角剖分是Delaunay三角剖分,它是一种特殊的三角剖分。先从Delaunay边说起:【定义】Delaunay边:假设E中的一条边e(两个端点为a,b),e若满足下列条件,则称之为Delaunay边:存在一个圆经过a,b两点,圆内(注意是圆内,圆上最多三点共圆)不含点集V中任何其他的点,这一特性又称空圆特性。【定义】Delaunay三角剖分:如果点集V的一个三角

3、剖分T只包含Delaunay边,那么该三角剖分称为Delaunay三角剖分。优化处理:理论上为了构造Delaunay三角网[2]  ,Lawson提出的局部优化过程LOP(LocalOptimizationProcedure),一般三角网经过LOP处理,即可确保成为Delaunay三角网,其基本做法如下所示:1.将两个具有共同边的三角形合成一个多边形。2.以最大空圆准则作检查,看其第四个顶点是否在三角形的外接圆之内。3.如果在,修正对角线即将对角线对调,即完成局部优化过程的处理。LOP处理过程如下图所示:Delaunay剖分的算法Delaunay剖分是一种

4、三角剖分的标准,实现它有多种算法。准则特性编辑准则:要满足Delaunay三角剖分的定义,必须符合两个重要的准则:1、空圆特性:Delaunay三角网是唯一的(任意四点不能共圆),在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示:2、最大化最小角特性:在散点集可能形成的三角剖分中,Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲,Delaunay三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线,在相互交换后,六个内角的最小角不再增大。如下图所示:特性:以下是Delau

5、nay剖分所具备的优异特性:1.最接近:以最近的三点形成三角形,且各线段(三角形的边)皆不相交。2.唯一性:不论从区域何处开始构建,最终都将得到一致的结果。3.最优性:任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话,那么两个三角形六个内角中最小的角度不会变大。4.最规则:如果将三角网中的每个三角形的最小角进行升序排列,则Delaunay三角网的排列得到的数值最大。5.区域性:新增、删除、移动某一个顶点时只会影响临近的三角形。6.具有凸多边形的外壳:三角网最外层的边界形成一个凸多边形的外壳。计算方法编辑a)Lawson算法逐点插入的Lawson算法

6、[3]  是Lawson在1977年提出的,该算法思路简单,易于编程实现。基本原理为:首先建立一个大的三角形或多边形,把所有数据点包围起来,向其中插入一点,该点与包含它的三角形三个顶点相连,形成三个新的三角形,然后逐个对它们进行空外接圆检测,同时用Lawson设计的局部优化过程LOP进行优化,即通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。上述基于散点的构网算法理论严密、唯一性好,网格满足空圆特性,较为理想。由其逐点插入的构网过程可知,遇到非Delaunay边时,通过删除调整,可以构造形成新的Delaunay边。在完成构网后,增加新点时

7、,无需对所有的点进行重新构网,只需对新点的影响三角形范围进行局部联网,且局部联网的方法简单易行。同样,点的删除、移动也可快速动态地进行。但在实际应用当中,这种构网算法当点集较大时构网速度也较慢,如果点集范围是非凸区域或者存在内环,则会产生非法三角形。如左图所示:当离散点集构成圆环时,Lawson算法产生的非法三角形离散点集合   Lawson算法产生的三角剖分    正确的三角剖分  b)Bowyer-Watson算法(推荐)Watson算法的基本步骤是:1、构造一个超级三角形,包含所有散点,放入三角形链表。2、将点集中的散点依次插入,在三角形链表中找出外

8、接圆包含插入点的三角形(称为该点的影响三角形),删除影响三角形的公

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。