凸包算法設(shè)計

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

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

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

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

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

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

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

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

then

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

else

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

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

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

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

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

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

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

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

因此，為了檢驗這些點是否位于這條直線的同一邊，可以簡單地把每個點代入方程ax+by=c，檢驗這些表達式的符號是否相同。2.3算法設(shè)計算法：Voidconvex_hull(){inti,j,k,sign=0;//sign用于記錄滿足條件的點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)的每個點都作檢查{

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

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

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

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

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

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