计算几何在程序设计竞赛中的应用ppt课件

1、计算几何在程序设计竞赛中的应用计算几何在程序设计竞赛中的应用软件学院2019级穆浩英预备知识预备知识(I)差乘：计算几何的基本问题计算几何的基本问题是位置和方向，基本是位置和方向，基本运算是向量的差乘和运算是向量的差乘和点乘点乘aba x b =xayb-xbya=xa yaxb yb = a b sin两个向量差积的几何意义是以两个向量差积的几何意义是以两向量为邻边的平行四边形的两向量为邻边的平行四边形的有向面积，若有向面积，若为右手螺旋为右手螺旋方向结果为正，否则为负。方向结果为正，否则为负。（为有向夹角）为有向夹角） 所以，计算几何中的位置是指左右。如果所以，计算几何中的位置是指左右。如

2、果axb0则则a在在b的右边的右边否则否则a在在b的左边的左边预备知识预备知识(II)差积应用(1)：判断两条线段是否相交计算几何的基本问题计算几何的基本问题是位置和方向，基本是位置和方向，基本运算是向量的差乘和运算是向量的差乘和点乘点乘首先，将线段作向量处理。首先，将线段作向量处理。如果点如果点(x3,y3)、(x4,y4)分别在分别在A的的两侧两侧,同时点同时点(x1,y1)、点、点(x2,y2)分别分别在在B的两侧的两侧(xy)，则可以确定，则可以确定A与与B相交相交.我们定义一种运算我们定义一种运算cross(a,b,c)，它，它的返回值为向量的返回值为向量与向量与向量的的差积。差积。

3、那么：那么： if(cross(a,b,c)*cross(a,b,d)0 &cross(c,d,a)*cross(c,d,b)0) return TRUE；a(x1,y1)b(x2,y2)c(x3,y3)d(x4,y4)AB(x3,y3)(x4,y4)在A的两边预备知识预备知识(III)特殊情况：计算几何的基本问题计算几何的基本问题是位置和方向，基本是位置和方向，基本运算是向量的差乘和运算是向量的差乘和点乘点乘efghabcd（一）（一）（二）（二）cross(a,b,d) =0 ,cross(e,f,h)=0,但一可以认为相交，（二但一可以认为相交，（二则不可以认为相交则不可以认为相交 。判

4、断交点是否在线段上。判断交点是否在线段上预备知识预备知识(VI)为解决上述问题，我们引入点乘：计算几何的基本问题计算几何的基本问题是位置和方向，基本是位置和方向，基本运算是向量的差乘和运算是向量的差乘和点乘点乘baa .b = xa*xb + ya*yb = a b cosabc当当cross(a,b,c)=0时，假如时，假如 . 小于等于小于等于0，那么，那么c点在点在ab上，否则上，否则c点在点在ab外外预备知识预备知识(V)设设dot(a,b,c) 返回返回.的值。我们来看的值。我们来看dot(a,b,c)值与值与c在在ab上投影上投影c的关系的关系.计算几何的基本问题计算几何的基本问题

5、是位置和方向，基本是位置和方向，基本运算是向量的差乘和运算是向量的差乘和点乘点乘abccccdot(a,b,c) = 0c在在a上上 cdot(a,b,c) ab 2 c在在ab前前 0 dot(a,b,c) ab 2c在在ab上上 基本问题举例基本问题举例()1.位置 (左右)判断例：zju1041问题描述：在有n个点的面上有一个给定了半径和圆心坐标的半圆，半圆可以绕圆心转动但不可以平移，求半圆最多能包含多少点，边界上的点认为在圆内。基本问题举例基本问题举例()基本思路：1.到圆心的距离大于半径的点直到圆心的距离大于半径的点直接排除。接排除。2.以圆心和任意一点确定一以圆心和任意一点确定一

6、有有向线段作为半径位置，分别计数向线段作为半径位置，分别计数该有向线段左边点的个数该有向线段左边点的个数(nl)和和右边点的个数右边点的个数(nr)。3.重复步骤重复步骤2直到所有点都被枚举直到所有点都被枚举过。过。4.枚举过程中出现的最大的枚举过程中出现的最大的nl或或nr就是所求的结果。就是所求的结果。nl =nr =Max =34452433452534基本问题举例()代码：代码：#includeusing namespace std;struct point int x,y;pp150;int det(int x1,int y1,int x2,int y2) return(x1*y2-

7、x2*y1);int main() int rx,ry; double r; while(cinrxryr & r0) int max = 0; r=r*r; int n,i; int p = 0;cinn;for(i = 0 ;i xy; if(x-rx)*(x-rx)+(y-ry)*(y-ry)=r) ppp.x=x; ppp+.y=y; for(i = 0 ;i p ; i +) int num_l=0，num_r=0，j; for(j = 0; j 0) num_l+; if(dmax) max = num_l;if(num_rmax) max = num_r;coutmax= 0)l

8、ine makeline(point p1,point p2) line l; int sign = 1; l.a=p2.y-p1.y; if( l.a0 ) sign = -1; l.a=sign*l.a; l.b=sign*(p1.x-p2.x); l.c=sign*(p1.y*p2.x-p1.x*p2.y); return l; 基本问题举例（基本问题举例（）l相关算法l判断两线段是否相交，如果相交则求出交点l相交用差积cross(a,b,c)*cross(a,b,d)0 &cross(c,d,a)*cross(c,d,b) cutting_num) & cutting_num 0) l

