1. 三角剖分与Delaunay剖分的定义
如何把一个散点集合剖分成不均匀的三角形网格,这就是散点集的三角剖分问题,散点集的三角剖分,对数值分析以及图形学来说,都是极为重要的一项预处理技术。该问题图示如下:
1.1.三角剖分定义
【定义】三角剖分:假设V是二维实数域上的有限点集,边e是由点集中的点作为端点构成的封闭线段, E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G,该平面图满足条件:
1.除了端点,平面图中的边不包含点集中的任何点。
2.没有相交边。
3.平面图中所有的面都是三角面,且所有三角面的合集是散点集V的凸包。
1.2. Delaunay三角剖分的定义
在实际中运用的最多的三角剖分是Delaunay三角剖分,它是一种特殊的三角剖分。先从Delaunay边说起:
【定义】Delaunay边:假设E中的一条边e(两个端点为a,b),e若满足下列条件,则称之为Delaunay边:存在一个圆经过a,b两点,圆内(注意是圆内,圆上最多三点共圆)不含点集V中任何其他的点,这一特性又称空圆特性。
【定义】Delaunay三角剖分:如果点集V的一个三角剖分T只包含Delaunay边,那么该三角剖分称为Delaunay三角剖分。
1.3.Delaunay三角剖分的准则
要满足Delaunay三角剖分的定义,必须符合两个重要的准则:
1、空圆特性:Delaunay三角网是唯一的(任意四点不能共圆),在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示:
2、最大化最小角特性:在散点集可能形成的三角剖分中,Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲,Delaunay 三角网是“最接近于规则化的“的三角网。具体的说是指在两个相邻的三角形构成凸四边形的对角线,在相互交换后,六个内角的最小角不再增大。如下图所示:
1.4.Delaunay三角剖分的特性
以下是Delaunay剖分所具备的优异特性:
1.最接近:以最近临的三点形成三角形,且各线段(三角形的边)皆不相交。
2.唯一性:不论从区域何处开始构建,最终都将得到一致的结果。
3.最优性:任意两个相邻三角形形成的凸四边形的对角线如果可以互换的话,那么两个三角形六个内角中最小的角度不会变大。
4.最规则:如果将三角网中的每个三角形的最小角进行升序排列,则Delaunay三角网的排列得到的数值最大。
5.区域性:新增、删除、移动某一个顶点时只会影响临近的三角形。
6.具有凸多边形的外壳:三角网最外层的边界形成一个凸多边形的外壳。
1.5.局部最优化处理
理论上为了构造Delaunay三角网,Lawson提出的局部优化过程LOP(Local Optimization Procedure),一般三角网经过LOP处理,即可确保成为Delaunay三角网,其基本做法如下所示:
1.将两个具有共同边的三角形合成一个多边形。
2.以最大空圆准则作检查,看其第四个顶点是否在三角形的外接圆之内。
3.如果在,修正对角线即将对角线对调,即完成局部优化过程的处理。
LOP处理过程如下图所示:
2.Delaunay剖分的算法
Delaunay剖分是一种三角剖分的标准,实现它有多种算法。
2.1.Lawson算法
逐点插入的Lawson算法是Lawson在1977年提出的,该算法思路简单,易于编程实现。基本原理为:首先建立一个大的三角形或多边形,把 所有数据点包围起来,向其中插入一点,该点与包含它的三角形三个顶点相连,形成三个新的三角形,然后逐个对它们进行空外接圆检测,同时用Lawson设计 的局部优化过程LOP进行优化,即通过交换对角线的方法来保证所形成的三角网为Delaunay三角网。
上述基于散点的构网算法理论严密、唯一性好,网格满足空圆特性,较为理想。由其逐点插 入的构网过程可知,遇到非Delaunay边时,通过删除调整,可以构造形成新的Delaunay边。在完成构网后,增加新点时,无需对所有的点进行重新 构网,只需对新点的影响三角形范围进行局部联网,且局部联网的方法简单易行。同样,点的删除、移动也可快速动态地进行。但在实际应用当中,这种构网算法当 点集较大时构网速度也较慢,如果点集范围是非凸区域或者存在内环,则会产生非法三角形。
2.2.Bowyer-Watson算法
Lawson算法的基本步骤是:
1、构造一个超级三角形,包含所有散点,放入三角形链表。
2、将点集中的散点依次插入,在三角形链表中找出其外接圆包含插入点的三角形(称为该点的影响三角形),删除影响三角形的公共边,将插入点同影响三角形的全部顶点连接起来,从而完成一个点在Delaunay三角形链表中的插入。
3、根据优化准则对局部新形成的三角形进行优化。将形成的三角形放入Delaunay三角形链表。
4、循环执行上述第2步,直到所有散点插入完毕。
这一算法的关键的第2步图示如下:
本文来自CSDN博客,http://www.cnblogs.com/RenLiQQ/archive/2008/02/06/1065399.html
分享到:
相关推荐
尤其是Delaunay三角剖分,由于其独特性,关于点集的很多种几何图都和Delaunay三角剖分相关,如Voronoi图,EMST树,Gabriel图等。Delaunay三角剖分有最大化最小角,“最接近于规则化的“的三角网和唯一性(任意四点不...
Delaunay三角剖分算法 1. 三角剖分与Delaunay剖分的定义 如何把一个散点集合剖分成不均匀的三角形网格,这就是散点集的三角剖分问题,散点集的三角剖分,对数值分析以及图形学来说,都是极为重要的一项预处理技术。 ...
用python3.6实现delaunay三角剖分算法,读入存有坐标的csv文件,计算出结果用Tkinter库显示。
离散点生成三角网络的一个经典算法 算法原理:分为三步: 一、凸包生成:二、环切边界法凸包三角剖分三、离散的内插:
为提高带特征线约束的Delaunay三角剖分的速度和效率从两个方面进行改进一是生成无约束的Delaunay三角网时采用并行剖 分算法二是在约束线上插入点时应用取三角形外接圆与特征线交点的方法并行剖分算法具有较好的加速...
Delaunay三角剖分在可视化,GIS,计算机图形学中有着广泛的应用。本文主要是针对3d三角网剖分算法的介绍,研究与应用。
用powercrust算法实现的delaunay三角剖分算法,用到了MATLAB的delaunayn函数库,有兔子等点云源数据和完整的代码,程序可运行,亲测可用
找了半天国内网站上都没找到好用的,好不容易从国外的网站上下载到的..带示例数据和源码 delaunay三角剖分
用java实现的delaunay三角剖分的生成算法,结构严谨,自己添加点后,随即变化对应的三角形化的图形
Delaunay三角剖分逐点插入算法实现
本文在详细研究和分析了典型的Delaunay三角剖分算法的思想后,针对增量 算法中的关键问题提出改进的方法,从降低算法的时间复杂度的角度出发,以点 定位搜索这一关键问题为切入点,提出新的改进搜索的方法,该算法...
用vc实现任意多边形的Delaunay三角剖分(计算几何作业)
Delaunay三角剖分算法(三维)
使用Matlab实现了delaunay三角剖分,delaunay三角形具有一些非常好的性质,可以用来生成Voronoi图。
Delaunay三角剖分算法的python实现,含有详细的算法实现过程。
本书对二维平面和三维空间限定Delaunay三角剖分技术进行了系统全面介绍,给出了可以在任意点、线段和平面片的限定条件下完成限定Delaunay三角剖分及网格优化的算法,并论证了算法的有效性。本书可供计算机等领域的...
基于python语言的Delaunay三角剖分算法实现
三维折剖面Delaunay三角剖分在三维地质建模和其他领域具有广泛应用。目前常用的方法是将其投影到二维平面三角剖分。该方法有三点不足:(1)违反Delaunay三角剖分优化准则;(2)悬三角形问题;(3)投影多值问题。...
在二维平面内进行Delaunay三角剖分,再将结果返回到三维空间内。实验结果表明,算法能够构建质量较好的三角网格。由于该算法将点云的三角剖分转换到低维空间,通过实验结果对比本算法与其他算法效果,证明该方法能够...
Delaunay 三角剖分 算法的实现和渲染 代码&文档