凸包生成算法實驗報告

1、精選優(yōu)質文檔-傾情為你奉上實驗報告班 級： 學生姓名： 學 號： 日 期: 2014年5月11日 判斷點線關系及計算多邊形內(nèi)角一、點與線的關系（1）定義：平面上的三點P1(x1,y1),P2(x2,y2),P3(x3,y3)的面積量：|x1 x2 x3|S(P1,P2,P3) = |y1 y2 y3| = (x1-x3)*(y2-y3) - (y1-y3)*(x2-x3)|1 1 1 |當P1P2P3逆時針時S為正的，當P1P2P3順時針時S為負的。令矢量的起點為A，終點為B，判斷的點為C，如果S（A，B，C）為正數(shù)，則C在矢量AB的左側；如果S（A，B，C）為負數(shù)，則C在矢量AB的右側；如果

2、S（A，B，C）為0，則C在直線AB上。（2）算法 int MyMath:IsRightInLine(MyPoint p1, MyPoint p2, MyPoint p3) int s;s = (p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x);if (s>0)return 1; /點在直線左側else if (s<0)return 2;/點在直線右側 elsereturn 0;/點在直線上 二、計算多邊形內(nèi)角（1） 算法過程第一步：輸入一系列的離散點；第二步：找x坐標值最小的點p0，這樣能確定由此點構成的多邊形的角是凸的；第三步：定義與

3、p0點相鄰的前后兩個點p1，p2，若超出數(shù)組邊界，則用首點或尾點取代；第四步：計算p2與向量p1p0的位置關系，若p2在向量p1p0的左邊，則多邊形呈逆時針方向；若p2在向量p1p0的右邊，則多邊形呈順時針方向。第五步：計算多邊形的各個內(nèi)角，利用兩個向量的夾角公式計算。由于多邊形有凹凸性，所以算角時要分情況。找規(guī)律可知，若多邊形是逆時針走向，那么，若三個相鄰的點構成凸角，三點的走向始終是逆時針走向，否則，是順時針走向，故可根據(jù)此來確定角度。（2） 算法實現(xiàn)1、 定義點類class MyPoint public:MyPoint();virtual MyPoint();public:int id;

4、int x,y,z;2、 定義數(shù)學計算類class MyMath public:MyMath();virtual MyMath();public:static float CalcuAngle(MyPoint p1,MyPoint p2,MyPoint p3,int flag);/算角度static int IsRightInLine(MyPoint p1,MyPoint p2,MyPoint p3);/判斷點與直線位置關系protected:staticfloat VectorAngel(MyPoint p1,MyPoint p2,MyPoint p3);/計算向量角staticfloat

5、CalCuMatrix(MyPoint p1,MyPoint p2,MyPoint p3);詳細代碼：/點與直線的關系int MyMath:IsRightInLine(MyPoint p1, MyPoint p2, MyPoint p3) int s;s = (p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x);if (s>0)return 1; /點在直線左側else if (s<0)return 2;/點在直線右側 elsereturn 0;/點在直線上 /計算角度float MyMath:CalcuAngle(MyPoint p1,

6、MyPoint p2, MyPoint p3,int flag) /判斷正逆方向float d = CalCuMatrix(p1,p2,p3);float angle = VectorAngel(p1,p2,p3);if (flag=1)if (d>0)/逆時針，凸多邊形(在數(shù)學坐標系中正確，程序中相反)return (180.0-angle);else /順時針，凹多邊形return (180.0+angle);if (flag=2)if (d>0)/逆時針，凸多邊形return (180.0+angle);else /順時針，凹多邊形return (180.0-angle);/

7、求矩陣，用于判斷走向float MyMath:CalCuMatrix(MyPoint p1,MyPoint p2,MyPoint p3) return (p1.x*p2.y+p1.y*p3.x+p2.x*p3.y)-(p2.y*p3.x+p3.y*p1.x+p1.y*p2.x);/求向量夾角float MyMath:VectorAngel(MyPoint p1, MyPoint p2, MyPoint p3) int dx1 = p2.x-p1.x; int dy1 = p2.y-p1.y; int dx2 = p3.x-p2.x; int dy2 = p3.y-p2.y; float a =

