凸多邊形最優(yōu)三角剖分

凸多邊形最優(yōu)三角剖分一、 問題描述多邊形是平面上一條分段線性的閉曲線。也就是說，多邊形是由一系列首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連接點(diǎn)稱為多邊形的頂點(diǎn)。若多邊形的邊之間除了連接頂點(diǎn)外沒有別的公共點(diǎn)，則稱該多邊形為簡(jiǎn)單多邊形。一個(gè)簡(jiǎn)單多邊形將平面分為3個(gè)部分：被包圍在多邊形內(nèi)的所有點(diǎn)構(gòu)成了多邊形的內(nèi)部；多邊形本身構(gòu)成多邊形的邊界；而平面上其余的點(diǎn)構(gòu)成了多邊形的外部。當(dāng)一個(gè)簡(jiǎn)單多邊形及其內(nèi)部構(gòu)成一個(gè)閉凸集時(shí)，稱該簡(jiǎn)單多邊形為凸多邊形。也就是說凸多邊形邊界上或內(nèi)部的任意兩點(diǎn)所連成的直線段上所有的點(diǎn)均在該凸多邊形的內(nèi)部或邊界上。通常，用多邊形頂點(diǎn)的逆時(shí)針序列來表示一個(gè)凸多邊形，即P=｛v0,v1，…，vn-1｝表示具有n條邊v0v1，v1v2，-，vn-1vn的一個(gè)凸多邊形，其中，約定v0=vn。若v與Vj是多邊形上不相鄰的兩個(gè)頂點(diǎn)，則線段VjVj稱為多邊形的一條弦。弦將多邊形分割成凸的兩個(gè)子多邊形｛Vi,vi+1，…，Vj｝和｛Vj,Vj+1，…，Vj｝。多邊形的三角剖分是一個(gè)將多邊形分割成互不相交的三角形的弦的集合T。圖1是一個(gè)凸多邊形的兩個(gè)不同的三角剖分。圖1一個(gè)凸多邊形的2個(gè)不同的三角剖分在凸多邊形P的一個(gè)三角剖分T中，各弦互不相交，且弦數(shù)已達(dá)到最大，即P的任一不在T中的弦必與T中某一弦相交。在一個(gè)有n個(gè)頂點(diǎn)的凸多邊形的三角剖分中，恰好有n-3條弦和n-2個(gè)三角形。凸多邊形最優(yōu)三角剖分的問題是：給定一個(gè)凸多邊形P=｛v0,v1，…，vn-1｝以及定義在由多邊形的邊和弦組成的三角形上的權(quán)函數(shù)3。要求確定該凸多邊形的一個(gè)三角剖分，使得該三角剖分對(duì)應(yīng)的權(quán)即剖分中諸三角形上的權(quán)之和為最小。可以定義三角形上各種各樣的權(quán)函數(shù)3。例如：定義w(vivvk)=|viv|+|vivk|+|vkv|，其中，MV是點(diǎn)v到v的歐氏距離。相應(yīng)于此權(quán)函數(shù)的最優(yōu)三角剖分即為最小弦長三角剖分。二、 算法思路凸多邊形的三角剖分與表達(dá)式的完全加括號(hào)方式之間具有十分緊密的聯(lián)系。正如所看到過的，矩陣連乘積的最優(yōu)計(jì)算次序問題等價(jià)于矩陣鏈的完全加括號(hào)方式。這些問題之間的相關(guān)性可從它們所對(duì)應(yīng)的完全二叉樹的同構(gòu)性看出。一個(gè)表達(dá)式的完全加括號(hào)方式對(duì)應(yīng)于一棵完全二叉樹，人們稱這棵二叉樹為表達(dá)式的語法樹。例如，與完全加括號(hào)的矩陣連乘積(內(nèi)(人2鈿)(人4代人6)))相對(duì)應(yīng)的語法樹如圖2(a)所示。<*) (b)圖2表達(dá)式語法樹與三角剖分的對(duì)應(yīng)語法樹中每一個(gè)葉子表示表達(dá)式中一個(gè)原子。在語法樹中，若一結(jié)點(diǎn)有一個(gè)表示表達(dá)式左子樹，以及一個(gè)表示表達(dá)式Er的右子樹，則以該結(jié)點(diǎn)為根的子樹表示表達(dá)式仁店』。因此，有n個(gè)原子的完全加括號(hào)表達(dá)式對(duì)應(yīng)于惟一的一棵有n個(gè)葉結(jié)點(diǎn)的語法樹，反之亦然。凸多邊形｛v0,v1，…，vn-1｝的三角剖分也可以用語法樹來表示。例如，圖1(a)中凸多邊形的三角剖分可用圖2(b)所示的語法樹來表示。該語法樹的根結(jié)點(diǎn)為邊v0v6，三角剖分中的弦組成其余的內(nèi)部結(jié)點(diǎn)。多邊形中除v0v6邊外的每一條邊是語法樹的一個(gè)葉結(jié)點(diǎn)。樹根v0v6是三角形v0v3v6的一條邊，該三角形將原多邊形分為3個(gè)部分：三角形v0v3v6，凸多邊形｛v0,v1，…，V3｝和凸多邊形｛v3,v4，…，v6｝。三角形v0v3v6的另外兩條邊，即弦v3v6和v0v3為根的兩個(gè)兒子。以它們?yōu)楦淖訕浞謩e表示凸多邊形｛v0,v1，…，V3｝和凸多邊形｛v3,v4，…，V6｝的三角剖分。在一般情況下，一個(gè)凸n邊形的三角剖分對(duì)應(yīng)于一棵有n-1個(gè)葉子的語法樹。反之，也可根據(jù)一棵有n-1個(gè)葉子的語法樹產(chǎn)生相應(yīng)的一個(gè)凸n邊形的三角剖分。也就是說，凸n邊形的三角剖分與n-1個(gè)葉子的語法樹之間存在一一對(duì)應(yīng)關(guān)系。由于n個(gè)矩陣的完全加括號(hào)乘積與n個(gè)葉子的語法樹之間存在一一對(duì)應(yīng)關(guān)系，因此n個(gè)矩陣的完全加括號(hào)乘積也與凸(n+1)邊形的三角剖分之間存在一一對(duì)應(yīng)關(guān)系。圖2的(a)和(b)表示出了這種對(duì)應(yīng)關(guān)系，這時(shí)n=6。矩陣連乘積A1A2..A6中的每個(gè)矩陣入對(duì)應(yīng)于凸(n+1)邊形中的一條邊％‘。三角剖分中的一條弦《馬，i<j，對(duì)應(yīng)于矩陣連乘積A[i+1:j]。事實(shí)上，矩陣連乘積的最優(yōu)計(jì)算次序問題是凸多邊形最優(yōu)三角剖分問題的一個(gè)特殊情形。對(duì)于給定的矩陣鏈A1A2..An，定義一個(gè)與之相應(yīng)的凸(n+1)邊形P=｛v0,v1，…，vn｝，使得矩陣A與凸多邊形的邊vi-1v一一對(duì)應(yīng)。若矩陣A的維數(shù)為pi-1xpi，i=1,2，_，n，則定義三角形vvvk上的權(quán)函數(shù)值為：w(vivjvk)=pipjpko依此權(quán)函數(shù)的定義，凸多邊形P的最優(yōu)三角剖分所對(duì)應(yīng)的語法樹給出矩陣鏈A1A2..An的最優(yōu)完全加括號(hào)方式。三、 實(shí)驗(yàn)源程序

