Delaunay三角剖分及matlab实例.pdfVIP

Delaunay三三⾓⾓剖剖分分及及matlab实实例例

鉴于Delaunay三⾓剖分在点云拟合⽅⾯有不错的应⽤，现对该算法的原理进简单的汇总~

原原理理部部分分

1、、三三⾓⾓剖剖分分与与Delaunay剖剖分分的的定定义义

如何把⼀个离散⼏何剖分成不均匀的三⾓形⽹格，这就是离散点的三⾓剖分问题，散点集的三⾓剖分，对数值分析以及图形学来说，都是极为重要的⼀项处理技术。该问题图⽰如下：

1.1三三⾓⾓剖剖分分定定义义

【定义】三⾓剖分：假设V是⼆维实数域上的有限点集，边e是由点集中的点作为端点构成的封闭线段，E为e的集合。那么该点集V的⼀个三⾓剖分T=(V,E)是⼀个平⾯图G,该平⾯图满⾜条

件：

1、除了端点，平⾯图中的边不包含点集中的任何点。

2、没有相交边。//边和边没有交叉点

3、平⾯图中所有的⾯都是三⾓⾯，且所有三⾓⾯的合集是散点集V的凸包。

//：⽤不严谨的话来讲，给定⼆维平⾯上的点集，凸包就是将最外层的点连接起来构成的凸多边型，它能包含点集中所有的点。

1.2Delaunay三三⾓⾓剖剖分分的的定定义义

在实际中运⽤的最多的三⾓剖分是Delaunay三⾓剖分，它是⼀种特殊的三⾓剖分。先从Delaunay边说起：

【定义】Delaunay边：假设E中的⼀条边e(两个端点为a,b)，e若满⾜下列条件，则称之为Delaunay边：存在⼀个圆经过a,b亮点，圆内（注意是园内，圆上最多三点共圆）不含点集V中任何

其他的点，这⼀特性⼜称空圆特性。

【定义】Delaunay三⾓剖分：如果点集V的⼀个三⾓剖分T只包含Delaunay边，那么该三⾓剖分称为Delaunay三⾓剖分。

1.3Delaunay三三⾓⾓剖剖分分的的准准则则

要满⾜Delaunay三⾓剖分的定义，必须符合两个重要的准则：

1、空圆特性：Delaunay三⾓⽹是唯⼀的（任意四点不能共圆），在Delaunay三⾓形⽹中任⼀三⾓形的外接圆范围内不会有其它点存在。如下图所⽰：

2、最⼤化最⼩⾓特性：在散点集可能形成的三⾓剖分中，Delaunay三⾓剖分所形成的三⾓形的最⼩⾓最⼤。从这个意义上讲，Delaunay三⾓⽹是“最接近于规则化的”三⾓⽹。具体的说是在

两个相邻的三⾓形构成凸四边形的对⾓线，在相互交换后，两个内⾓的最⼩⾓不再增⼤。如下图所⽰：

1.4Delaunay三三⾓⾓剖剖分分的的特特性性

以下是Delaunay剖分所具备的优异特性：

1、最接近：以最接近的三点形成三⾓形，且各线段（三⾓的边）皆不相交。

2、唯⼀性：不论从区域何处开始构建，最终都将得到⼀致的结果。

3、最优性：任意两个相邻三⾓形构成的凸四边形的对⾓线如果可以互换，那么两个三⾓形六个内⾓中最⼩⾓度不会变化。

4、最规则：如果将三⾓⽹中的每个三⾓形的最⼩⾓进升序排列，则Delaunay三⾓⽹的排列得到的数值最⼤。

5、区域性：新增、删除、移动某⼀个顶点只会影响邻近的三⾓形。

6、具有凸边形的外壳：三⾓⽹最外层的边界形成⼀个凸多边形的外壳。

1.5局局部部最最优优化化处处理理

理论上为了构造Delaunay三⾓⽹，Lawson提出的局部优化过程LP(LocalptimizationProcedure),⼀般三⾓⽹经过LP处理，即可确保为Delaunay三⾓⽹，其基本做法如下所⽰：

1、将两个具有共同边的三⾓形合成⼀个多边形。

2、以最⼤空圆准则作检查，看其第四个顶点是否在三⾓形的外接圆内。

3、如果在，修正对⾓线即将对⾓线对调，即完成局部优化过程的处理。

LP处理过程如下图所⽰：

1.6三三维维空空间间情情形形

Delaunay三⾓⽹格的性质可以推⼴到⾼维。⼀个三维点集的三⾓剖分是由四⾯体构成。下图显⽰了⼀个由两个四⾯体构成的简单三维Delaunay三⾓剖分。⼀个四⾯体的外接球来说明空接球

准则。

2.Delaunay剖剖分分的的算算法法

Delaunay剖分是⼀种三⾓剖分的标准，实现它有多种算法。

2.1.Lawson算算法法

逐点插⼊的Lawson算法是Lawson在1977年提出的，该算法思路简单，易于编程实现。基本原理为：⾸先建⽴⼀个⼤的三⾓形或多边形，把所有数据点包围起来，向其中插⼊⼀点，该点与

包含它的三⾓形三个顶点相连，形成三个新的三⾓形，然后逐个对它们进空外接圆检测，同时⽤Lawson设计的局部优化过程L