8、 (dx1*dx2+dy1*dy2)/(sqrt(dx1*dx1+dy1*dy1)*sqrt(dx2*dx2+dy2*dy2); return (180*acos(a)/3.1415;3、 定義多邊形類class MyPolygon public:MyPolygon();virtual MyPolygon();public:CArray<MyPoint,MyPoint> dingDianArray;/多邊形頂點CArray<int,int> trangleArray; /角度 int flag;/判斷順逆方向,逆為2，順為1，初始為0public:void AddPoi

9、nt(MyPoint p);/加點void DrawPolygon(CDC * pDC);/畫多邊形 bool Cacul();/計算夾角；詳細代碼：/畫多邊形void MyPolygon:DrawPolygon(CDC * pDC)CPen *pen = new CPen(0, 1, RGB(255,0,0);CPen* oldPen = pDC->SelectObject(pen); int ix,iy;int dianCount=dingDianArray.GetSize(); /畫點for (int i=0;i<dingDianArray.GetSize();i+) ix

10、= dingDianArrayi.x;iy = dingDianArrayi.y;pDC->Ellipse(ix-3,iy-3,ix+3,iy+3); /畫邊if (dianCount>=3)pDC->MoveTo(dingDianArray0.x,dingDianArray0.y);for(int i=1;i<dianCount;i+)pDC->LineTo(dingDianArrayi.x,dingDianArrayi.y);pDC->LineTo(dingDianArray0.x,dingDianArray0.y); /畫角度if (trangleAr

11、ray.GetSize()>0)for (int i=0;i<trangleArray.GetSize();i+)CString s;s.Format("%d",trangleArrayi);pDC->TextOut(dingDianArrayi.x,dingDianArrayi.y,s); pDC->SelectObject(oldPen); /加點void MyPolygon:AddPoint(MyPoint p) dingDianArray.Add(p);/計算方向和角度bool MyPolygon:Cacul() if (dingDianAr

12、ray.GetSize()<3) flag = 0; return false; else /找x值最小的點 int index=0; MyPoint p = dingDianArray0; for (int i=1;i<dingDianArray.GetSize();i+) MyPoint pi = dingDianArrayi; if (p.x>pi.x) index= i; p = pi; /定義與當前點相鄰的兩點 int i_1 = index -1; int i1 = index+1; if (i_1<0) i_1 = dingDianArray.GetSiz

13、e ()-1; if (i1>dingDianArray.GetSize()-1) i1=0; MyPoint pi_1 = dingDianArrayi_1; MyPoint pi1 = dingDianArrayi1; /判斷點線位置關系，確定多邊形的走向 int isRight = MyMath:IsRightInLine(pi_1,p,pi1); if (isRight=1) flag = 1; else if (isRight=2) flag = 2; else flag=0; /計算多邊形內(nèi)角 trangleArray.RemoveAll(); for( i=0;i<d

14、ingDianArray.GetSize();i+) i_1 = i -1; i1 = i+1; if (i_1<0) i_1 = dingDianArray.GetSize ()-1; if (i1>dingDianArray.GetSize()-1) i1=0; p = dingDianArrayi; pi_1 = dingDianArrayi_1; pi1 = dingDianArrayi1; float angle = MyMath:CalcuAngle(pi_1,p,pi1,flag); trangleArray.Add (int)angle); return true;

15、 return false;（3） 算法結果凸包生成算法一、凸包定義通俗的說就是：一組平面上的點，求一個包含所有點的最小凸多邊形，這個最小凸多邊形就是凸包。二、Graham算法思想概要：Graham算法的主要思想就是，最終形成的凸包，即包圍所有點的凸多邊形，假定多邊形是按逆時針方向生成的，那么多邊形內(nèi)部包圍的所有點與多邊形每個有向邊的關系都是：點在有向邊的左邊。依照此思想，只要找到一個出發(fā)點，然后依此出發(fā)點按逆時針方向構建多邊形，并保證每加入一條有向邊時，都要滿足其余點都在該邊的左邊。具體算法過程：（1）輸入：點集S=P（2）尋找基點P0：在所有點中找到y(tǒng)坐標最小的點，若找到多個，則選取其中X

16、坐標最大的點作為基點，若只找到一個，則直接以這個點作為基點。（3）排序：以基點為起點，以其余點為終點構成一個向量<P0,PK>，逐個計算每個向量與x軸正方向的夾角，并按夾角有小到大進行排序，得到一個排序的點S1=p0,p1,p2,p3p(N-1)；對于夾角相同的點，剔除掉離基點近的點，只保留離基點最遠的那個點。注意：由于計算角度復雜且耗時，在這里采用另外一種方式處理，根據(jù)上面的點線關系，從基點p0出發(fā)，依次遍歷其它點，設為pk，p0和pk就構成一條有向向量，依次判斷其它點（如pm）在向量的哪個方向，若在線段右邊，則用其它點代替pk，構成一個新向量p0pm,繼續(xù)判斷剩余的點，這樣一趟

17、下來，就能找到最右邊的點；依此道理判斷其他點。如圖：從向量p0p3（p3是任意選的，最終要將除p0外的所有點選到即可）開始，p1在向量p0p3左邊，不變；p2在p0p3左邊，向量不變；p4在p0p3右邊，這時要將比較的向量變?yōu)閜0p4；繼續(xù)遍歷p5，p5在p0p4右邊，向量變?yōu)閜0p5；繼續(xù)遍歷p6,p6在向量p0p5右邊，向量變?yōu)閜0p6；遍歷p7，p7在向量p0p6右邊，向量變?yōu)閜0p7，這一趟下來就將p7這一個最右邊的點找到了。同樣的方法排序其他點，最后向量按與x軸正方向的順序就是p7,p6,p5,p4,p3,p2,p1,依次遞增。（4）構造凸包：第一步：首先將基點p0入棧，p1和p2也

