凸多边形最优三角剖分.docx

凸多边形最优三角剖分2007-07-13 00:03一、 问题描述多边形是平面上一条分段线性的闭曲线也就是说，多边形是由一系列首尾相接 的直线段组成的组成多边形的各直线段称为该多边形的边多边形相接两条边 的连接点称为多边形的顶点若多边形的边之间除了连接顶点外没有别的公共 点，则称该多边形为简单多边形一个简单多边形将平面分为3个部分：被包围 在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平 面上其余的点构成了多边形的外部当一个简单多边形及其内部构成一个闭凸集 时，称该简单多边形为凸多边形也就是说凸多边形边界上或内部的任意两点所 连成的直线段上所有的点均在该凸多边形的内部或边界上通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P={v0,vi ,„ ,vn-i} 表示具有n条边v v , v v ,…，v v的一个凸多边形，其中，约定v二v0 1 1 2 n-1 n 0 n若vi与v.是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦弦 将多边形分割成凸的两个子多边形{v ,v ,„ ,v } 和 {v ,v ,„ ,v }多边形 的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合T。

图1是一个凸多边形的两个不同的三角剖分fV55JV4旳f图1 一个凸多边形的2个不同的三角剖分在凸多边形P的一个三角剖分T中，各弦互不相交，且弦数已达到最大，即P 的任一不在T中的弦必与T中某一弦相交在一个有n个顶点的凸多边形的三角 剖分中，恰好有n-3条弦和n-2个三角形凸多边形最优三角剖分的问题是：给定一个凸多边形P={v ,v ,„ ,v }以及定 义在由多边形的边和弦组成的三角形上的权函数①要求确定该凸多边形的一 个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小可以定义三角形上各种各样的权函数3例如：定义 3 (vvv) = |vv| + |vv| + |vv|,其中，|vv|是点v到v的欧氏距离相应i j k i j i k k j i j i j于此权函数的最优三角剖分即为最小弦长三角剖分二、 算法思路凸多边形的三角剖分与表达式的完全加括号方式之间具有十分紧密的联系正如 所看到过的，矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号方式这些问题之间的相关性可从它们所对应的完全二叉树的同构性看出一个表达式的完全加括号方式对应于一棵完全二叉树，人们称这棵二叉树为表达式的语法树。

例如，与完全加括号的矩阵连乘积((A (AA))(A (AA)))相对应的1 2 3 4 5 6语法树如图2(a)所示图 2 表达式语法树与三角剖分的对应语法树中每一个叶子表示表达式中一个原子在语法树中，若一结点有一个表示 表达式 E 的左子树，以及一个表示表达式 E 的右子树，则以该结点为根的子树1r表示表达式(EE)O因此，有n个原子的完全加括号表达式对应于惟一的一棵有 1rn 个叶结点的语法树，反之亦然凸多边形｛v ,v，…,v ｝的三角剖分也可以用语法树来表示例如，图1(a)中 凸多边形的三角剖分可用图2(b)所示的语法树来表示该语法树的根结点为边 vv ,三角剖分中的弦组成其余的内部结点多边形中除vv边外的每一条边是0 6 0 6语法树的一个叶结点树根vv是三角形vvv的一条边，该三角形将原多边形0 6 0 3 6分为3个部分:三角形vvv,凸多边形｛v ,v，…，v ｝和凸多边形｛v ,v，…，v ｝ o 三角形vvv的另外两条边：即弦vv和0vv1为根的两个儿子以它们为根的子0 3 6 3 6 0 3树分别表示凸多边形｛v ,v，„ ，v ｝和凸多边形｛v ,v，„，v ｝的三角剖分。

0 1 3 3 4 6在一般情况下，一个凸n边形的三角剖分对应于一棵有n-1个叶子的语法树反 之，也可根据一棵有n-1个叶子的语法树产生相应的一个凸n边形的三角剖分 也就是说，凸n边形的三角剖分与n-1个叶子的语法树之间存在一一对应关系 由于n个矩阵的完全加括号乘积与n个叶子的语法树之间存在一一对应关系，因 此n个矩阵的完全加括号乘积也与凸(n+1)边形的三角剖分之间存在一一对应关系图2的（a）和（b）表示出了这种对应关系，这时n=6矩阵连乘积A A ..A中 的每个矩阵A对应于凸（n+1）边形中的一条边v V三角剖分中的一条弦v v , i

1 2 n三、 实验源程序四、 测试结果给定的七个顶点坐标分别为（8，26）、（0，20）、（0，10）、（10，0）、（22，12）、（27，21）、（15，26），测试结果如下：顶一ffg奄等一奄毬即 g塑坐坐坐力勺勺勺勺勺勺112 3 4点融馬馬融点 点 人顶顶顶顶顶顶码形需形 貝入入入入入入ffl角角甬审该程序有一定的灵活性，用户可以自己选择顶点的个数以及顶点坐标，并对顶点坐标进行分析，判断这些顶点能否构成一个凸多边形，例如输入四个点坐标（0，0）、（0，10）、（4，4）、（10，0），这四个点构成的多边形显然是一个凹多边形，测试结果为：10 0cont inu.ea 19気 *D:Vlicrosoft Fisual Stu顶垂阪莎莎卿to 矍坐坐坐边y 边的的的的多血 多前V1UZU3凸 y 凸点点点点成綁 入顶顶顶顶构客 ^<入入人法 I K —r -^n« J庐五、总结(1)凸多边形的最优三角剖分本来是一个几何问题，但通过分析，它本质上于 矩阵连乘积的最优计算次序问题极为相似，从而可以将问题进行转化，用动态规 划算法有效的解决这个问题2)本实验的七个顶点坐标数据是给定的，可以构成一个凸多边形，但对于未 知的数据，事先并不知道所给数据能否构成一个凸多边形。

