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

计算几何在程序设计竞赛中的应用,软件学院2003级穆浩英,预备知识(I),差乘：,两个向量差积的几何意义是以 两向量为邻边的平行四边形的 有向面积，若为右手螺旋 方向结果为正，否则为负。,（为有向夹角）,预备知识(II),差积应用(1)：判断两条线段是否相交,首先，将线段作向量处理。,如果点(x3,y3)、(x4,y4)分别在A的 两侧,同时点(x1,y1)、点(x2,y2)分别 在B的两侧(xy)，则可以确定A与B 相交.,我们定义一种运算cross(a,b,c)，它 的返回值为向量与向量的 差积。,则： if(cross(a,b,c)*cross(a,b,d)0 &cross(c,d,a)*cross(c,d,b)0) return TRUE；,(x3,y3)(x4,y4)在A的两边,预备知识(III),特殊情况：,e,f,g,h,a,b,c,d,（一）,（二）,cross(a,b,d) =0 ,cross(e,f,h)=0,但（一）可以认为相交，（二）则不可以认为相交 。判断交点是否在线段上,预备知识(VI),为解决上述问题，我们引入点乘：,a .b = xa*xb + ya*yb = a b cos,a,b,c,当cross(a,b,c)=0时，如果 . 小于等于0，则 c点在ab上，否则c点在ab外,预备知识(V),设dot(a,b,c) 返回.的值。我们来看dot(a,b,c)值与c在ab上投影c的关系.,a,b,dot(a,b,c) = 0c在a上,基本问题举例(),1.位置 (左右)判断,例：zju1041 问题描述：在有n个点的面上有一个给定了半径和圆心坐标的半圆，半圆可以绕圆心转动但不可以平移，求半圆最多能包含多少点，边界上的点认为在圆内。,基本问题举例(),基本思路：,1.到圆心的距离大于半径的点直接排除。,2.以圆心和任意一点确定一 有向线段作为半径位置，分别计数该有向线段左边点的个数(nl)和右边点的个数(nr)。,3.重复步骤2直到所有点都被枚举 过。,4.枚举过程中出现的最大的nl或 nr就是所求的结果。,nl = nr = Max =,4,5,基本问题举例(),代码：,#include using 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 rx,ry; double r; while(cinrxryr ,cinn; for(i = 0 ;i xy; if(x-rx)*(x-rx)+(y-ry)*(y-ry)0) num_l+; if(dmax) max = num_l; if(num_rmax) max = num_r; coutmaxendl; return 0; ,基本问题举例（）,2.求交点（ZJU1460） 问题描述：用刀切1000*1000的方形蛋糕，问切割若干刀之后，蛋糕被分为多少块，假设： 蛋糕顶点坐标为(0,0)(0,1000)(1000,1000)(1000,0) 切割刀数不超过8 切割后每一块蛋糕的边长不小于1 切割线和蛋糕边界有两个交点,基本问题举例（）,基本思路 假设平面上已经被m条直线切割成了n块，那么再增加一条直线增加的块数等于增加的交点数加1。,基本问题举例（）,相关算法 根据已知两点坐标，求过这两点的直线解析方程： a*x+b*y+c = 0 (a = 0),line 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; ,基本问题举例（）,相关算法 判断两线段是否相交，如果相交则求出交点 相交用差积cross(a,b,c)*cross(a,b,d)0 &cross(c,d,a)*cross(c,d,b)0)判断（注意表示越界） 求交点,/ 求两条直线 l1(a1*x+b1*y+c1 = 0), l2(a2*x+b2*y+c2 = 0)的交点 void lineintersect(line l1,line l2,point ,基本问题举例（）,特殊情况 切割线和边界或者以前的切割线重合（排除） 重复交点（只计算1次） 在边界相交（不增加交点）,6=4+(1+1) not 7=4+(2+1),3=2+(0+1) not 4=2+(1+1),基本问题举例（）,代码（主程序）,int main(int argc, char *argv) /读入所有线段，并排除重复线段 int cutting_num=0; while(cin cutting_num) ,int main(int argc, char *argv) / int partion_num = line_on_edge(cuttings0)?1:2; for(int i=1;i new_cross_pts; for(int j=0;j0 ,基本问题举例(),3.求多边形的面积。 前面已经讲过，两向量的差积的几何意义是以这两个向量为邻边的平行四边形的有向面积，我们可以利用这一点来求简单多边形的面积。 所谓简单多边形就是任何不相邻的两条边都没有交点，包括凸多边形和凹多边形。,.,基本问题举例(),求下面多边形的面积，已知个顶点的坐标。,a,b,c,d,e,f,a,b,c,d,e,f,0,基本问题举例(),4.求凸包 定义：直观地讲，对于一个平面点集或者一个 多边形，它的凸包指的是包含它的最小凸 图形或最小凸区域。,基本问题举例(),Graham-Scan算法(了解Gift-Wrapping算法 ) 试探性凸包 我们尝试从p1(最低点，一定属于凸包)出发，沿着多边形顶点逆时针的顺序，试探性的增长凸包.显然，一个点如果属于凸包，那么它到达下一个点一定需要左转，否则，该点一定不属于凸包。,P1,P2,P4,P3,P6,P5,凸包顶点,基本问题举例(),算法总结：,2.该算法带有简单的回溯，因此宜用栈实现，栈中存储的是 到目前为止的“局部凸包”，如果当前边对于栈顶边右转，就 退栈。一直到“局部凸包”完整。,1. Graham-Scan需要一个序，如果输入是平面点集，首先需要对所有的点按极角排序。显然， “极角大小”比较用“左右手”关系比较(差积) 即：BCi的极角比BCj的极角大BCi在BCj左边。,基本问题举例(),3.伪代码： push(p1);push(p2); i=3; while i=n do if pi 在栈顶边pt-1pt左手方向 then push(pi) 并且i+； else pop();,4.复杂度分析 上述while语句中，每个点显然进栈一次，而最多出栈 一次，故时间复杂度为O(n).,附加问题(需要离散化问题),例：zju1128 问题描述：一些已知右下顶点和左上顶点坐标的矩形，这些矩形可能部分重叠，求它们所占的实际面积。例如：,附加问题(需要离散化问题),方案一、 把矩形映射到数组M 中，如果某矩形的位置为（x1，y1）（x2，y2）则Mij=1（其中x1=i=x2,y1=j=y2）。但是，如果坐标值离散程度很大或者非整型，此方案就不可行。,方案二、 判断任两个矩形是否相交，如果重叠，两面积相加，减去重叠部分。但重叠情况很多，算法不复杂但程序写起来很复杂，容易出错。,附加问题(需要离散化问题),方案三离散化,1、首先分离出所有的横坐标和纵坐 标分别按升序存入数组X 和Y 中. 2、 设数组XY . 对于每个矩形(x1,y1)(x2,y2) 确定i1,i2,j1,j2,使得, Xi1x1,Xi2y1,Yi2=y2 令XY i j = 1 (i从i1到i2，j从j1到j2) 3、统计面积： area+=XYij *(Xi-Xi-1) *(Yi Yi-1),附加问题(需要离散化问题),代码 #include using namespace std; double x200,y200,in1004; bool xy200200; double N=0.000001; int n_map; void input(); void solve(); double cacu();,附加问题(需要离散化问题),int main() while(cinn_map ,附加问题(需要离散化问题),void input() for(int i = 0,k=0 ; i ini0ini1ini2ini3; xk = ini0; yk = ini1; k+; xk = ini2; yk = ini3; k+; ,附加问题(需要离散化问题),vo