凸多边形最优三角剖分 2007-07-13 00:03
一、 问题描述
多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。
通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P={v0 ,v1 ,? ,vn-1}表示具有n条边v0v1，v1v2，? ,vn-1vn的一个凸多边形，其中，约定v0=vn。 若vi与vj是多边形上不相邻的两个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成凸的两个子多边形{vi ,vi+1 ,? ,vj}和{vj ,vj+1 ,? ,vi}。多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合T。图1是一个凸多边形的两个不同的三角剖分。
图1 一个凸多边形的2个不同的三角剖分
在凸多边形P的一个三角剖分T中，各弦互不相交，且弦数已达到最大，即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角剖分中，恰好有n-3条弦和n-2个三角形。
凸多边形最优三角剖分的问题是：给定一个凸多边形P={v0 ,v1 ,? ,vn-1}以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。 可以定义三角形上各种各样的权函数ω。例如：定
义 ω(vivjvk)=|vivj|+|vivk|+|vkvj|，其中，|vivj|是点vi到vj的欧氏距离。相应
于此权函数的最优三角剖分即为最小弦长三角剖分。 二、 算法思路
凸多边形的三角剖分与表达式的完全加括号方式之间具有十分紧密的联系。正如所看到过的，矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号方式。这些问题之间的相关性可从它们所对应的完全二叉树的同构性看出。
一个表达式的完全加括号方式对应于一棵完全二叉树，人们称这棵二叉树为表达式的语法树。例如，与完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))相对应的语法树如图2(a)所示。
图2 表达式语法树与三角剖分的对应
语法树中每一个叶子表示表达式中一个原子。在语法树中，若一结点有一个表示表达式E1的左子树，以及一个表示表达式Er的右子树，则以该结点为根的子树表示表达式(E1Er)。因此，有n个原子的完全加括号表达式对应于惟一的一棵有
n个叶结点的语法树，反之亦然。 凸多边形{v0 ,v1 ,? ,vn-1}的三角剖分也可以用语法树来表示。例如，图1(a)中凸多边形的三角剖分可用图2(b)所示的语法树来表示。该语法树的根结点为边v0v6，三角剖分中的弦组成其余的内部结点。多边形中除v0v6边外的每一条边是语法树的一个叶结点。树根v0v6是三角形v0v3v6的一条边，该三角形将原多边形分为3个部分：三角形v0v3v6，凸多边形{v0 ,v1 ,? ,v3}和凸多边形{v3 ,v4 ,? ,v6}。三角形v0v3v6的另外两条边，即弦v3v6和v0v3为根的两个儿子。以它们为根的子树分别表示凸多边形{v0 ,v1 ,? ,v3}和凸多边形{v3 ,v4 ,? ,v6}的三角剖分。 在一般情况下，一个凸n边形的三角剖分对应于一棵有n-1个叶子的语法树。反之，也可根据一棵有n-1个叶子的语法树产生相应的一个凸n边形的三角剖分。也就是说，凸n边形的三角剖分与n-1个叶子的语法树之间存在一一对应关系。由于n个矩阵的完全加括号乘积与n个叶子的语法树之间存在一一对应关系，因此n个矩阵的完全加括号乘积也与凸(n+1)边形的三角剖分之间存在一一对应关
系。图2的(a)和(b)表示出了这种对应关系，这时n=6。矩阵连乘积A1A2..A6中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，i 事实上，矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的一个特殊情形。 对于给定的矩阵链A1A2..An，定义一个与之相应的凸(n+1)边形 P={v0 ,v1 ,? ,vn}，使得矩阵Ai与凸多边形的边vi-1vi一一对应。若矩阵Ai的维数为pi-1×pi,i=1,2,?,n，则定义三角形vivjvk上的权函数值为： ω(vivjvk)=pipjpk。依此权函数的定义，凸多边形P的最优三角剖分所对应的语法树给出矩阵链A1A2..An的最优完全加括号方式。 三、 实验源程序 四、 测试结果 给定的七个顶点坐标分别为(8,26)、(0,20)、(0,10)、(10,0)、(22,12)、(27,21)、(15,26)，测试结果如下： 该程序有一定的灵活性，用户可以自己选择顶点的个数以及顶点坐标，并对顶点坐标进行分析，判断这些顶点能否构成一个凸多边形，例如输入四个点坐标 (0,0)、(0,10)、(4,4)、(10,0)，这四个点构成的多边形显然是一个凹多边形，测试结果为： 五、 总结 （1）凸多边形的最优三角剖分本来是一个几何问题，但通过分析，它本质上于矩阵连乘积的最优计算次序问题极为相似，从而可以将问题进行转化，用动态规划算法有效的解决这个问题。 （2）本实验的七个顶点坐标数据是给定的，可以构成一个凸多边形，但对于未知的数据，事先并不知道所给数据能否构成一个凸多边形。所以我在这里多做了一点工作，就是如何判断所给的顶点能否构成凸多边形。解决思路是： 用两点式推导直线一般方程，设已知的两点坐标分别为(x1,y1),(x2,y2),得 x*(y1-y2)-y*(x1-x2)+(x1-x2)*y2-x1*(y1-y2)=0, 令a=y1-y2,b=x1-x2,c=(x1-x2)*y1-x1*(y1-y2)。即ax+by+c=0。 对于任一条直线ax+by+c=0 (a,b不同时为0)，则其余非构成直线的点的坐标(x,y)代入直线方程，若ax+by+c>0,则该点在直线右侧；若ax+by+c<0,则点在直线左侧;若ax+by+c=0,则在直线上。例：有一直线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:10 3D 三维（three dimension）。客观世界中静止的物体都是三维的，在计算机图形学中常在一定的坐标系中用（x，y，z）坐标系列表示物体。 3D modeling 3D建模。用三维坐标来描述物体的形状。在各种计算机图形应用领域中有不同的三维建模方法，用不同的算法来描述这些领域中的物体和对象。 3D transformation 3D变换。在三维空间中把物体的三维坐标从一个位置变换至另一位置，或者从 一个坐标系变换至另一坐标系。这是一种对物体的三维坐标（x，y，z）进行数据操作的一种形式。 3D transformation sequence 3D变换序列。把客观世界中的物体在计算机屏幕上显示，通常需要进行一系列坐标变换，如从物体的相对坐标系变换至计算机屏幕需要经过平移、旋转、视点投影变换等一系列坐标变换。 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