新建一個(gè)類CTriangle,Classtype選擇GenericClass。Triangle.h代碼typedefstruct{intx;inty;}point;classCTriangle{public:boolRun();CTriangle();virtual~CTriangle();private:〃用遞歸的方法輸出剖分后的各個(gè)三角形voidTraceback(inti,intj,int**s);〃計(jì)算最優(yōu)值算法boolminWeightTriangulation();〃處理鍵盤輸入，同時(shí)判斷能否構(gòu)成一個(gè)凸多邊形boolInput();〃計(jì)算三角形權(quán)值的函數(shù)intw(pointX,pointY,pointZ);//計(jì)算平面上任意兩點(diǎn)間距離的函數(shù)〃記錄最優(yōu)三角剖分中所有三角形信息int**s;〃記錄最優(yōu)三角剖分中所有三角形信息int**s;〃記錄最優(yōu)三角剖分所對(duì)應(yīng)的權(quán)函數(shù)值int**t;〃記錄凸多邊形各頂點(diǎn)坐標(biāo)point*v;//記錄坐標(biāo)在直線方程中的值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<<"請(qǐng)輸入凸多邊形頂點(diǎn)個(gè)數(shù)："；cin?m;M=m-1;for(inti=0;i<m;i++){cout?'輸入頂點(diǎn)v"<<i<<"的坐標(biāo)："；cin?v[i].x?v[i].y;}〃根據(jù)頂點(diǎn)坐標(biāo)判斷是否能構(gòu)成一個(gè)凸多邊形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<<"無法構(gòu)成凸多邊形！"<<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()){四、 測(cè)試結(jié)果

{CTriangle::Traceback(1,M,s);cout<<endl;cout<<"最優(yōu)權(quán)值之和為："<<t[1][M]?endl;returntrue;}elsereturnfalse;}elsereturnfalse;}main.cpp代碼#include"Triangle.h"voidmain(){CTriangletriangle;triangle.Run();}給定的七個(gè)頂點(diǎn)坐標(biāo)分別為(8,26)、(0,20)、(0,10)、(10,0)、(22,12)、(27,21)、(15,26),測(cè)試結(jié)果如下:該程序有一定的靈活性，用戶可以自己選擇頂點(diǎn)的個(gè)數(shù)以及頂點(diǎn)坐標(biāo)，并對(duì)頂點(diǎn)坐標(biāo)進(jìn)行分析，判斷這些頂點(diǎn)能否構(gòu)成一個(gè)凸多邊形，例如輸入四個(gè)點(diǎn)坐標(biāo)(0,0)、(0,10)、(4,4)、(10,0)，這四個(gè)點(diǎn)構(gòu)成的多邊形顯然是一個(gè)凹多邊形，測(cè)試結(jié)果為：五、 總結(jié)凸多邊形的最優(yōu)三角剖分本來是一個(gè)幾何問題，但通過分析，它本質(zhì)上于矩陣連乘積的最優(yōu)計(jì)算次序問題極為相似，從而可以將問題進(jìn)行轉(zhuǎn)化，用動(dòng)態(tài)規(guī)劃算法有效的解決這個(gè)問題。本實(shí)驗(yàn)的七個(gè)頂點(diǎn)坐標(biāo)數(shù)據(jù)是給定的，可以構(gòu)成一個(gè)凸多邊形，但對(duì)于未知的數(shù)據(jù)，事先并不知道所給數(shù)據(jù)能否構(gòu)成一個(gè)凸多邊形。所以我在這里多做了一點(diǎn)工作，就是如何判斷所給的頂點(diǎn)能否構(gòu)成凸多邊形。解決思路是：用兩點(diǎn)式推導(dǎo)直線一般方程，設(shè)已知的兩點(diǎn)坐標(biāo)分別為(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。對(duì)于任一條直線ax+by+c=0(a,b不同時(shí)為0),則其余非構(gòu)成直線的點(diǎn)的坐標(biāo)