所以我在这里多做了 一点工作，就是如何判断所给的顶点能否构成凸多边形解决思路是：用两点式推导直线一般方程，设已知的两点坐标分别为(xl,yl),(x2,y2),得x*(y1-y2)-y*(x1-x2)+(x1-x2)*y2-x1*(y1-y2)=0,令 a二yl-y2,b=xl-x2,c=(xl-x2) *yl-xl*(yl-y2)即 ax+by+c=O对于任一条直线 ax+by+c=0 (a,b 不同时为 0) ，则其余非构成直线的点的坐标 (x,y)代入直线方程，若ax+by+c>0,则该点在直线右侧；若ax+by+c<0,则点在直 线左侧;若ax+by+c=O,则在直线上例：有一直线5x-6y+3=0, —点(5,0)代入直 线方程，则方程左式>0所以点(5,0)在直线右侧程序中用指针v来记录各点坐标，按逆时针依次输入用*total来记录坐标在 直线方程中的值用 p 和 q 分别记录点代入方程所得值的正或负的点的个数若 是凸多边形，则应全为正或全为负，即p>0和q>0不同时成立；若是凹多边形， 则p>0和q>0同时成立而其中若p=0和q=0同时成立，则不能构成多边形图形学:名词解释 (1)2007-07-13 00:103D三维(three dimension)。

客观世界中静止的物体都是三维的，在计算机图形 学中常在一定的坐标系中用(x, y，z)坐标系列表示物体3D modeling3D 建模用三维坐标来描述物体的形状在各种计算机图形应用领域中有不同 的三维建模方法，用不同的算法来描述这些领域中的物体和对象3D transformation3D变换在三维空间中把物体的三维坐标从一个位置变换至另一位置，或者从一个坐标系变换至另一坐标系这是一种对物体的三维坐标(x, y, z)进行数 据操作的一种形式3D transformation sequence3D 变换序列把客观世界中的物体在计算机屏幕上显示,通常需要进行一系列 坐标变换,如从物体的相对坐标系变换至计算机屏幕需要经过平移、旋转、视 点投影变换等一系列坐标变换4D四维( four dimension) 在计算机图形学中描述客观世界除了用三维坐标来描述物体的形状外，还用时间t作为第四维来描述过程，通常用(x, y, z, t) 表示6D六维(six dimension )在计算机图形学三维应用过程中(例如：模拟仿真、 虚拟现实应用等)用六个自由度( x, y, z 坐标、偏角、倾角、仰角)来描述物 体的运动。

a stream一段流AABB沿坐标轴的包围盒(axis-aligned bounding boxes)ABI二进制接口Absorption吸收Accumulation Buffer累积缓存累积缓存同颜色缓存一样也保存颜色数据，但它只保存RGBA颜色数 据,而不能保存颜色索引数据(因为在颜色表方式下使用累积缓存其结果不确 定)这个缓存一般用于累积一系列图像,从而形成最后的合成图像利用这 种方法,可以进行场景反走样操作action mapping动作映射algorithm算法一般指在用电脑软件解决问题时所用的数学方法或程序实现过程通常 用数学公式或程序框图来描述aliasing走样在进行渲染着色的时候，所绘制的图元直接按照所赋给的颜色绘制象素， 就会产生锯齿状的边，这就是走样alpha blending阿尔法混合一种让图像产生透明感的技术alpha channelalpha 通道 alpha color componentalpha 颜色组件 alpha constantalpha 常量alpha value阿尔法值颜色成分中的第四个成分Alpha值不用于直接显示，一般用于颜色 的混合Ambient Light环境光analog模拟animated deformation动态自由变形AntiAliasing反走样(anti-aliasing)。

根据图形单元的象素覆盖区域来确定象素的颜色值, 这种渲染绘制技术就是反走样APIs应用程序编程接口 application specific clipping特定裁剪应用图形单元在视点坐标系的平面上进行ARB体系结构评审委员会( Architecture Review Board )Architecture Review Board 体系结构评审委员会( ARB)area fill 区域填充即用指定的颜色和模式填充多边形或三角形区域围绕区域的线条即 为边界这在计算机图形学中是基本的绘图方式articulated motion关节运动一个与其它三维图形相连接的部件的运动这种运动在动画或模拟 中经常用到AxDF轴变形（axial Deformation）axial Deformation轴变形（ AxDF）axis aligned bounding boxes沿坐标轴的包围盒（ AABB）。