凸包生成算法实验报告

实验报告班级：学生姓名：学号：201101218日期:2014年5月11日判断点线关系及计算多边形内角一、点与线的关系（1）定义：平面上的三点P1(x1,y1),P2(x2,y2),P3(x3,y3)的面积量：|x1x2x3|S(P1,P2,P3)=|y1y2y3|=(x1-x3)*(y2-y3)-(y1-y3)*(x2-x3)|111|当P1P2P3逆时针时S为正的，当P1P2P3顺时针时S为负的。令矢量的起点为A，终点为B，判断的点为C，如果S（A，B，C）为正数，则C在矢量AB的左侧；如果S（A，B，C）为负数，则C在矢量AB的右侧；如果S（A，B，C）为0，则C在直线AB上。（2）算法intMyMath::IsRightInLine(MyPointp1,MyPointp2,MyPointp3){ints;s=(p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x);if(s0){return1;//点在直线左侧}elseif(s0){return2;//点在直线右侧}else{return0;//点在直线上}}二、计算多边形内角（1）算法过程第一步：输入一系列的离散点；第二步：找x坐标值最小的点p0，这样能确定由此点构成的多边形的角是凸的；第三步：定义与p0点相邻的前后两个点p1，p2，若超出数组边界，则用首点或尾点取代；第四步：计算p2与向量p1p0的位置关系，若p2在向量p1p0的左边，则多边形呈逆时针方向；若p2在向量p1p0的右边，则多边形呈顺时针方向。第五步：计算多边形的各个内角，利用两个向量的夹角公式计算。由于多边形有凹凸性，所以算角时要分情况。找规律可知，若多边形是逆时针走向，那么，若三个相邻的点构成凸角，三点的走向始终是逆时针走向，否则，是顺时针走向，故可根据此来确定角度。（2）算法实现1、定义点类classMyPoint{public:MyPoint();virtual~MyPoint();public:intid;intx,y,z;};2、定义数学计算类classMyMath{public:MyMath();virtual~MyMath();public:staticfloatCalcuAngle(MyPointp1,MyPointp2,MyPointp3,intflag);//算角度staticintIsRightInLine(MyPointp1,MyPointp2,MyPointp3);//判断点与直线位置关系protected:staticfloatVectorAngel(MyPointp1,MyPointp2,MyPointp3);//计算向量角staticfloatCalCuMatrix(MyPointp1,MyPointp2,MyPointp3);};详细代码：//点与直线的关系intMyMath::IsRightInLine(MyPointp1,MyPointp2,MyPointp3){ints;s=(p1.x-p3.x)*(p2.y-p3.y)-(p1.y-p3.y)*(p2.x-p3.x);if(s0){return1;//点在直线左侧}elseif(s0){return2;//点在直线右侧}else{return0;//点在直线上}}//计算角度floatMyMath::CalcuAngle(MyPointp1,MyPointp2,MyPointp3,intflag){//判断正逆方向floatd=CalCuMatrix(p1,p2,p3);floatangle=VectorAngel(p1,p2,p3);if(flag==1){if(d0)//逆时针，凸多边形(在数学坐标系中正确，程序中相反){return(180.0-angle);}else//顺时针，凹多边形{return(180.0+angle);}}if(flag==2){if(d0)//逆时针，凸多边形{return(180.0+angle);}else//顺时针，凹多边形{return(180.0-angle);}}}//求矩阵，用于判断走向floatMyMath::CalCuMatrix(MyPointp1,MyPointp2,MyPointp3){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));}//求向量夹角floatMyMath::VectorAngel(MyPointp1,MyPointp2,MyPointp3){intdx1=p2.x-p1.x;intdy1=p2.y-p1.y;intdx2=p3.x-p2.x;intdy2=p3.y-p2.y;floata=(dx1*dx2+dy1*dy2)/(sqrt(dx1*dx1+dy1*dy1)*sqrt(dx2*dx2+dy2*dy2));return(180*acos(a))/3.1415;}3、定义多边形类classMyPolygon{public:MyPolygon();virtual~MyPolygon();public:CArrayMyPoint,MyPointdingDianArray;//多边形顶点CArrayint,inttrangleArray;//角度intflag;//判断顺逆方向,逆为2，顺为1，初始为0public:voidAddPoint(MyPointp);//加点voidDrawPolygon(CDC*pDC);//画多边形boolCacul();//计算夹角}；详细代码：//画多边形voidMyPolygon::DrawPolygon(CDC*pDC){CPen*pen=newCPen(0,1,RGB(255,0,0));CPen*oldPen=pDC-SelectObject(pen);intix,iy;intdianCount=dingDianArray.GetSize();//画点for(inti=0;idingDianArray.GetSize();i++){ix=dingDianArray[i].x;iy=dingDianArray[i].y;pDC-Ellipse(ix-3,iy-3,ix+3,iy+3);}//画边if(dianCount=3){pDC-MoveTo(dingDianArray[0].x,dingDianArray[0].y);for(inti=1;idianCount;i++){pDC-LineTo(dingDianArray[i].x,dingDianArray[i].y);}pDC-LineTo(dingDianArray[0].x,dingDianArray[0].y);}//画角度if(trangleArray.GetSize()0){for(inti=0;itrangleArray.GetSize();i++){CStrings;s.Format(%d,trangleArray[i]);pDC-TextOut(dingDianArray[i].x,dingDianArray[i].y,s);}}pDC-SelectObject(oldPen);}//加点voidMyPolygon::AddPoint(MyPointp){dingDianArray.Add(p);}//计算方向和角度boolMyPolygon::Cacul(){if(dingDianArray.GetSize()3){flag=0;returnfalse;}else{//找x值最小的点intindex=0;MyPointp=dingDianArray[0];for(inti=1;idingDianArray.GetSize();i++){MyPointpi=dingDianArray[i];if(p.xpi.x){index=i;p=pi;}}//定义与当前点相邻的两点inti_1=index-1;inti1=index+1;if(i_10){i_1=dingDianArray.GetSize()-1;}if(i1dingDianArray.GetSize()-1){i1=0;}MyPointpi_1=dingDianArray[i_1];MyPointpi1=dingDianArray[i1];//判断点线位置关系，确定多边形的走向intisRight=MyMath::IsRightInLine(pi_1,p,pi1);if(isRight==1){flag=1;}elseif(isRight==2){flag=2;}else{flag=0;}//计算多边形内角trangleArray.RemoveAll();for(i=0;idingDianArray.GetSize();i++){i_1=i-1;i1=i+1;if(i_10){i_1=dingDianArray.GetSize()-1;}if(i1dingDianArray.GetSize()-1){i1=0;}p=dingDianArray[i];pi_1=dingDianArray[i_1];pi1=dingDianArray[i1];floatangle=MyMath::CalcuAngle(pi_1,p,pi1,flag);trangleArray.Add((int)angle);}returntrue;}returnfalse;}（3）算法结果凸包生成算法一、凸包定义通俗的说就是：一组平面上的点，求一个包含所有点的最小凸多边形，这个最小凸多边形就是凸包。二、Graham算法思想概要：Graham算法的主要思想就是，最终形成的凸包，即包围所有点的凸多边形，假定多边形是按逆时针方向生成的，那么多边形内部包围的所有点与多边形每个有向边的关系都是：点在有向边的左边。依照此思想，只要找到一个出发点，然后依此出发点按逆时针方向构建多边形，并保证每加入一条有向边时，都要满足其余点都在该边的左边。具体算法过程：（1）输入：点集S={P}（2）寻找基点P0：在所有点中找到y坐标最小的点，若找到多个，则选取其中X坐标最大的点作为基点，若只找到一个，则直接以这个点作为基点。（3）排序：以基点为起点，以其余点为终点构成一个向量P0,PK，逐个计算每个向量与x轴正方向的夹角，并按夹角有小到大进行排序，得到一个排序的点S1={p0,p1,p2,p3…p(N-1)}；对于夹角相同的点，剔除掉离基点近的点，只保留离基点最远的那个点。注意：由于计算角度复杂且耗时，在这里采用另外一种方式处理，根据上面的点线关系，从基点p0出发，依次遍历其它点，设为pk，p0和pk就构成一条有向向量，依次判断其它点（如pm）在向量的哪个方向，若在线段右边，则用其它点代替pk，构成一个新向量p0pm,继续判断剩余的点，这样一趟下来，就能找到最右边的点；依此道理判断其他点。如图：从向量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也依次入栈；第二步：取栈顶的前两个点构成向量，即向量p(k-1),pk；第三步：判断点p(k+1)是否在向量的左边；第四步：情况1:若在向量的左边，则将点p(k+1)入栈，重复第二步；情况2：若在向量的右边，将点pk出栈，继续取下一个点，重复步骤二。第五步：最后栈中存储的点就为凸