[工学]ACMlecture_05计算几何基础ppt课件

1、ACM程序设计程序设计杭州电子科技大学 刘春英今天，今天，他他 了吗？了吗？AC每周一星每周一星4：0705341007053410陈晟陈晟 第五讲第五讲计算几何初步计算几何初步(Computational Geometry Basic)第一单元第一单元线段属性线段属性思索：思索：1 1、传统的计算线段相交的方法是什么？、传统的计算线段相交的方法是什么？2 2、传统方法和本方法的区别是什么？、传统方法和本方法的区别是什么？特别提示：特别提示：n以上引见的线段的三个属性，是计以上引见的线段的三个属性，是计算几何的根底，在很多方面都有运算几何的根底，在很多方面都有运用，比如求凸

2、包等等，请务必掌握！用，比如求凸包等等，请务必掌握！第二单元第二单元多边形面积和重心多边形面积和重心根本问题根本问题1：n给定一个简单多边形，求其面积。给定一个简单多边形，求其面积。n输入：多边形顶点按逆时针顺输入：多边形顶点按逆时针顺序陈列序陈列n输出：面积输出：面积S S思索如以下图形：思索如以下图形：Any good idea?先看最简单的多边形先看最简单的多边形三角形三角形三角形的面积：三角形的面积：n在解析几何里， ABC的面积可以经过如下方法求得：n点坐标 = 边长 = 海伦公式 = 面积思索：此方法的缺陷：思索：此方法的缺陷：计算量大精度损失更好的方法？计算几何的方法：计算几何的

3、方法：n在计算几何里，我们知道，ABC的面积就是“向量AB和“向量AC两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。ABC成左手系，负面积ABC成右手系，正面积BCACBA大功告成：大功告成：nArea(A,B,C)= 1/2 * (AB) (AC)n = /2n特别留意：n 以上得到是有向面积有正负！ Xb X a Yb Y aXc X a Yc Y a凸多边形的三角形剖分凸多边形的三角形剖分n很自然地，我们会想到以 P1为扇面中心，衔接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：n A=sigma(Ai) (i=

4、1N-2)P1P2P3P4P5P6A1A2A3A4凹多边形的面积？凹多边形的面积？P1P4P3P2依然成立！依然成立！多边形面积公式：A=sigma(Ai) (i=1N-2)结论： “有向面积A比“面积S其实更本质！恣意点为扇心的三角形剖分：恣意点为扇心的三角形剖分：n我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？n比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。P0P1P2P6P5P4P3前面的三角剖分显然对于多边形内部前面的三角剖分显然对于多边形内部恣意一点都是适宜的！恣意一点都是适宜的！我们可以得到：A=sigma(Ai) i=1N 即：A=sigma

5、 /2 i=1N Xi X0 Yi Y0X(i+1) X0 Y(i+1) Y0能否把扇心移到多边形以外呢？能否把扇心移到多边形以外呢？P0P1P2P3P4既然内外都可以，为什么不设既然内外都可以，为什么不设P0为坐标原点呢？为坐标原点呢？OP1P2P3P4如今的公式？简化的公式：简化的公式：A=sigma /2 i=1N Xi YiX(i+1) Y(i+1)面积问题面积问题搞定！搞定！根本问题根本问题2：n给定一个简单多边形，求其重心。给定一个简单多边形，求其重心。n输入：多边形顶点按逆时针顺输入：多边形顶点按逆时针顺序陈列序陈列n输出：重心点输出：重心点C C从三角形的重心谈起：从三角形的重

6、心谈起：三角形的重心是： (x1+x2+x3) / 3，(y1+y2+y3) / 3可以推行否？Sigma(xi)/N , sigma(yi)/N (i=1N) ?看看一个特例：看看一个特例：.缘由：缘由：n错误的推行公式是“质点系重心公式，即假设以为多边形的质量仅分布在其顶点上，且均匀分布，那么这个公式是对的。n但是，如今多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的！Solution:n剖分成N个三角形，分别求出其重心和面积，这时可以想象，原来质量均匀分布在内部区域上，而如今质量仅仅分布在这N个重心点上等假变换，这时候就可以利用刚刚的质点系重心公式了。n不过，要略微改一改

7、，改成加权平均数，由于质量不是均匀分布的，每个质点代表其所在三角形，其质量就是该三角形的面积有向面积！，这就是权！公式：公式：nC=sigma(Ai * Ci) / A (i=1N)nCi=Centroid( O Pi Pi+1)n = (O + Pi +Pi+1 )/3nC=sigma(Pi +Pi+1)(Pi Pi+1) ) /(6A)第三单元第三单元凸包凸包( Convex Hull )( Convex Hull )凸包模板：凸包模板：/xiaoxia版#include #include #include typedef structdouble x;double y;POINT;POI

8、NT result102;/保管凸包上的点POINT a102;int n,top;double Distance(POINT p1,POINT p2)/两点间的间隔return sqrt(p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);double Multiply(POINT p1,POINT p2,POINT p3) /叉积 return (p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x); int Compare(const void *p1,const void *p2)POINT *p3,*p

9、4;double m; p3=(POINT *)p1; p4=(POINT *)p2; m=Multiply(a0,*p3,*p4) ;if(m0) return 1;else if(m=0&(Distance(a0,*p3)Distance(a0,*p4)return 1;else return -1;void Tubao() int i; result0.x=a0.x; result0.y=a0.y; result1.x=a1.x; result1.y=a1.y; result2.x=a2.x; result2.y=a2.y; top=2; for(i=3;i=n;i+) whil

10、e(Multiply(resulttop-1,resulttop,ai)=0)top-; resulttop+1.x=ai.x; resulttop+1.y=ai.y; top+; int main() int i,p; double px,py,len,temp; while(scanf(%d,&n)!=EOF,n) for(i=0;in;i+) scanf(%lf%lf,&ai.x,&ai.y); if(n=1) printf(0.00n); continue; else if(n=2) printf(%.2lfn,Distance(a0,a1); continue; py=-1; for(i=0;in;i+) if(py=-1 | ai.ypy) px=ai.x; py=ai.y; p=i; else if(ai.y=py & ai.xpx) px=ai.x; py=ai.y; p=i; /swap(a0,ap) temp=a0.x; a0.x=ap.x; ap.x=temp; temp=a0.y; a0.y=ap.y; ap.y=temp; qsort(&a1,n-1,sizeof(double)*2,Compare); an.x=a0.x; an.y=a0.y; Tubao(); len=0.0; for(i=0;itop;i+)