《ACM课件(lecture_05)计算几何基础》由会员分享，可在线阅读，更多相关《ACM课件(lecture_05)计算几何基础（72页珍藏版）》请在金锄头文库上搜索。
1、ACM程序设计杭州电子科技大学 刘春英 *1今天，你 了吗？ACDate2每周一星（4）：07053410陈晟 Date3第五讲计算几何初步 (Computational Geometry Basic)Date4第一单元线段属性Date5Date6Date7Date8Date9Date10Date11Date12Date13思考：1、传统的计算线段相交的方法是什么？2、传统方法和本方法的区别是什么？Date14特别提醒：n以上介绍的线段的三个属性，是计 算几何的基础，在很多方面都有应 用，比如求凸包等等，请务必掌握 ！Date15第二单元多边形面积和重心Date16基本问题（1）：n给定一个简
2、单多边形，求其面积 。n输入：多边形（顶点按逆时针顺 序排列）n输出：面积SDate17思考如下图形：Date18Any good idea?Date19先看最简单的多边形三角形Date20三角形的面积：n在解析几何里， ABC的面积可以通过 如下方法求得：n点坐标 = 边长 = 海伦公式 = 面积Date21思考：此方法的缺点：计算量大精度损失更好的方法？Date22计算几何的方法：n在计算几何里，我们知道，ABC的面积 就是“向量AB”和“向量AC”两个向量叉积 的绝对值的一半。其正负表示三角形顶 点是在右手系还是左手系。ABC成左手系，负面积ABC成右手系，正面积BCACBADate23
3、大功告成：nArea(A,B,C)= 1/2 * (AB) (AC)= /2特别注意：以上得到是有向面积（有正负）！ Xb X a Yb Y aXc X a Yc Y aDate24凸多边形的三角形剖分n很自然地，我们会想到以 P1为扇面中心 ，连接P1Pi就得到N-2个三角形，由于凸 性，保证这些三角形全在多边形内，那 么，这个凸多边形的有向面积：A=sigma(Ai) (i=1N-2)P1P2P3P4P5P6A1A2A3A4Date25凹多边形的面积？P1P4P3P2Date26依然成立！多边形面积公式：A=sigma(Ai) (i=1N-2)结论：“有向面积”A比“面积”S其实更本质！D
4、ate27任意点为扇心的三角形剖分：n我们能把多边形分成N-2个三角形，为什么不 能分成N个三角形呢？n比如，以多边形内部的一个点为扇心，就可以 把多边形剖分成 N个三角形。P0P1P2P6P5P4P3Date28前面的三角剖分显然对于多边形内 部任意一点都是合适的！我们可以得到： A=sigma(Ai) （ i=1N ）即：A=sigma /2（ i=1N ） Xi X0 Yi Y0X(i+1) X0 Y(i+1) Y0Date29能否把扇心移到多边形以外呢？P0P1P2P3P4Date30既然内外都可以，为什么不设 P0为坐标原点呢？OP1P2P3P4现在的公式？Date31简化的公式：
5、A=sigma /2（ i=1N ）Xi YiX(i+1) Y(i+1)面积问题 搞定！Date32基本问题（2）：n给定一个简单多边形，求其重心 。n输入：多边形（顶点按逆时针顺 序排列）n输出：重心点CDate33从三角形的重心谈起：三角形的重心是：(x1+x2+x3) / 3，(y1+y2+y3) / 3可以推广否？Sigma(xi)/N , sigma(yi)/N (i=1N) ?Date34看看一个特例： .Date35原因：n错误的推广公式是“质点系重心公式”，即 如果认为多边形的质量仅分布在其顶点 上，且均匀分布，则这个公式是对的。n但是，现在多边形的质量是均匀分布在 其内部区域
6、上的，也就是说，是与面积 有关的！Date36Solution:n剖分成N个三角形，分别求出其重心和面 积，这时可以想象，原来质量均匀分布 在内部区域上，而现在质量仅仅分布在 这N个重心点上（等假变换），这时候就 可以利用刚才的质点系重心公式了。n不过，要稍微改一改，改成加权平均数 ，因为质量不是均匀分布的，每个质点 代表其所在三角形，其质量就是该三角 形的面积（有向面积！），这就是 权！Date37公式：nC=sigma(Ai * Ci) / A (i=1N)nCi=Centroid( O Pi Pi+1)n = (O + Pi +Pi+1 )/3nC=sigma(Pi +Pi+1)(Pi
7、Pi+1) ) /(6A)Date38全部搞全部搞 定！定！Date39第三单元凸包( Convex Hull )Date40Date41Date42Date43Date44Date45Date46Date47Date48Date49Date50Date51Date52Date53Date54Date55Date56Date57Date58Date59Date60Date61Date62Date63Date64Date65Date66Date67凸包模板：/xiaoxia版 #include #include #include typedef struct double x; double y
8、; POINT;POINT 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 vo
9、id *p2) POINT *p3,*p4; double m;p3=(POINT *)p1; p4=(POINT *)p2; m=Multiply(a0,*p3,*p4) ; if(m0) return 1; else if(m=0 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+)while(Multiply(resulttop- 1,resultto
10、p,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“,in;i+)scanf(“%lf%lf“,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 py=
11、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(an.x=a0.x;an.y=a0.y;Tubao();len=0.0;for(i=0;itop;i+)len=len+Distance(resulti,resulti +1);printf(“%.2lfn“,len);return 0; Date68Any question?Date69课后作业： ACM ProgrammingExercise（5 ）_Geometry Date70下一讲：并查集Date71Welcome to HDOJ Thank You Date72
