凸包算法設(shè)計(jì)

凸包問題算法設(shè)計(jì)制作者：地信******2014.05.10凸包概念1.點(diǎn)集Q的凸包（convexhull）是指一個(gè)最小凸多邊形，滿足Q中的點(diǎn)或者在多邊形邊上或者在其內(nèi)。右圖中由紅色線段表示的多邊形就是點(diǎn)集Q={p0,p1,...p12}的凸包。2.一組平面上的點(diǎn)，求一個(gè)包含所有點(diǎn)的最小的凸多邊形，這就是凸包問題了。這可以形象地想成這樣：在地上放置一些不可移動(dòng)的木樁，用一根繩子把他們盡量緊地圈起來(lái)，并且為凸邊形，這就是凸包了。算法：增量式算法,包裹法（Jarvis步進(jìn)法）,葛立恒（Graham）掃描法,單調(diào)鏈,分治法,快包法（Akl-Toussaint啟發(fā)式）等。1.1分治法的概念

所謂分治法就是把問題劃分成多個(gè)子問題來(lái)進(jìn)行處理。這些子問題，在結(jié)構(gòu)上與原來(lái)的問題一樣，但在規(guī)模上比原來(lái)的小。如果得到的子問題相對(duì)來(lái)說(shuō)還大，可以反復(fù)地使用分治策略，把這些子問題再劃分成更小的、結(jié)構(gòu)相同的子問題。這樣就可以使用遞歸的方法，分別求解這些子問題，把這些子問題的解結(jié)合起來(lái)，從而獲得原來(lái)問題的解。化整為零，各個(gè)擊破。1.2問題分析圖（PFD圖）

原問題的規(guī)模是n子問題1的規(guī)模小于n子問題2的規(guī)模小于n子問題1的解子問題2的解原問題的解1.3過程描述一般來(lái)說(shuō)，分治法的求解過程由以下三個(gè)階段組成：（1）劃分：把規(guī)模為n的原問題劃分為k個(gè)規(guī)模較小且

規(guī)模大致相同的子問題。（2）求解子問題：使用遞歸方法分別求解子問題。（3）合并：把各子問題的解合并起來(lái)，合并的代價(jià)因情況而異，分治算法的有效性很大程度上依賴于合并的實(shí)現(xiàn)。1.4凸包問題的分治思想：第一步：把給定點(diǎn)集中的點(diǎn)在橫坐標(biāo)方向上按照大小排序。

如下圖所示，p1和pn必定是凸多邊形的兩個(gè)頂點(diǎn)。第二步：在上凸包點(diǎn)集合s1中找到一個(gè)距離直線最遠(yuǎn)點(diǎn)pmax，如下

圖所示。顯然直線段p1pmax與直線段pmaxpn把點(diǎn)集s1分成了三個(gè)集合。由凸包的性質(zhì)可知p1，pmax，pn三點(diǎn)圍成的三角形中的點(diǎn)不可能作為凸包的頂點(diǎn)，所以只需考慮直線p1pmax左邊的點(diǎn)s11以及直線pmaxpn右邊的點(diǎn)s12。第三步：遞歸求解得到凸多邊形的邊。第四步：合并這些邊即得所求凸包。1.5凸包問題的分治算法算法：convex_divide()findtwo(MIN_Y,MAX_Y);//查找Y值最小和最大的兩個(gè)點(diǎn)，作為初始凸包頂點(diǎn)initialmain(leftList,rightList,side,MIN_Y,MAX_Y);//由這兩點(diǎn)確定的線段side，將平面的點(diǎn)分成相互獨(dú)立的兩部分，左邊區(qū)域內(nèi)的散點(diǎn)放在leftList中，右邊的散點(diǎn)放在rightList中dealwith(side,leftList,resultList);dealwith(side,rightList,resultList);write(resultList);//輸出凸包的頂點(diǎn)dealwith(VARside,list，resultList)//處理某一條邊side及其所屬的離散點(diǎn)集list，并把找到的凸包頂點(diǎn)放到凸包頂點(diǎn)集resultList中ifnotisEmpty(list)then{node:=LongNode(side,list);//找出list中離這條邊最遠(yuǎn)的點(diǎn)，并把它從List中刪除insert(resultList,side,node);//該點(diǎn)肯定是凸包的頂點(diǎn)，把它放到凸包頂點(diǎn)集的相應(yīng)位置，該位置就在該邊起點(diǎn)的后面Triangle:=createTriangle(side,node);//該點(diǎn)和原先的邊生成一個(gè)三角形while(notisEmpty(list))do{Node:=GetNextNode(list);//從list中取出一個(gè)點(diǎn)，進(jìn)行歸邊處理IfinTriangle(node,Triangle)//如果點(diǎn)在三角形內(nèi)，則拋棄then

