凸包生成算法实验报告

1、精选优质文档-倾情为你奉上实验报告班 级： 学生姓名： 学 号： 日 期: 2014年5月11日 判断点线关系及计算多边形内角一、点与线的关系（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）为正数，则C在矢量AB的左侧；如果S（A，B，C）为负数，则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;/点在直线上 二、计算多边形内角（1） 算法过程第一步：输入一系列的离散点；第二步：找x坐标值最小的点p0，这样能确定由此点构成的多边形的角是凸的；第三步：定义与

3、p0点相邻的前后两个点p1，p2，若超出数组边界，则用首点或尾点取代；第四步：计算p2与向量p1p0的位置关系，若p2在向量p1p0的左边，则多边形呈逆时针方向；若p2在向量p1p0的右边，则多边形呈顺时针方向。第五步：计算多边形的各个内角，利用两个向量的夹角公式计算。由于多边形有凹凸性，所以算角时要分情况。找规律可知，若多边形是逆时针走向，那么，若三个相邻的点构成凸角，三点的走向始终是逆时针走向，否则，是顺时针走向，故可根据此来确定角度。（2） 算法实现1、 定义点类class MyPoint public:MyPoint();virtual MyPoint();public:int id;

4、int x,y,z;2、 定义数学计算类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)/逆时针，凸多边形(在数学坐标系中正确，程序中相反)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; /计算多边形内角 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算法的主要思想就是，最终形成的凸包，即包围所有点的凸多边形，假定多边形是按逆时针方向生成的，那么多边形内部包围的所有点与多边形每个有向边的关系都是：点在有向边的左边。依照此思想，只要找到一个出发点，然后依此出发点按逆时针方向构建多边形，并保证每加入一条有向边时，都要满足其余点都在该边的左边。具体算法过程：（1）输入：点集S=P（2）寻找基点P0：在所有点中找到y坐标最小的点，若找到多个，则选取其中X

16、坐标最大的点作为基点，若只找到一个，则直接以这个点作为基点。（3）排序：以基点为起点，以其余点为终点构成一个向量<P0,PK>，逐个计算每个向量与x轴正方向的夹角，并按夹角有小到大进行排序，得到一个排序的点S1=p0,p1,p2,p3p(N-1)；对于夹角相同的点，剔除掉离基点近的点，只保留离基点最远的那个点。注意：由于计算角度复杂且耗时，在这里采用另外一种方式处理，根据上面的点线关系，从基点p0出发，依次遍历其它点，设为pk，p0和pk就构成一条有向向量，依次判断其它点（如pm）在向量的哪个方向，若在线段右边，则用其它点代替pk，构成一个新向量p0pm,继续判断剩余的点，这样一趟

17、下来，就能找到最右边的点；依此道理判断其他点。如图：从向量p0p3（p3是任意选的，最终要将除p0外的所有点选到即可）开始，p1在向量p0p3左边，不变；p2在p0p3左边，向量不变；p4在p0p3右边，这时要将比较的向量变为p0p4；继续遍历p5，p5在p0p4右边，向量变为p0p5；继续遍历p6,p6在向量p0p5右边，向量变为p0p6；遍历p7，p7在向量p0p6右边，向量变为p0p7，这一趟下来就将p7这一个最右边的点找到了。同样的方法排序其他点，最后向量按与x轴正方向的顺序就是p7,p6,p5,p4,p3,p2,p1,依次递增。（4）构造凸包：第一步：首先将基点p0入栈，p1和p2也

18、依次入栈；第二步：取栈顶的前两个点构成向量，即向量<p(k-1),pk>；第三步：判断点p(k+1)是否在向量的左边；第四步： 情况1:若在向量的左边，则将点p(k+1)入栈，重复第二步； 情况2：若在向量的右边，将点pk出栈，继续取下一个点，重复步骤二。第五步：最后栈中存储的点就为凸包。三、编程实现1、判断点p3是否在p1p2左边函数。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、();/初始化排序数组 CGramhamCaclu:index = FindBasePoint(SortPoints);/找基点if (CGramhamCaclu:index>=0)Exchange(CGramhamCaclu:index,0);bool sort = Sort();/排序if (sort)Stack();/栈操作/初始化排序数组 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;/