Delaunay三角剖分.doc

Delaunay三角剖分来源:相关文章:OpenCV三角剖分的遍历和纹理映射:Delaunay三角剖分是1934年发明的将空间点连接为三角形,使得所有三角形中最小角最大的一个技术。如果你熟悉计算机图形学,你便会知道Delaunay三角剖分是变现三维形状的基础。如果我们在三维空间渲染一个,我们可以通过这个物体的投影来建立二维视觉图,并用二维Delaunay三角剖分来分析识别该物体,或者将它与实物相比较。Delaunay剖分是连接计算机视觉与计算机图形学的桥梁。然而使用OpenCV实现三角剖分的不足之处就是OpenCV只实现了二维的Delaunay剖分。如果我们能够对三维点进行三角剖分,也就是说构成立体视觉,那么我们可以在三维的计算机图形和计算机视觉进行无缝的转换。然而二维三角剖分通常用于计算机视觉中标记空间目标的特征或运动场景跟踪,目标识别,或两个不同的摄像机的场景匹配(如图从立体图像中获得深度信息)。下面内容摘自:1三角剖分与Delaunay剖分的定义如何把一个离散几何剖分成不均匀的三角形网格,这就是离散点的三角剖分问题,散点集的三角剖分,对数值分析以及图形学来说,都是极为重要的一项处理技术。该问题图示如下:【定义】三角剖分:假设V是二维实数域上的有限点集,边e是由点集中的点作为端点构成的封闭线段,E为e的集合。那么该点集V的一个三角剖分T=(V,E)是一个平面图G,该平面图满足条件:1、除了端点,平面图中的边不包含点集中的任何点。2、没有相交边。(边和边没有交叉点)3、平面图中所有的面都是三角面,且所有三角面的合集是散点集V的凸包。,它是一种特殊的三角剖分。先从Delaunay边说起:【定义】Delaunay边:假设E中的一条边e(两个端点为a,b),e若满足下列条件,则称之为Delaunay边:存在一个圆经过a,b亮点,圆内(注意是圆内,圆上最多三点共圆)不含点集V中任何其他的点,这一特性又称空圆特性。【定义】Delaunay三角剖分:如果点集V的一个三角剖分T只包含Delaunay边,那么该三角剖分称为Delaunay三角剖分。,必须符合两个重要的准则:1、空圆特性:Delaunay三角网是唯一的(任意四点不能共圆),在Delaunay三角形网中任一三角形的外接圆范围内不会有其它点存在。如下图所示:2、最大化最小角特性:在散点集可能形成的三角剖分中,Delaunay三角剖分所形成的三角形的最小角最大。从这个意义上讲,Delaunay三角网是“最接近于规则化的”三角网。具体的说是在两个相邻的三角形构成凸四边形的对角线,在相互交换后,两个内角的最小角不再增大。如下图所示::1、最接近:以最接近的三点形成三角形,且各线段(三角行的边)皆不相交。2、唯一性:不论从区域何处开始构建,最终都将得到一致的结果。3、最优性:任意两个相邻三角形构成的凸四边形的对角线如何可以互换的话,那么两个三角形六个内角中最小角度不会变化。4、最规则:如果将三角网中的每个三角形的最小角进行升序排列,则Delaunay三角网的