18、依次入棧；第二步：取棧頂?shù)那皟蓚€點構成向量，即向量<p(k-1),pk>；第三步：判斷點p(k+1)是否在向量的左邊；第四步： 情況1:若在向量的左邊，則將點p(k+1)入棧，重復第二步； 情況2：若在向量的右邊，將點pk出棧，繼續(xù)取下一個點，重復步驟二。第五步：最后棧中存儲的點就為凸包。三、編程實現(xiàn)1、判斷點p3是否在p1p2左邊函數(shù)。2、定義一個點類3、定義一個CGramhamCaclu類，用來生成凸包4、CGramhamCaclu類詳細代碼：CGramhamCaclu:CGramhamCaclu() CGramhamCaclu:CGramhamCaclu(CGramhamCa

19、clu& crah)CGramhamCaclu:CGramhamCaclu()/畫原始點void CGramhamCaclu:DrawPoints(CDC* pDC) CPen * pen = new CPen(0,1,RGB(255,0,0); CPen * oldpen = pDC->SelectObject(pen); int x,y; for (int i=0;i<InitialPoints.GetSize ();i+) x = InitialPointsi.x; y = InitialPointsi.y; pDC->Ellipse(x-3,y-3,x+3,y

20、+3);/畫點 CString s; s.Format("%d",i); pDC->TextOut(x,y,s);/畫序號 pDC->SelectObject(oldpen);/畫凸包void CGramhamCaclu:DrawMinmumPolygon(CDC* pDC) CPen * pen = new CPen(0,1,RGB(255,0,0); CPen * pen1 = new CPen(1,2,RGB(0,255,0); int size = temparr.GetSize();if (size>=3)CPen * oldpen = pDC-

21、>SelectObject(pen);CString s("基點"); pDC->TextOut(InitialPointsindex.x,InitialPointsindex.y,s);/畫每個點與基點構成的向量，可以不要/for (int i1=1;i1<SortPoints.GetSize();i1+)/pDC->MoveTo(SortPoints0.x,SortPoints0.y);/pDC->LineTo(SortPointsi1.x,SortPointsi1.y);/pDC->SelectObject(oldpen); CPe

22、n * oldpen1 = pDC->SelectObject(pen1);pDC->MoveTo(temparr0.x,temparr0.y);for ( int i=1;i<size;i+)pDC->LineTo(temparri.x,temparri.y);pDC->LineTo(temparr0.x,temparr0.y); pDC->SelectObject(oldpen1);/凸包計算void CGramhamCaclu:CaculTuBao()if (InitialPoints.GetSize()>=3)InitialSortPoints

23、();/初始化排序數(shù)組 CGramhamCaclu:index = FindBasePoint(SortPoints);/找基點if (CGramhamCaclu:index>=0)Exchange(CGramhamCaclu:index,0);bool sort = Sort();/排序if (sort)Stack();/棧操作/初始化排序數(shù)組 void CGramhamCaclu:InitialSortPoints()if (InitialPoints.GetSize()>=3)for (int i=0;i<InitialPoints.GetSize();i+)SortP

24、oints.Add (InitialPointsi);/找基點int CGramhamCaclu:FindBasePoint(CArray<Cpoint2D,Cpoint2D>& cp) Cpoint2D cpd; int index =-1; CArray<int,int> carray; if (cp.GetSize()>=3) index = 0; cpd = cp0; /找一個y最大值 for (int i=1;i<cp.GetSize();i+) if (cpd.y<cpi.y) cpd = cpi; index = i; /找所有y最大值 for (int j=0;j<cp.GetSize();j+) if (cpj.y = cpindex.y) carray.Add (j); /找x最大值 if (carray.GetSize()>1) index = carray0; for (i=0;i<carray.GetSize();i+) if (cpindex.x<cpcarrayi.x) index = carrayi; return index;/