Delaunay三角剖分(Delaunay+Triangulation)相关知识(可编辑).doc

Delaunay三角剖分(DelaunayTriangulation)相关知识(可编辑)Delaunay三角剖分(DelaunayTriangulation)相关知识记忆过往总有一个人需要这些知识。本博客信息正在迁往////0>.[置顶]Delaunay三角剖分DelaunayTriangulation相关知识分类:Voronoi2012-02-1311:&&代码大话点集的三角剖分(Triangulation),对数值分析(比如有限元分析)以及图形学来说,都是极为重要的一项预处理技术。尤其是Delaunay三角剖分,由于其独特性,关于点集的很多种几何图都和Delaunay三角剖分相关,如Voronoi图,EMST树,Gabriel图等。Delaunay三角剖分有几个很好的特性:,“最接近于规则化的“的三角网。(任意四点不能共圆)。概念及定义二维实数域二维平面上的三角剖分定义1:假设V是二维实数域上的有限点集,边e是由点集中的点作为端点构成的封闭线段,E为e的集合。那么该点集V的一个三角剖分TV,E是一个平面图G,该平面图满足条件:,平面图中的边不包含点集中的任何点。。,且所有三角面的合集就是点集V的凸包。那什么是Delaunay三角剖分呢?不过是一种特殊的三角剖分罢了。从Delaunay边说起。Delaunay边定义2:假设E中的一条边e(两个端点为a,b),e若满足下列条件,则称之为Delaunay边:存在一个圆经过a,b两点,圆内不含点集V中任何的点,这一特性又称空圆特性。Delaunay三角剖分定义3:如果点集V的一个三角剖分T只包含Delaunay边,那么该三角剖分称为Delaunay三角剖分。我们看几个图:由上面的图引出Delaunay三角剖分的另一种定义:定义4:假设T为V的任一三角剖分,则T是V的一个Delaunay三角剖分,当前仅当T中的每个三角形的外接圆的内部不包含V中任何的点。Voronoi图定义5:V的Voronoi图是由多边形区域的集合(有些区域可能不是闭合的),该区域仅含点集中的一个点v,区域中的任何位置到v的距离都比该位置到点集中其它所有点的距离短。由Voronoi图和Delaunay三角剖分的关系,可以引出另一个Delaunay三角剖分的定义:定义6:将Voronoi图相邻区域(共边的区域)中的点连接起来构成的图,称为Delaunay三角剖分。如下图:概念部分到此,下面看看怎么求Delaunay三角剖分。计算Delaunay三角剖分1计算Delaunay三角剖分问题1:计算二维Delaunay三角剖分问题输入:二维实数域上的点集V问题输出:Delaunay三角剖分DTV,。用得较多的是基于定义3或4的算法。目前常用的算法又分为好几种,被不同的家伙发现。什么扫描线法(Sweepline),随机增量法(Incremental),分治法(DivideandConquer)啊等等。随机增量法(Incremental)其中,随机增量法较为简单,遵循增量法的一贯思路,即按照随机的顺序依次插入点集中的点,在整个过程中都要维护并更新一个与当前点集对应的Delaunay三角剖分。考虑插入vi点的情况,由于前面插入所有的点v1,v2,,vi-1构成的DTv1,v2,,vi-1已经是Delaunay三角剖分,只需要考虑插入vi点后引起的变化,并作调整使得DTv1,v2,,vi-1Uvi成为新的Delaunay三角剖分DTv1,v2,,vi。插入调整过程:首先确定vi落在哪个三角形中(或边上),然后将vi与三角形三个顶点连接起来构成三个三角形(或与共边的两个三角形的对顶点连接起来构成四个三角形),由于新生成的边以及原来的边可能不是或不再是Delaunay边,故进行边翻转来调整使之都成为Delaunay边,从而得出DTv1,v2,,vi。其Pseudocode如下:AlgorithmIncrementalDelaunayVInput:由n个点组成的二维点集VOutput::wecanusetriangleabc,a0,3M,b-3M,-3M,c3M,0,M|x1|,|x2|,|x3|,U|y1|,|y2|,|y3|,,b,-1to