ACM算法计算几何基础.ppt

《ACM算法计算几何基础.ppt》由会员分享，可在线阅读，更多相关《ACM算法计算几何基础.ppt（71页珍藏版）》请在三一办公上搜索。

1、2023/7/5,1,ACM 程序设计,计算机学院 刘春英,2023/7/5,2,今天，,你 了吗？,AC,2023/7/5,3,每周一星（6）：,老 菜(donhau),2023/7/5,4,第七讲,计算几何初步(Computational Geometry Basic),2023/7/5,5,第一单元,线 段 属 性,2023/7/5,6,2023/7/5,7,2023/7/5,8,2023/7/5,9,2023/7/5,10,2023/7/5,11,2023/7/5,12,2023/7/5,13,2023/7/5,14,思考：,1、传统的计算线段相交的方法是什么？2、传统方法和本方法的区

2、别是什么？,2023/7/5,15,特别提醒：,以上介绍的线段的三个属性，是计算几何的基础，在很多方面都有应用，比如求凸包等等，请务必掌握！,2023/7/5,16,第二单元,多边形面积 和重心,2023/7/5,17,基本问题（1）：,给定一个简单多边形，求其面积。输入：多边形（顶点按逆时针顺序排列）输出：面积S,2023/7/5,18,思考如下图形：,2023/7/5,19,Any good idea?,2023/7/5,20,先讨论最简单的多边形三角形,2023/7/5,21,三角形的面积：,在解析几何里，ABC的面积可以通过如下方法求得：点坐标=边长=海伦公式=面积,2023/7/5,

3、22,思考：此方法的缺点：,计算量大,精度损失,更好的方法？,2023/7/5,23,计算几何的方法：,在计算几何里，我们知道，ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。,ABC成左手系，负面积,ABC成右手系，正面积,2023/7/5,24,大功告成：,Area(A,B,C)=1/2*(AB)(AC)=/2特别注意：以上得到是有向面积（有正负）！,Xb X a Yb Y a,Xc X a Yc Y a,2023/7/5,25,凸多边形的三角形剖分,很自然地，我们会想到以 P1为扇面中心，连接P1Pi就得到N-2个三角形，由

4、于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：A=sigma(Ai)(i=1N-2),2023/7/5,26,凹多边形的面积？,2023/7/5,27,依然成立！,多边形面积公式：A=sigma(Ai)(i=1N-2),结论：“有向面积”A比“面积”S其实更本质！,2023/7/5,28,任意点为扇心的三角形剖分：,我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。,P0,P1,P2,P6,P5,P4,P3,2023/7/5,29,前面的三角剖分显然对于多边形内部任意一点都是合适的！,我们可以得

5、到：A=sigma(Ai)（i=1N）即：A=sigma/2（i=1N）,Xi X0 Yi Y0,X(i+1)X0 Y(i+1)Y0,2023/7/5,30,能不能把扇心移到多边形以外呢？,2023/7/5,31,既然内外都可以，为什么不设P0为坐标原点呢？,现在的公式？,2023/7/5,32,简化的公式：,A=sigma/2（i=1N）,Xi Yi,X(i+1)Y(i+1),面积问题搞定！,2023/7/5,33,基本问题（2）：,给定一个简单多边形，求其重心。输入：多边形（顶点按逆时针顺序排列）输出：重心点C,2023/7/5,34,从三角形的重心谈起：,三角形的重心是：(x1+x2+x

6、3)/3，(y1+y2+y3)/3,可以推广否？,Sigma(xi)/N,sigma(yi)/N(i=1N)?,2023/7/5,35,看看一个特例：,2023/7/5,36,原因：,错误的推广公式是“质点系重心公式”，即如果认为多边形的质量仅分布在其顶点上，且均匀分布，则这个公式是对的。但是，现在多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的！,2023/7/5,37,Solution:,剖分成N个三角形，分别求出其重心和面积，这时可以想象，原来质量均匀分布在内部区域上，而现在质量仅仅分布在这N个重心点上（等假变换），这时候就可以利用刚才的质点系重心公式了。不过，要稍微改一

7、改，改成加权平均数，因为质量不是均匀分布的，每个质点代表其所在三角形，其质量就是该三角形的面积（有向面积！），这就是权！,2023/7/5,38,公式：,C=sigma(Ai*Ci)/A(i=1N)Ci=Centroid(O Pi Pi+1)=(O+Pi+Pi+1)C=sigma(Pi+Pi+1)(Pi Pi+1)/(6A),2023/7/5,39,全部搞定！,2023/7/5,40,第三单元,凸包(Convex Hull),2023/7/5,41,2023/7/5,42,2023/7/5,43,2023/7/5,44,2023/7/5,45,2023/7/5,46,2023/7/5,47,2

8、023/7/5,48,2023/7/5,49,2023/7/5,50,2023/7/5,51,2023/7/5,52,2023/7/5,53,2023/7/5,54,2023/7/5,55,2023/7/5,56,2023/7/5,57,2023/7/5,58,2023/7/5,59,2023/7/5,60,2023/7/5,61,2023/7/5,62,2023/7/5,63,2023/7/5,64,2023/7/5,65,2023/7/5,66,2023/7/5,67,2023/7/5,68,凸包模板：,/xiaoxia版#include#include#include typedef s

9、tructdouble x;double y;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

10、,const void*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,2023/7/5,69,Any Question?,2023/7/5,70,相关练习题：,1086 You can Solve a Geometry Problem too1115 Lifting the Stone 2036 改革春风吹满地 1348、1392Zoj:1450、1541,2023/7/5,71,See you next week.,Thank you!,