9、ine_seg cuttings8; int line_num=0; for(int i=0;i l;if(line_num=0 | !line_already_exists(l,cuttings,line_num) )cuttingsline_num+=l; int main(int argc, char *argv)/ int partion_num = line_on_edge(cuttings0)?1:2; for(int i=1;iline_num;i+) if(line_on_edge(cuttingsi)continue; vector new_cross_pts; for(in

10、t j=0;j0&!point_already_exists(cross_pt,new_cross_pts) new_cross_pts.push_back(cross_pt); partion_num+=(1+new_cross_pts.size(); cout partion_num endl; return 0;基本问题举例基本问题举例()3.求多边形的面积。求多边形的面积。 前面已经讲过，两向量的差积的几何意义前面已经讲过，两向量的差积的几何意义是以这两个向量为邻边的平行四边形的有向面是以这两个向量为邻边的平行四边形的有向面积，我们可以利用这一点来求简单多边形的面积，我们可以利用这一点

11、来求简单多边形的面积。积。所谓简单多边形就是任何不相邻的两条边所谓简单多边形就是任何不相邻的两条边都没有交点，包括凸多边形和凹多边形。都没有交点，包括凸多边形和凹多边形。.基本问题举例基本问题举例()求下面多边形的面积，已知个顶点的坐标。A=1/2Xi yi Xi+1 yi+1i=1nabcdefabcdef0基本问题举例基本问题举例()4.求凸包求凸包定义：直观地讲，对于一个平面点集或者一个定义：直观地讲，对于一个平面点集或者一个多边形，它的凸包指的是包含它的最小凸多边形，它的凸包指的是包含它的最小凸图形或最小凸区域。图形或最小凸区域。基本问题举例基本问题举例()Graham-Scan算法算

12、法(了解了解Gift-Wrapping算法算法 )试探性凸包试探性凸包 我们尝试从我们尝试从p1(最低点，一定属于凸包最低点，一定属于凸包)动身，动身，沿着多边形顶点逆时针的顺序，试探性的增长沿着多边形顶点逆时针的顺序，试探性的增长凸包凸包.显然，一个点如果属于凸包，那么它到显然，一个点如果属于凸包，那么它到达下一个点一定需要左转，否则，该点一定不达下一个点一定需要左转，否则，该点一定不属于凸包。属于凸包。 P1P2P4P3P6P5P1P2P3P4P6P5凸包顶点凸包顶点基本问题举例基本问题举例()算法总结：算法总结：2.该算法带有简单的回溯，因此宜用栈实现，栈中存储的是该算法带有简单的回溯，

13、因此宜用栈实现，栈中存储的是 到目前为止的到目前为止的“局部凸包局部凸包”，如果当前边对于栈顶边右转，就，如果当前边对于栈顶边右转，就 退栈。一直到退栈。一直到“局部凸包完好。局部凸包完好。 1. Graham-Scan需要一个序，如果输入是平面点集，首先需要一个序，如果输入是平面点集，首先需要对所有的点按极角排序。显然，需要对所有的点按极角排序。显然， “极角大小比较用极角大小比较用“左右手关系比较左右手关系比较(差积差积) 即：即：BCi的极角比的极角比BCj的极角大的极角大BCi在在BCj左边。左边。基本问题举例基本问题举例()3.伪代码：伪代码：push(p1);push(p2);i=

14、3;while i=n doif pi 在栈顶边在栈顶边pt-1pt左手方向左手方向then push(pi) 并且并且i+；else pop();4.复杂度分析复杂度分析 上述上述while语句中，每个点显然进栈一次，而最多出栈语句中，每个点显然进栈一次，而最多出栈一次，故时间复杂度为一次，故时间复杂度为O(n).附加问题附加问题(需要离散化问题需要离散化问题)例：例：zju1128 问题描述：一些已知右下顶点和左上顶点问题描述：一些已知右下顶点和左上顶点坐标的矩形，这些矩形可能部分重叠，求它们坐标的矩形，这些矩形可能部分重叠，求它们所占的实际面积。例如：所占的实际面积。例如：附加问题附加问

15、题(需要离散化问题需要离散化问题)方案一、方案一、把矩形映射到数组把矩形映射到数组M 中，如果某矩形的位置为中，如果某矩形的位置为x1，y1）（）（x2，y2则则Mij=1其中其中x1=i=x2,y1=jx1,Xi2y1,Yi2=y2令令XY i j = 1 (i从从i1到到i2，j从从j1到到j2)3、统计面积：、统计面积： area+=XYij *(Xi-Xi-1)*(Yi Yi-1)X1X2X5X7Y3Y6Y8Y1Y2附加问题附加问题(需要离散化问题需要离散化问题)代码代码#includeusing namespace std;double x200,y200,in1004;bool x

16、y200200;double N=0.000001;int n_map;void input(); void solve(); double cacu(); 附加问题附加问题(需要离散化问题需要离散化问题)int main() while(cinn_map & n_map != 0) input();sort(x,x+2*n_map);sort(y,y+2*n_map);memset(xy,0,sizeof(xy);solve();double sum=cacu();coutsumendl;return 0;附加问题附加问题(需要离散化问题需要离散化问题)void input()for(int i = 0,k=0 ; i ini0ini1ini2ini3;xk = ini0;yk = ini1;k+;xk = ini2;yk = ini3;k+;附加问题附加问题(需要离散化问题需要离散化问题)void solve()for(int i = 0 ; i N & k N &