Delaunay角剖分.docVIP

Delaunay三角剖分 来源：/raby_gyl/article/details相关文章：OpenCV三角剖分的遍历和纹理映射：/raby_gyl/article/detailsDelaunay三角剖分是1934年发明的将空间点连接为三角形，使得所有三角形中最小角最大的一个技术。 如果你熟悉计算机图形学，你便会知道Delaunay三角剖分是变现三维形状的基础。如果我们在三维空间渲染一个，我们可以通过这个物体的投影来建立二维视觉图，并用二维Delaunay三角剖分来分析识别该物体，或者将它与实物相比较。Delaunay剖分是连接计算机视觉与计算机图形学的桥梁。然而使用OpenCV实现三角剖分的不足之处就是OpenCV只实现了二维的Delaunay剖分。如果我们能够对三维点进行三角剖分，也就是说构成立体视觉，那么我们可以在三维的计算机图形和计算机视觉进行无缝的转换。然而二维三角剖分通常用于计算机视觉中标记空间目标的特征或运动场景跟踪，目标识别，或两个不同的摄像机的场景匹配（如图从立体图像中获得深度信息）。 下面内容摘自：/RenLiQQ/archive/2008/02/06/1065399.html 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剖分是一种三角剖分的标准，实现它有多种算法。 由表可以看出，三角网生成法的时间效率最低，分治算法的时间效率最高，逐点插入法效率居中。由于区域生长法本质的缺陷，导致其效率受限，这种方法在80年代中期以后已经很少使用。分治算法时间效率相对较高，但是由于其递归执行，所以需要较大的