[凸包生成算法实验报告.docx

实验报告班 级： 学生姓名： 学 号： 201101218 日 期: 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的右侧；如果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 (s0){return 1; //点在直线左侧}else if (s0){return 2;//点在直线右侧} else{return 0;//点在直线上} }二、计算多边形内角算法过程第一步：输入一系列的离散点；第二步：找x坐标值最小的点p0，这样能确定由此点构成的多边形的角是凸的；第三步：定义与p0点相邻的前后两个点p1，p2，若超出数组边界，则用首点或尾点取代；第四步：计算p2与向量p1p0的位置关系，若p2在向量p1p0的左边，则多边形呈逆时针方向；若p2在向量p1p0的右边，则多边形呈顺时针方向。第五步：计算多边形的各个内角，利用两个向量的夹角公式计算。由于多边形有凹凸性，所以算角时要分情况。找规律可知，若多边形是逆时针走向，那么，若三个相邻的点构成凸角，三点的走向始终是逆时针走向，否则，是顺时针走向，故可根据此来确定角度。算法实现定义点类class MyPoint {public:MyPoint();virtual ~MyPoint();public:int id;int x,y,z;};定义数学计算类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 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 (s0){return 1; //点在直线左侧}else if (s0){return 2;//点在直线右侧} else{return 0;//点在直线上} }//计算角度float MyMath::CalcuAngle(MyPoint p1, MyPoint p2, MyPoint p3,int flag){ //判断正逆方向float d = CalCuMatrix(p1,p2,p3);float angle = 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);}}}//求矩阵，用于判断走向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::Vec