《ACM课件lecture-计算几何基础.ppt》由会员分享，可在线阅读，更多相关《ACM课件lecture-计算几何基础.ppt（72页珍藏版）》请在装配图网上搜索。
1、ACM程序设计,杭州电子科技大学 刘春英 ,2020/9/6,2,今天，,你 了吗？,AC,2020/9/6,3,每周一星（4）：,07053410陈晟,2020/9/6,4,第五讲,计算几何初步 (Computational Geometry Basic),2020/9/6,5,第一单元,线段属性,2020/9/6,6,2020/9/6,7,2020/9/6,8,2020/9/6,9,2020/9/6,10,2020/9/6,11,2020/9/6,12,2020/9/6,13,2020/9/6,14,思考：,1、传统的计算线段相交的方法是什么？ 2、传统方法和本方法的区别是什么？,2020
2、/9/6,15,特别提醒：,以上介绍的线段的三个属性，是计算几何的基础，在很多方面都有应用，比如求凸包等等，请务必掌握！,2020/9/6,16,第二单元,多边形面积和重心,2020/9/6,17,基本问题（1）：,给定一个简单多边形，求其面积。 输入：多边形（顶点按逆时针顺序排列） 输出：面积S,2020/9/6,18,思考如下图形：,2020/9/6,19,Any good idea?,2020/9/6,20,先看最简单的多边形三角形,2020/9/6,21,三角形的面积：,在解析几何里， ABC的面积可以通过如下方法求得： 点坐标 = 边长 = 海伦公式 = 面积,2020/9/6,22
3、,思考：此方法的缺点：,计算量大,精度损失,更好的方法？,2020/9/6,23,计算几何的方法：,在计算几何里，我们知道，ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。,ABC成左手系，负面积,ABC成右手系，正面积,2020/9/6,24,大功告成：,Area(A,B,C)= 1/2 * (AB) (AC) = /2 特别注意： 以上得到是有向面积（有正负）！,Xb X a Yb Y a,Xc X a Yc Y a,2020/9/6,25,凸多边形的三角形剖分,很自然地，我们会想到以 P1为扇面中心，连接P1Pi就得到N-2
4、个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积： A=sigma(Ai) (i=1N-2),2020/9/6,26,凹多边形的面积？,2020/9/6,27,依然成立！,多边形面积公式：A=sigma(Ai) (i=1N-2),结论： “有向面积”A比“面积”S其实更本质！,2020/9/6,28,任意点为扇心的三角形剖分：,我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？ 比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。,P0,P1,P2,P6,P5,P4,P3,2020/9/6,29,前面的三角剖分显然对于多边形内部任意一点都
5、是合适的！,我们可以得到： A=sigma(Ai) （ i=1N ） 即：A=sigma /2 （ i=1N ）,Xi X0 Yi Y0,X(i+1) X0 Y(i+1) Y0,2020/9/6,30,能否把扇心移到多边形以外呢？,2020/9/6,31,既然内外都可以，为什么不设P0为坐标原点呢？,现在的公式？,2020/9/6,32,简化的公式：,A=sigma /2 （ i=1N ）,Xi Yi,X(i+1) Y(i+1),面积问题搞定！,2020/9/6,33,基本问题（2）：,给定一个简单多边形，求其重心。 输入：多边形（顶点按逆时针顺序排列） 输出：重心点C,2020/9/6,34
6、,从三角形的重心谈起：,三角形的重心是： (x1+x2+x3) / 3，(y1+y2+y3) / 3,可以推广否？,Sigma(xi)/N , sigma(yi)/N (i=1N) ?,2020/9/6,35,看看一个特例：,2020/9/6,36,原因：,错误的推广公式是“质点系重心公式”，即如果认为多边形的质量仅分布在其顶点上，且均匀分布，则这个公式是对的。 但是，现在多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的！,2020/9/6,37,Solution:,剖分成N个三角形，分别求出其重心和面积，这时可以想象，原来质量均匀分布在内部区域上，而现在质量仅仅分布在这N个重
7、心点上（等假变换），这时候就可以利用刚才的质点系重心公式了。 不过，要稍微改一改，改成加权平均数，因为质量不是均匀分布的，每个质点代表其所在三角形，其质量就是该三角形的面积（有向面积！），这就是权！,2020/9/6,38,公式：,C=sigma(Ai * Ci) / A (i=1N) Ci=Centroid( O Pi Pi+1) = (O + Pi +Pi+1 )/3 C=sigma(Pi +Pi+1)(Pi Pi+1) ) /(6A),全部搞定！,2020/9/6,40,第三单元,凸包( Convex Hull ),2020/9/6,41,2020/9/6,42,2020/9/6,43,
8、2020/9/6,44,2020/9/6,45,2020/9/6,46,2020/9/6,47,2020/9/6,48,2020/9/6,49,2020/9/6,50,2020/9/6,51,2020/9/6,52,2020/9/6,53,2020/9/6,54,2020/9/6,55,2020/9/6,56,2020/9/6,57,2020/9/6,58,2020/9/6,59,2020/9/6,60,2020/9/6,61,2020/9/6,62,2020/9/6,63,2020/9/6,64,2020/9/6,65,2020/9/6,66,2020/9/6,67,2020/9/6,68,
9、凸包模板：,/xiaoxia版 #include #include #include typedef struct double 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
10、)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x); int Compare(const void *p1,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 ,Any question?,2020/9/6,70,课后作业：,ACM ProgrammingExercise（5）_Geometry,2020/9/6,71,下一讲：,并查集,2020/9/6,72,Welcome to HDOJ,Thank You ,
ACM课件lecture-计算几何基础.ppt
