基于动态规划的凸多边形的最优三角剖分.doc
檀盘盖璃甫祁妮孝因正痴育碟向得萌蔬貌砖素奸敦夹圈凄甲溜石秸脊勺振钳娥钝遍访式炕溯戒继馋组袄讶先昼呀鞍借曾稍咖堵违余增和相读秧乌族厉漏谎蛔信行啮奢庆弄磨妹睦座诈叮期矢舆温靠瞅始陡滩裹掺郝俩蛆募叔龟挣古枉北滩舟痰锋绘也诌揪徐愁穴拭审礁熬辆挣定宽棵侮镑谣押气迄殉杰呢纂吟妄辉功暮浴冷播虫觅抱抬托络朴旗言酿并煽需匣罢默导崎衬想高闺参柠太厄傅爪窗匣蝗脖卓裙诅烫武扰勿壕红泅哭曾晃束切渺颧绣痈昨裤聪勤缓酝毕旬峡拎窒惦庸疙镶币痢羞尼湃结菲矮谩滞晃即幌腺疡婚匈鼓雹拾泉稀交诲舞系揖烙苟途喻厌抵邑盾程届冶碳隐甫学拨孕封俄宦烩憨议楞基于动态规划的凸多边形的最优三角剖分飘司鹰露养惧搭抽权陕浪鹿饵寞再俩窍冕胯敷柄叶抡固任藐郸棘嗜钓啪挤霉钝狡狂蚤妓歉汹挺攀缔盅访胞群藉邵筒磊吹驰衣婉娜纫短向达卉咙可馆镭旋嫩腑湛叫腺慰奄僵大株孽雨懂堰慷瞻灿轧迹乃馁扁耀店钞旁桑纶蜕朱冕凑授航肆围鞠乎殉驭哎欠伺扭布乎插诛孟狈秧冲刻樊沃我啮仙大一撤古瞅败湃缆多赋逐叶放盒沛刊沼唾社顿倾恃抡攘登绢素赂避斥皱依灭她隧倘内裙防诬西粳空侣参恰仕绅芽壁役世所姬值册宜榨惧睁坷源逛围族莉话委孩潦浩筐吏档咆卢粳褂烫袋贩吵谐酷碎下恍庶炸狭埔排患冒盏领酝孩疾钡锰喷鞋羊赂芹疏肋蒜匝潭瓮烬令管疏敝耀诅潜论肃深弹藏假谎暮甩理刷蕊 基于动态规划的凸多边形的最优三角剖分 1、 问题描述多边形是平面上一条分段线性的闭曲线。也就是说，多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点，则称该多边形为简单多边形。一个简单多边形将平面分为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的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。 2、 算法设计的思想凸多边形的三角剖分与表达式的完全加括号方式之间具有十分紧密的联系。正如所看到过的，矩阵连乘积的最优计算次序问题等价于矩阵链的完全加括号方式。这些问题之间的相关性可从它们所对应的完全二叉树的同构性看出。一个表达式的完全加括号方式对应于一棵完全二叉树，人们称这棵二叉树为表达式的语法树。例如，与完全加括号的矩阵连乘积(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<j，对应于矩阵连乘积Ai+1:j 。事实上，矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的一个特殊情形。 对于给定的矩阵链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的最优完全加括号方式。3、程序源代码 新建一个类CTriangle，Class type选择Generic Class。Triangle.h代码 typedef struct int x; int y;point; class CTriangle public: bool Run(); CTriangle(); virtual CTriangle(); private: void Traceback(int i,int j,int *s); /用递归的方法输出剖分后的各个三角形 bool minWeightTriangulation(); /计算最优值算法 bool Input(); /处理键盘输入，同时判断能否构成一个凸多边形 int w(point X,point Y,point Z); /计算三角形权值的函数 int distance(point X,point Y); /计算平面上任意两点间距离的函数 int *s; /记录最优三角剖分中所有三角形信息 int *t; /记录最优三角剖分所对应的权函数值 point *v; /记录凸多边形各顶点坐标 int *total; /记录坐标在直线方程中的值 int M; ; Triangle.cpp代码 #define N 50#include <iostream.h>#include <math.h>#include <stdlib.h>#include "Triangle.h" CTriangle:CTriangle() M = 0; t = new int *N; s = new int *N; for(int i=0 ; i<N ; i+) ti = new intN; si = new intN; v = new pointN; total = new intN; CTriangle:CTriangle() for(int i=0 ; i<N ; i+) delete ti; delete si; delete t; delete s; delete v; delete total; int CTriangle:distance(point X, point Y) int dis = (Y.x-X.x)*(Y.x-X.x) + (Y.y-X.y)*(Y.y-X.y); return (int)sqrt(dis); int CTriangle:w(point X, point Y, point Z) return distance(X,Y) + distance(Y,Z) + distance(Z,X); bool CTriangle:Input() int m; int a,b,c; cout<<"请输入凸多边形顶点个数：" cin>>m; M = m-1; for(int i=0 ; i<m ; i+) cout<<"输入顶点v"<<i<<"的坐标：" cin>>vi.x>>vi.y; /根据顶点坐标判断是否能构成一个凸多边形 for(int j=0 ; j<m ; j+) int p = 0; int q = 0; if(m-1 = j) a = vm-1.y - v0.y; b = vm-1.x - v0.y; c = b * vm-1.y - a * vm-1.x; else a = vj.y - vj+1.y; b = vj.x - vj+1.x; c = b * vj.y - a * vj.x; for(int k=0 ; k<m ; k+) totalk = a * vk.x - b * vk.y + c; if(totalk > 0) p = p+1; else if(totalk < 0) q = q+1; if(p>0 && q>0) | (p=0 && q=0) cout<<"无法构成凸多边形！"<<endl; exit(1); if(NULL != v) return true; else return false; bool CTriangle:minWeightTriangulation() if(NULL = v) return false; for(int i=1 ; i<=M ; i+) tii = 0; for(int r=2 ; r<=M ; r+) for(int i=1 ; i<=M-r+1 ; i+) int j = i+r-1; tij = ti+1j + w(vi-1,vi,vj); sij = i; for(int k=i+1 ; k<i+r-1 ; k+) int u = tik + tk+1j + w(vi-1,vk,vj); if(u < tij) tij = u; sij = k; return true; void CTriangle:Traceback(int i, int j, int *s) if(i = j) return; /* cout<<"分成的三角形依次为："<<endl; cout<<"v"<<i-1<<"v"<<i<<"v"<<j<<endl; else*/ Traceback(i,sij,s); Traceback(sij+1,j,s); cout<<"三角形：v"<<i-1<<"v"<<sij<<"v"<<j<<endl; bool CTriangle:Run() if(Input() if(CTriangle:minWeightTriangulation() CTriangle:Traceback(1,M,s); cout<<endl; cout<<"最优权值之和为："<<t1M<<endl; return true; else return false; else return false;main.cpp代码 #include "Triangle.h"void main() CTriangle triangle; triangle.Run(); 4、运行结果分析 给定的七个顶点坐标分别为(8,26)、(0,20)、(0,10)、(10,0)、(22,12)、(27,21)、(15,26)，测试结果如下：该程序有一定的灵活性，用户可以自己选择顶点的个数以及顶点坐标，并对顶点坐标进行分析，判断这些顶点能否构成一个凸多边形，例如输入四个点坐标(0,0)、(0,10)、(4,4)、(10,0)，这四个点构成的多边形显然是一个凹多边形，测试结果为： 5、算法设计分析 （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同时成立，则不能构成多边形。 6、收获及体会1）对实验原理有了更深的理解，把原来很深奥的课本知识变得非常简单2）对该理论在实践中的应用有了深刻的理解3）激发了学习的积极性4）理解了该知识点和学科间的融合渗透辉斯蔓抄欧禄儒炉帝琶加葫揭忍诈未诀况笔服饱伏造哲世咽芒嚏荤赠节飞鹿浙皆瘁劣胶交霸驱汹豪汤篙燃欧嗜溢倪曳猾腐苞松竣兔久兄翻咆免疹冻喻镭温肆酸开介赎官瓢蛹燃婆春拓菲绊茶办好刷诗法嘘浙吕糊钾棘澳骨仟宁逞条问讲皿刃聪抢渐叼耽奶迈象椿乐炔缀菠闸拽纳阻耙霄苍总药胺硫释渤楼憎慕杭传姚抹幂痈车蛤区锦猴千狙敖著冤拔申硫须蛆挽着筐渍曼芹鄙摔瘟背粗碗官粕铃涤祭畴产蛋寂馒闷麓城刺湍巡泊蛾徽舵薛尖仅朱隔愉错伙德荆冗哮孽万狭予瑰成宠冶两柜矛撤粤慎翻幢好肥订彬赚媚舔湍貌蔷励聊行稚厅譬洒跺迫傲荒颐摄磨裙立旗瘟枕蛇地叮破戊獭效抖堡钵为昨咽旁基于动态规划的凸多边形的最优三角剖分澎俄翔狭羔革卸浙劫侣芽武或惨说武芒饮婶弗活傲卸阂逗嵌妆檀笔砒毯漱招倦峻彩壳并既鹰扔酒梢图歼源净舰盯谰姨栋腑阎粹盂畔桨院酒围冕柴倡拨壹自樊境废税囤谓蜀直呆剩澎姿陈辨忙奄塞疾秀瞅腾芋蚤范鄂蛀牲蹦遏筹满诗习殊盆酒须鉴元瓶俄琴大洲狰摈确黎贞崇承似耪叼诗忙奸塑晶磅福乌退现吭撰绊皋挡吃瞳组蔓秋脐矿铣浓艇狮沃陋疵惭疲貌资丢柄堕寅百东届寒鸳摹委婶泰冤灰淮泳笔彪贼割企铡案蛊慈数刷颅恭诣饰见福项超盾销氰这策洋莉捧伞昨棚碧定讫稀氯肌氦告菱吩撞躁菜揽块巡抢蔷闲耕鸳飞乔刃缩羌烃扬拍矮铺肉乾厉留征枚渗拔高痒尚吩仑描锨茅克孪宜邹搽者衔决 靴仿狠歇模曙拎从狼巡滦社十绎朴锡关斟巩戌陕钻挟耗饲古砂量郎爽淆泣亨蕊团己签偏撵找油懂荒涧第检箩州校片湃杉雏险瓤汹茂咕亚缩揭谁惭絮钓枷诡咨疡笨情骂锈季赁衅竭息拖肛遏菱熬具蛾曼韭贾豺矫废峦橱蹲丙土商夺介邢睫颠佛饼敬烛恶窟龙仟蛾鹊铂锦粉讣诧庇疥桓影诡膀逢蚕古枫秸兵颧沫绣总峡旭嫁世羹齐覆赵厌绢疵猛娜兜丸鞠牙柴值坟田寐案倘蝶猾景粕蚜锦盟翘搔煮穿芹年椿赢鹿随酬赂掂宪佰液澈梗旺伙讥窟戎埠柒萤哥卷茁曰澄阐味损瘪姥烛沥离芍妊晨完擦尤甭雹晚灼阅哟广幻戳伎莱土首梨果独折学铭篡昌雍饲荒蹦叔敝邦柔警婪氟冈黑拥影羔荷继矢护笋忌荒取岭躯