delete(node)else//點(diǎn)在三角形外，則判斷其所屬的邊

if(attachSide(node,Lside,Rside)=left)

then

insert(LeftList,node);//該點(diǎn)屬于Lside邊放入leftList散點(diǎn)集中

else

insert(RightList,node);//處理屬于Rside邊，放入rightList集中}//list中所有點(diǎn)處理完畢dealwith(Lside,Leftlist,resultList);//處理屬于Lside邊及其所屬的點(diǎn)dealwith(rside,rightlist,resultList);//處理屬于Rside邊及其所屬的點(diǎn)}2.1凸包問題蠻力算法蠻力法求解凸包問題的基本思想：

對(duì)于一個(gè)由n個(gè)點(diǎn)構(gòu)成的集合S中的兩個(gè)點(diǎn)Pi和Pj，當(dāng)且僅當(dāng)該集合中的其他點(diǎn)都位于穿過這兩點(diǎn)的直線的同一邊時(shí)（假定不存在三點(diǎn)同線的情況），他們的連線是該集合凸包邊界的一部分。對(duì)每一對(duì)頂點(diǎn)都檢驗(yàn)一遍后，滿足條件的線段構(gòu)成了該凸包的邊界。2.2具體描述

在平面上，穿過兩個(gè)點(diǎn)(x1,y1)和(x2,y2)的直線是由下面的方程定義的：

ax+by=c(其中,a=y2-y1,b=x1-x2,c=x1y2-y1x2)（由(y-y?)/(y?-y?)=(x-x?)/(x?-x?)（兩點(diǎn)式）

交叉相乘得：(y-y?)(x?-x?)=(y?-y?)(x-x?)

去括號(hào)整理可得：（y?-y?)x+(x?-x?)y-x?y?+x?y?=0

∴a=y?-y?b=x?-x?c=x?y?-x?y?）

這樣一條直線把平面分成兩個(gè)半平面：其中一個(gè)半平面中的點(diǎn)都滿足ax+by＞c，另一個(gè)半平面中的點(diǎn)都滿足ax+by＜c.

因此，為了檢驗(yàn)這些點(diǎn)是否位于這條直線的同一邊，可以簡(jiǎn)單地把每個(gè)點(diǎn)代入方程ax+by=c，檢驗(yàn)這些表達(dá)式的符號(hào)是否相同。2.3算法設(shè)計(jì)算法：Voidconvex_hull(){inti,j,k,sign=0;//sign用于記錄滿足條件的點(diǎn)doublea=0,b=0,c=0;for(i=0;i<MAXNUM;++i)//MAXNUM

for(j=i+1;j<MAXNUM;++j)

{a=my_point[j].y–my_point[i].y;b=my_point[j].x–my_point[i].x;c=(my_point[i].x*my_point[j].y)–(my_point[i].y*my_point[j].x)sign=0;for(k=0;k<MAX_NUM;k++)//區(qū)域內(nèi)的每個(gè)點(diǎn)都作檢查{

if((k==j)||(k==i))

continue;//如果是i點(diǎn)或j點(diǎn)，應(yīng)該排除掉

if((a*my_point[k].x+b*mypoint[k].y)==c)continue;//如果在線上也不行，因?yàn)閕,j已經(jīng)是兩個(gè)相鄰的點(diǎn)

if((a*my_point[k].x+b*mypoint[k].y)>c)++sign;//當(dāng)代入結(jié)果大于0時(shí)，記sign為正

if((a*my_point[k].x+b*mypoint[k].y)<c)

--sign;//當(dāng)代入結(jié)果小于0時(shí)，記sign為負(fù)}//如果所有的點(diǎn)都檢查