《计算几何在程序设计竞赛中的应用.ppt》由会员分享，可在线阅读，更多相关《计算几何在程序设计竞赛中的应用.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、计算几何在程序设计竞赛中的应用计算几何在程序设计竞赛中的应用软件学院2003级穆浩英预备知识预备知识(I)差乘：计算几何的基本问题是计算几何的基本问题是位置和方向，基本运算位置和方向，基本运算是向量的差乘和点乘是向量的差乘和点乘aba x b=xayb-xbya=xa yaxb yb=a b sin两个向量差积的几何意义是以两个向量差积的几何意义是以两向量为邻边的平行四边形的两向量为邻边的平行四边形的有向面积，若有向面积，若为右手螺旋为右手螺旋方向结果为正，否则为负。方向结果为正，否则为负。（为有向夹角）为有向夹角）所以，计算几何中的位置是指所以，计算几何中的位置是指左右左右。如果。如果axb
2、0则则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-x2*y1);int main()int r
7、x,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)line makeline(point p1,point p2)line l;int sign=1;l.a=p2.y-p1.y
8、;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相交用差积cross(a,b,c)*cross(a,b,d)0&cross(c,d,a)*cross(c,d,b)cutting_num)&cutting_num 0)line_seg cuttings8;int line_num=0;for(int i=0;i l;if(line_num=0|!line_already_exists(
9、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(int j=0;j0&!point_already_exists(cross_pt,new_cross_pts)new_cross_pts.push_back(cross_pt);partion_num+
10、=(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算法算法(了解了解Gift-Wrapping算法算法)试探性凸包试探性凸包 我们尝试从我们尝试从p1(最低点，一定属于凸包最低点，一定属于凸包)出发，沿着出发，沿着多边形顶点逆时针的顺序，试探性的增长凸包多边形顶点逆时
12、针的顺序，试探性的增长凸包.显然，显然，一个点如果属于凸包，那么它到达下一个点一定需要一个点如果属于凸包，那么它到达下一个点一定需要左转，否则，该点一定不属于凸包。左转，否则，该点一定不属于凸包。P1P2P4P3P6P5P1P2P3P4P6P5凸凸包包顶顶点点基本问题举例基本问题举例()算法总结：算法总结：2.该算法带有简单的回溯，因此宜用栈实现，栈中存储的是该算法带有简单的回溯，因此宜用栈实现，栈中存储的是 到目前为止的到目前为止的“局部凸包局部凸包”，如果当前边对于栈顶边右转，就，如果当前边对于栈顶边右转，就 退栈。一直到退栈。一直到“局部凸包局部凸包”完整。完整。1.Graham-Sca
13、n需要一个序，如果输入是平面点集，首先需要需要一个序，如果输入是平面点集，首先需要对所有的点按极角排序。显然，对所有的点按极角排序。显然，“极角大小极角大小”比较用比较用“左右左右手手”关系比较关系比较(差积差积)即：即：BCi的极角比的极角比BCj的极角大的极角大BCi在在BCj左边。左边。基本问题举例基本问题举例()3.伪代码：伪代码：push(p1);push(p2);i=3;while i=n doif pi 在栈顶边在栈顶边pt-1pt左手方向左手方向then push(pi)并且并且i+；else pop();4.复杂度分析复杂度分析 上述上述while语句中，每个点显然进栈一次，
14、而最多出栈语句中，每个点显然进栈一次，而最多出栈一次，故时间复杂度为一次，故时间复杂度为O(n).附加问题附加问题(需要离散化问题需要离散化问题)例：例：zju1128 问题描述：一些已知右下顶点和左上顶点坐标的矩问题描述：一些已知右下顶点和左上顶点坐标的矩形，这些矩形可能部分重叠，求它们所占的实际面积。形，这些矩形可能部分重叠，求它们所占的实际面积。例如：例如：附加问题附加问题(需要离散化问题需要离散化问题)方案一、方案一、把矩形映射到数组把矩形映射到数组M 中，如果某矩形的位置为（中，如果某矩形的位置为（x1，y1）（）（x2，y2）则）则Mij=1（其中（其中x1=i=x2,y1=jx1
15、,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 xy200200;double N=0.000001;int n_map;void input();void solve();double cacu();附加问题附加问题(需要离散化问题需要离散化问题)int main
16、()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&k N&k N&k 2*n_map)k+;j2=k;for(I=i1;I i2;I+)for(J=j1;J j2;J+)xyIJ=true;附加问题附加问题(需要离散化问题需要离散化问题)double cacu()double sum=0;for(int i=0;i 2*n_map;i+)for(int j=0;j 2*n_map;j+)sum+=xyij*(xi+1-xi)*(yj+1-yj);return sum;