平面几何常用算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,平面几何常用算法,2014.8.21,1.,计算几何基础,2026/10/23,2.,凸包问题,3.,旋转卡壳,计算几何基础,2026/10/23,1,、向量（矢量）的概念,设,=a,，则有向线段 的长度叫做向量（矢量）,a,的长度或模，记作,|a|,。,夹角：两个非,0,矢量,a,、,b,，在空间任取一点,O,，作,=a,，,=b,，则角,AOB,叫做矢量,a,与,b,的夹角，记作,。若,=/2,，则称,a,与,b,互相垂直，记作,ab,。,计算几何基础,计算几何基础,2,、矢量的加减法,以点,O,为起点、,A,为端点作矢量,a,，以点,A,为起点、,B,为端点作矢量,b,，则以点,O,为起点、,B,为端点的矢量称为,a,与,b,的和,a+b,，如下中图。,若从,A,点作 ，要求 的模等于,|b|,，方向与,b,相反，即,=-b,，则以,O,为起点、,B,为端点的矢量称为,a,与,b,的差,a-b,，如下右图。,3,、矢量的分解,定理：,如果平面两个矢量,a,b,，对任一矢量,p,，一定存在一个且仅一个有序实数组,x,y,，使得：,p=xa+yb,。,含义与物理上的合力,或,力的分解一样。,形式上看，相当于长方形的对角线。,计算几何基础,4,、矢量的数量积（点乘）,两个矢量的数量积是一个数，大小等于这两个矢量的模的乘积再乘以它们夹角的余弦。即：,a,b,|a|b|cos,数量积等于两个矢量的对应支量乘积之和。即：,a,b,a,x,b,x,a,y,b,y,计算几何基础,5,、矢量的矢量积（叉乘、叉积）,矢量积的一般含义：两个矢量,a,和,b,的矢量积是一个矢量，记作,ab,，其模等于由,a,和,b,作成的平行四边形的面积，方向与平行四边形所在平面垂直，当站在这个方向观察时，,a,逆时针转过一个小于,的角到达,b,的方向。这个方向也可以用物理上的右手螺旋定则判断：右手四指弯向由,A,转到,B,的方向（转过的角小于,），拇指指向的就是矢量积的方向。,计算几何基础,9,、矢量的矢量积（叉乘、叉积）,探讨一个重要问题：给定两个矢量：和 ，对它们的公共端点,P0,来说，判断 是否在 的顺时针方向。,方法：,如图，把,P0,作为原点，得出向量,P1,=P1-P0,和,P2,=P2-P0,，因此，这两个向量的叉积为：,如果该叉积为正，,则 在 的顺时针方向，,如果为负，则 在 的逆时针方向。,如果等于,0,，则,P0,，,P1,，,P2,三点共线。,计算几何基础,判断线段是否相交的模板（hdu1086）,include,using namespace std;,struct point,double x,y;,;,struct segment,point begin,end;,;,double min(double x,double y),return xy?x:y;,bool onsegment(point pi,point pj,point pk)/,判断点,pk,是否在线段,pi pj,上,if(min(pi.x,pj.x)=pk.x&pk.x=max(pi.x,pj.x),if(min(pi.y,pj.y)=pk.y&pk.y=max(pi.y,pj.y),return true;,return false;,double direction(point pi,point pj,point pk)/,计算向量,pkpi,和向量,pjpi,的叉积,return(pi.x-pk.x)*(pi.y-pj.y)-(pi.y-pk.y)*(pi.x-pj.x);,bool judge(point p1,point p2,point p3,point p4)/,判断线段,p1p2,和,p3p4,是否相交,double d1=direction(p3,p4,p1);,double d2=direction(p3,p4,p2);,double d3=direction(p1,p2,p3);,double d4=direction(p1,p2,p4);,if(d1*d20&d3*d40),return true;,if(d1=0&onsegment(p3,p4,p1),return true;,if(d2=0&onsegment(p3,p4,p2),return true;,if(d3=0&onsegment(p1,p2,p3),return true;,if(d4=0&onsegment(p1,p2,p4),return true;,return false;,二.判断点是否在多边形内,方法一：射线法,仔细观察：,在多边形内的点和不在多边形内的点向某个方向引一条射线，这些射线和多边形的交点的个数有什么特点？,结论：,如果从该点引一条射线，这条射线和多边形的交点个数为奇数，则该点在多边形里面，若为偶数，则该点在多边形外面。,由于有更好更容易实现的弧长法，就不贴射线法的模板了。,弧长 法（转角法）：,将坐标原点平移到被测点,P,这个新坐标系将平面划分为,4,个象限,对每个多边形顶点,Pi,只考虑其所在的象限，然后按邻接顺序访问多边形的各个顶点,Pi,分析,Pi,和,Pi+1,有下列四种情况,:,、,(1)Pi+1,和,Pi,在同一象限，此时弧长和不变,;,(1)Pi+1,在,Pi,的下一象限,此时弧长和加,/2;,(2)Pi+1,在,Pi,的上一象限,此时弧长和减,/2;,(3)Pi+1,在,Pi,的相对象限,首先计算,f=pi+1.y*pi.x-pi+1.x*pi.y(,叉积,),若,f=0,则点在多边形上,;,若,f0,弧长和加,.,最后对算出的代数和和上述的情况一样判断即可,.,实现的时候要注意,:,若被测点和多边形的顶点重合时要特殊处理,.,具体实现的时候,取,x=0 y=0,作为第一象限,x=0,作为第二象限,x0 y=0 y0,作为第四象限,2026/10/23,S=-pi/2-pi/2+0-pi/2-pi/2 =-2*pi,弧长法模板（,zju1081,）,2026/10/23,struct point,int x,y;,pMAX;,bool inpolygon(point t,int n)/t,为需要判断的点,n,为多边形点的个数,int i,sum=0;/,用来保存弧长和,pn=p0;/,因为第一个点和最后一个点的象限关系也要判断,for(i=0;i=0?(p0.y=0?0:3):(p0.y=0?1:2);/,计算第一个点的象限,for(i=1;i=0?(pi.y=0?0:3):(pi.y=0?1:2);/,计算象限,if(t2=(t1+1)%4)sum+=1;/Pi+1,在,Pi,的下一象限,此时弧长和加,/2;,else if(t2=(t1+3)%4)sum-=1;/Pi+1,在,Pi,的上一象限,此时弧长和减,/2;,else if(t2=(t1+2)%4)/Pi+1,在,Pi,的相对象限,if(f0)sum+=2;,else sum-=2;,t1=t2;,for(int j=0;jn;j+)/,恢复坐标,pj.x+=t.x;,pj.y+=t.y;,if(i,边长,=,海伦公式,=,面积,2026/10/23,24,思考：此方法的缺点：,计算量大,精度损失,更好的方法？,2026/10/23,26,大功告成：,Area(A,B,C)=1/2*(AB)(AC),=,/2,特别注意：,以上得到是,有向面积（有正负）,！,Xb X a Yb Y a,Xc X a Yc Y a,2026/10/23,27,凸多边形的三角形剖分,很自然地，我们会想到以,P1,为扇面中心，连接,P1Pi,就得到,N-2,个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：,A=sigma(Ai)(i=1,N-2),P1,P2,P3,P4,P5,P6,A1,A2,A3,A4,2026/10/23,28,凹多边形的面积？,P1,P4,P3,P2,2026/10/23,30,任意点为扇心的三角形剖分,：,我们能把多边形分成,N-2,个三角形，为什么不能分成,N,个三角形呢？,比如，以多边形内部的一个点为扇心，就可以把多边形剖分成,N,个三角形。,P0,P1,P2,P6,P5,P4,P3,2026/10/23,31,前面的三角剖分显然对于多边形内部任意一点都是合适的！,我们可以得到：,A=sigma(Ai),（,i=1,N,）,即,：,A,=,sigma,/2,（,i=1,N,）,Xi X0 Yi Y0,X(i+1)X0 Y(i+1)Y0,2026/10/23,32,能否把扇心移到多边形以外呢？,P0,P1,P2,P3,P4,2026/10/23,33,既然内外都可以，为什么不设,P0,为坐标原点呢？,O,P1,P2,P3,P4,现在的公式？,2026/10/23,34,简化的公式：,A,=,sigma,/2,（,i=1,N,）,Xi Yi,X(i+1)Y(i+1),2026/10/23,35,基本问题（,2,）：,给定一个简单多边形，求其重心。,输入,：多边形（顶点按逆时针顺序排列）,输出,：重心点,C,求任意多边形的重心,1,、质量集中在顶点上，,n,个顶点坐标为,(xi,yi),，质量为,mi,，则重心,X=(ximi)/mi,Y=(yimi)/mi,2,、若每个点的质量相同则,X=xi/n,Y=yi/n 2,、质量分布均匀,3,、特殊地，质量均匀的三角形重心：,X=(x0+x1+x2)/3,Y=(y0+y1+y2)/3,2026/10/23,将n边形分成多个三角形，分别求出重心坐标以及质量m【因为质量分布均匀，所以可以设密度为1，则面积就是质量】因为质量都集中在重心 所以把所有求出来的重心按逆时针连接起来又是一个多边形 但是这个多边形的质量集中在顶点上 所以可以利用上面公式进行计算,2026/10/23,求质量分布均匀的,n,边形重心,#include,#include,#include,using namespace std;,const int N=1000000;,struct point,double x;,double y;,pN,g;/p,数组保存多边形的顶点,double crossProd(point A,point B,point C)/,计算三角形,ABC,有向面积,return(B.x-A.x)*(C.y-A.y)-(B.y-A.y)*(C.x-A.x);,void compGravity(int n)/,求重心,g,point tmp;double sumArea,area;sumArea=0;g.x=g.y=0;,for(int i=2;in;+i),area=crossProd(p0,pi-1,pi);,sumArea+=area;,tmp.x=p0.x+pi-1.x+pi.x;,tmp.y=p0.y+pi-1.y+pi.y;,g.x+=tmp.x*area;,g.y+=tmp.y*area;,g.x/=(sumArea*3.0);g.y/=(sumArea*3.0);,2026/10/23,二、凸包的求解,2026/10/23,二.凸包的求法(Graham算法),凸包的定义：,你可以这样想象：平面上有很多根钉子,你的手里有一根橡皮环,你用橡皮环把这些钉子都套起来，然后松手，橡皮环所形成的图形就是这些钉子的一个凸包（如下图）,Graham扫描法：,1.,选则,p0,作为,y,坐标最小的点，如果有多个这样的点，则选择,x,最小的。,2.,剩余的点根据他们相对于,p0,的极角的大小从小到大排序，设排序后的点依次为P0.n。,3.,设置一个栈，P0,P1,P2先入栈。,4.对于 P3.n的每个点，若它与栈顶的两个点不构成向左转的关系,则将栈顶的点出栈,直至没有点需要出栈以后将当前点进栈；,所有点处理完之后栈中保存的点就是凸包了。,思考：,如何对这些极角排序？,用atan函数？显然会有精度问题，不准确,回忆一下以前讲的向量的叉积。,2026/10/23,p0,p1,p2,如何知道p2的极角就比p1大呢？,再思考一下如何判断左转还是右转？,自然也是叉积。,显然只需要向量p0p1和向量p0p2做叉积就可以了，如果大于0则p2的极角比p1大。,2026/10/23,43,2026/10/23,44,2026/10/23,45,2026/10/23,46,2026/10/23,47,2026/10/23,48,2026/10/23,49,2026/10/23,50,2026/10/23,51,2026/10/23,52,2026/10/23,53,2026/10/23,54,2026/10/23,55,2026/10/23,graham,算法模板,#include,#include,#include,using namespace std;,const int MAXN=105;,const double eps=1e-8;,struct Point,int x;,int y;,;,Point pMAXN;/,保存输入结点,Point stMAXN;/,保存凸包结点，把,que,当一个栈来使用,int top;/,记录栈顶位置,double dis(Point a,Point b)/,求,a,b,两点距离,return sqrt(double(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);,int cross(Point p1,Point p2,Point p0)/,求,P0P1,与,P0P2,的叉积,return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);,bool cmp(Point p1,Point p2),int k=cross(p2,p1,p0);/p0p2,叉乘,p0p1,if(keps)/p1,的极角比,p2,小或者极角相等去距离大的,return true;else return false;,void GrahamScan(int n),Point tmp;int k=0;,for(int i=1;in;+i)/,找出,y,值,(y,值相同时找,x,最小,),最小的点作为起始点,P0,if(pi.y pk.y)|(pi.y=pk.y)&(pi.xpk.x),k=i;,tmp=p0;p0=pk;pk=tmp;,sort(p+1,p+n,cmp);/,按极角大小排序,top=-1;st+top=p0;st+top=p1;st+top=p2;/,先把极角最小的,0,1,2,三点存入栈中,for(int i=3;i=0)/,如果不能左转,则退栈,top-;,st+top=pi;,+top;,2026/10/23,平面几何题目,Hdu1086 (,判断线段是否相交,),Zju 1081(,判断点是否在多边形内,),Hdu1756(,判断点是否在多边形内部,),Hdu1348 1392(,求凸包,),Hdu1115(,求质量分布均匀的多边形的重心,),以上都是基础模板题。,2026/10/23,2026/10/23,END,