凸多边形最优三角剖分

凸多边形最优三角剖分一、 问题描述多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为3个部分：被包围在多边形内的所有点构成了多边形的内部；多边形本身构成多边形的边界；而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时，称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。通常，用多边形顶点的逆时针序列来表示一个凸多边形，即P=｛v0,v1，…，vn-1｝表示具有n条边v0v1，v1v2，-，vn-1vn的一个凸多边形，其中，约定v0=vn。若v与Vj是多边形上不相邻的两个顶点，则线段VjVj称为多边形的一条弦。弦将多边形分割成凸的两个子多边形｛Vi,vi+1，…，Vj｝和｛Vj,Vj+1，…，Vj｝。多边形的三角剖分是一个将多边形分割成互不相交的三角形的弦的集合T。图1是一个凸多边形的两个不同的三角剖分。图1一个凸多边形的2个不同的三角剖分在凸多边形P的一个三角剖分T中，各弦互不相交，且弦数已达到最大，即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角剖分中，恰好有n-3条弦和n-2个三角形。凸多边形最优三角剖分的问题是：给定一个凸多边形P=｛v0,v1，…，vn-1｝以及定义在由多边形的边和弦组成的三角形上的权函数3。要求确定该凸多边形的一个三角剖分，使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。可以定义三角形上各种各样的权函数3。例如：定义w(vivvk)=|viv|+|vivk|+|vkv|，其中，MV是点v到v的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。二、 算法思路凸多边形的三角剖分与表达式的完全加括号方式之间具有十分紧密的联系。正如所看到过的，矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号方式。这些问题之间的相关性可从它们所对应的完全二叉树的同构性看出。一个表达式的完全加括号方式对应于一棵完全二叉树，人们称这棵二叉树为表达式的语法树。例如，与完全加括号的矩阵连乘积(内(人2钿)(人4代人6)))相对应的语法树如图2(a)所示。<*) (b)图2表达式语法树与三角剖分的对应语法树中每一个叶子表示表达式中一个原子。在语法树中，若一结点有一个表示表达式左子树，以及一个表示表达式Er的右子树，则以该结点为根的子树表示表达式仁店』。因此，有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中的每个矩阵入对应于凸(n+1)边形中的一条边％‘。三角剖分中的一条弦《马，i<j，对应于矩阵连乘积A[i+1:j]。事实上，矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的一个特殊情形。对于给定的矩阵链A1A2..An，定义一个与之相应的凸(n+1)边形P=｛v0,v1，…，vn｝，使得矩阵A与凸多边形的边vi-1v一一对应。若矩阵A的维数为pi-1xpi，i=1,2，_，n，则定义三角形vvvk上的权函数值为：w(vivjvk)=pipjpko依此权函数的定义，凸多边形P的最优三角剖分所对应的语法树给出矩阵链A1A2..An的最优完全加括号方式。三、 实验源程序

新建一个类CTriangle,Classtype选择GenericClass。Triangle.h代码typedefstruct{intx;inty;}point;classCTriangle{public:boolRun();CTriangle();virtual~CTriangle();private:〃用递归的方法输出剖分后的各个三角形voidTraceback(inti,intj,int**s);〃计算最优值算法boolminWeightTriangulation();〃处理键盘输入，同时判断能否构成一个凸多边形boolInput();〃计算三角形权值的函数intw(pointX,pointY,pointZ);//计算平面上任意两点间距离的函数〃记录最优三角剖分中所有三角形信息int**s;〃记录最优三角剖分中所有三角形信息int**s;〃记录最优三角剖分所对应的权函数值int**t;〃记录凸多边形各顶点坐标point*v;//记录坐标在直线方程中的值int*total;intM;};Triangle.cpp代码#defineN50#include<iostream.h>#include<math.h>#include<stdlib.h>#include"Triangle.h"CTriangle::CTriangle(){M=0;t=newint*[N];s=newint*[N];for(inti=0;i<N;i++){t[i]=newint[N];s[i]=newint[N];v=newpoint[N];total=newint[N];}CTriangle::~CTriangle(){for(inti=0;i<N;i++){delete[]t[i];delete[]s[i];}delete[]t;delete[]s;delete[]v;delete[]total;}intCTriangle::distance(pointX,pointY){intdis=(Y.x-X.x)*(Y.x-X.x)+(Y.y-X.y)*(Y.y-X.y);return(int)sqrt(dis);}intCTriangle::w(pointX,pointY,pointZ){returndistance(X,Y)+distance(Y,Z)+distance(Z,X);boolCTriangle::Input(){intm;inta,b,c;cout<<"请输入凸多边形顶点个数："；cin»m;M=m-1;for(inti=0;i<m;i++){cout«'输入顶点v"<<i<<"的坐标："；cin»v[i].x»v[i].y;}〃根据顶点坐标判断是否能构成一个凸多边形for(intj=0;j<m;j++){intp=0;intq=0;if(m-1==j){a=v[m-1].y-v[0].y;b=v[m-1].x-v[0].y;c=b*v[m-1].y-a*v[m-1].x;}elsereturntrue;a=v[j].y-v[j+1].y;b=v[j].x-v[j+1].x;c=b*v[j].y-a*v[j].x;}for(intk=0;k<m;k++){total[k]=a*v[k].x-b*v[k].y+c;if(total[k]>0){P=P+1；}elseif(total[k]<0){q=q+1;}}if((p>0&&q>0)||(p==0&&q==0)){cout<<"无法构成凸多边形！"<<endl;exit(1);}}elsereturnfalse;}boolCTriangle::minWeightTriangulation(){if(NULL==v)returnfalse;for(inti=1;i<=M;i++)t[i][i]=0;for(intr=2;r<=M;r++)for(inti=1;i<=M-r+1;i++){intj=i+r-1;t[i][j]=t[i+1][j]+w(v[i-1],v[i],v[j]);s[i][j]=i;for(intk=i+1;k<i+r-1;k++){intu=t[i][k]+t[k+1][j]+w(v[i-1],v[k],v[j]);if(u<t[i][j]){t[i][j]=u;s[i][j]=k;if(NULL!=v)if(CTriangle::minWeightTriangulation())returntrue;}voidCTriangle::Traceback(inti,intj,int**s){if(i==j)return;/*{cout<<"分成的三角形依次为："<<endl;cout<<"v"<<i-1<<"v"<<i<<"v"<<j<<endl;}else*/Traceback(i,s[i][j],s);Traceback(s[i][j]+1,j,s);cout«'三角形：v"<<i-1<<"v"<<s[i][j]<<"v"<<j<<endl;}boolCTriangle::Run(){if(lnput()){四、 测试结果

{CTriangle::Traceback(1,M,s);cout<<endl;cout<<"最优权值之和为："<<t[1][M]«endl;returntrue;}elsereturnfalse;}elsereturnfalse;}main.cpp代码#include"Triangle.h"voidmain(){CTriangletriangle;triangle.Run();}给定的七个顶点坐标分别为(8,26)、(0,20)、(0,10)、(10,0)、(22,12)、(27,21)、(15,26),测试结果如下:该程序有一定的灵活性，用户可以自己选择顶点的个数以及顶点坐标，并对顶点坐标进行分析，判断这些顶点能否构成一个凸多边形，例如输入四个点坐标(0,0)、(0,10)、(4,4)、(10,0)，这四个点构成的多边形显然是一个凹多边形，测试结果为：五、 总结凸多边形的最优三角剖分本来是一个几何问题，但通过分析，它本质上于矩阵连乘积的最优计算次序问题极为相似，从而可以将问题进行转化，用动态规划算法有效的解决这个问题。本实验的七个顶点坐标数据是给定的，可以构成一个凸多边形，但对于未知的数据，事先并不知道所给数据能否构成一个凸多边形。所以我在这里多做了一点工作，就是如何判断所给的顶点能否构成凸多边形。解决思路是：用两点式推导直线一般方程，设已知的两点坐标分别为(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),则其余非构成直线的点的坐标