ACMlecture-05计算几何基础课件

2024/6/151今天，今天，你你 了吗？了吗？AC第1页/共71页2023/8/91今天，你 了吗？AC第1页/共2024/6/152每周一星（每周一星（4）：）：0705341007053410陈晟陈晟 第2页/共71页2023/8/92每周一星（4）：07053410陈晟 第22024/6/153第五讲第五讲计算几何初步计算几何初步(Computational Geometry Basic)第3页/共71页2023/8/93第五讲计算几何初步第3页/共71页2024/6/154第一单元第一单元线段属性线段属性第4页/共71页2023/8/94第一单元线段属性第4页/共71页2024/6/155第5页/共71页2023/8/95第5页/共71页2024/6/156第6页/共71页2023/8/96第6页/共71页2024/6/157第7页/共71页2023/8/97第7页/共71页2024/6/158第8页/共71页2023/8/98第8页/共71页2024/6/159第9页/共71页2023/8/99第9页/共71页2024/6/1510第10页/共71页2023/8/910第10页/共71页2024/6/1511第11页/共71页2023/8/911第11页/共71页2024/6/1512第12页/共71页2023/8/912第12页/共71页2024/6/1513思考：思考：1 1、传统的计算线段相交的方法是什么？、传统的计算线段相交的方法是什么？2 2、传统方法和本方法的区别是什么？、传统方法和本方法的区别是什么？第13页/共71页2023/8/913思考：1、传统的计算线段相交的方法是什么2024/6/1514特别提醒：特别提醒：n以上介绍的线段的三个属性，是计以上介绍的线段的三个属性，是计算几何的基础，在很多方面都有应算几何的基础，在很多方面都有应用，比如求凸包等等，请务必掌握！用，比如求凸包等等，请务必掌握！第14页/共71页2023/8/914特别提醒：以上介绍的线段的三个属性，是计2024/6/1515第二单元第二单元多边形面积和重心多边形面积和重心第15页/共71页2023/8/915第二单元多边形面积和重心第15页/共712024/6/1516基本问题（基本问题（1）：）：n给定一个简单多边形，求其面积。给定一个简单多边形，求其面积。n输入输入：多边形（顶点按逆时针顺：多边形（顶点按逆时针顺序排列）序排列）n输出输出：面积：面积S S第16页/共71页2023/8/916基本问题（1）：给定一个简单多边形，求其2024/6/1517思考如下图形：思考如下图形：第17页/共71页2023/8/917思考如下图形：第17页/共71页2024/6/1518Any good idea?第18页/共71页2023/8/918Any good idea?第18页/共2024/6/1519先看最简单的多边形先看最简单的多边形三角形三角形第19页/共71页2023/8/919先看最简单的多边形三角形第19页/共2024/6/1520三角形的面积：三角形的面积：n在解析几何里，ABC的面积可以通过如下方法求得：n点坐标=边长 =海伦公式=面积第20页/共71页2023/8/920三角形的面积：在解析几何里，ABC的2024/6/1521思考：此方法的缺点：思考：此方法的缺点：计算量大精度损失更好的方法？第21页/共71页2023/8/921思考：此方法的缺点：计算量大精度损失更好2024/6/1522计算几何的方法：计算几何的方法：n在计算几何里，我们知道，ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。ABC成左手系，负面积ABC成右手系，正面积BCACBA第22页/共71页2023/8/922计算几何的方法：在计算几何里，我们知道，2024/6/1523大功告成：大功告成：nArea(A,B,C)=1/2*(AB)(AC)=/2特别注意：以上得到是有向面积（有正负）有向面积（有正负）！Xb X a Yb Y aXc X a Yc Y a第23页/共71页2023/8/923大功告成：Area(A,B,C)=12024/6/1524凸多边形的三角形剖分凸多边形的三角形剖分n很自然地，我们会想到以 P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：A=sigma(Ai)(i=1N-2)P1P2P3P4P5P6A1A2A3A4第24页/共71页2023/8/924凸多边形的三角形剖分很自然地，我们会想到2024/6/1525凹多边形的面积？凹多边形的面积？P1P4P3P2第25页/共71页2023/8/925凹多边形的面积？P1P4P3P2第25页2024/6/1526依然成立！依然成立！多边形面积公式：A=sigma(Ai)(i=1N-2)结论：“有向面积”A比“面积”S其实更本质本质！第26页/共71页2023/8/926依然成立！多边形面积公式：A=sig2024/6/1527任意点为扇心的三角形剖分任意点为扇心的三角形剖分：n我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？n比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。P0P1P2P6P5P4P3第27页/共71页2023/8/927任意点为扇心的三角形剖分：我们能把多边形2024/6/1528前面的三角剖分显然对于多边形内部前面的三角剖分显然对于多边形内部任意一点都是合适的！任意一点都是合适的！我们可以得到：A=sigma(Ai)（i=1N）即：A=sigma /2 （i=1N）Xi X0 Yi Y0X(i+1)X0 Y(i+1)Y0第28页/共71页2023/8/928前面的三角剖分显然对于多边形内部任意一点2024/6/1529能否把扇心移到多边形以外呢？能否把扇心移到多边形以外呢？P0P1P2P3P4第29页/共71页2023/8/929能否把扇心移到多边形以外呢？P0P1P22024/6/1530既然内外都可以，为什么不设既然内外都可以，为什么不设P0为坐标原点呢？为坐标原点呢？OP1P2P3P4现在的公式？第30页/共71页2023/8/930既然内外都可以，为什么不设P0为坐标原点2024/6/1531简化的公式：简化的公式：A=sigma /2（i=1N）Xi YiX(i+1)Y(i+1)面积问题面积问题搞定！搞定！第31页/共71页2023/8/931简化的公式：A=sigma /2024/6/1532基本问题（基本问题（2）：）：n给定一个简单多边形，求其重心。给定一个简单多边形，求其重心。n输入输入：多边形（顶点按逆时针顺：多边形（顶点按逆时针顺序排列）序排列）n输出输出：重心点：重心点C C第32页/共71页2023/8/932基本问题（2）：给定一个简单多边形，求其2024/6/1533从三角形的重心谈起：从三角形的重心谈起：三角形的重心是：(x1+x2+x3)/3，(y1+y2+y3)/3可以推广否？Sigma(xi)/N,sigma(yi)/N (i=1N)?第33页/共71页2023/8/933从三角形的重心谈起：三角形的重心是：可以2024/6/1534看看一个特例：看看一个特例：.第34页/共71页2023/8/934看看一个特例：.第34页/共71页2024/6/1535原因：原因：n错误的推广公式是“质点系重心公式”，即如果认为多边形的质量仅分布在其顶点上，且均匀分布，则这个公式是对的。n但是，现在多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的！第35页/共71页2023/8/935原因：错误的推广公式是“质点系重心公式”2024/6/1536Solution:n剖分成N个三角形，分别求出其重心和面积，这时可以想象，原来质量均匀分布在内部区域上，而现在质量仅仅分布在这N个重心点上（等假变换），这时候就可以利用刚才的质点系重心公式了。n不过，要稍微改一改，改成加权平均加权平均数，因为质量不是均匀分布的，每个质点代表其所在三角形，其质量就是该三角形的面积（有向面积有向面积！），这就是权！第36页/共71页2023/8/936Solution:剖分成N个三角形，分别2024/6/1537公式：公式：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)第37页/共71页2023/8/937公式：C=sigma(Ai*Ci)全部搞全部搞定！定！第38页/共71页全部搞定！第38页/共71页2024/6/1539第三单元第三单元凸包凸包(Convex Hull)(Convex Hull)第39页/共71页2023/8/939第三单元凸包(Convex Hull 2024/6/1540第40页/共71页2023/8/940第40页/共71页2024/6/1541第41页/共71页2023/8/941第41页/共71页2024/6/1542第42页/共71页2023/8/942第42页/共71页2024/6/1543第43页/共71页2023/8/943第43页/共71页2024/6/1544第44页/共71页2023/8/944第44页/共71页2024/6/1545第45页/共71页2023/8/945第45页/共71页2024/6/1546第46页/共71页2023/8/946第46页/共71页2024/6/1547第47页/共71页2023/8/947第47页/共71页2024/6/1548第48页/共71页2023/8/948第48页/共71页2024/6/1549第49页/共71页2023/8/949第49页/共71页2024/6/1550第50页/共71页2023/8/950第50页/共71页2024/6/1551第51页/共71页2023/8/951第51页/共71页2024/6/1552第52页/共71页2023/8/952第52页/共71页2024/6/1553第53页/共71页2023/8/953第53页/共71页2024/6/1554第54页/共71页2023/8/954第54页/共71页2024/6/1555第55页/共71页2023/8/955第55页/共71页2024/6/1556第56页/共71页2023/8/956第56页/共71页2024/6/1557第57页/共71页2023/8/957第57页/共71页2024/6/1558第58页/共71页2023/8/958第58页/共71页2024/6/1559第59页/共71页2023/8/959第59页/共71页2024/6/1560第60页/共71页2023/8/960第60页/共71页2024/6/1561第61页/共71页2023/8/961第61页/共71页2024/6/1562第62页/共71页2023/8/962第62页/共71页2024/6/1563第63页/共71页2023/8/963第63页/共71页2024/6/1564第64页/共71页2023/8/964第64页/共71页2024/6/1565第65页/共71页2023/8/965第65页/共71页2024/6/1566第66页/共71页2023/8/966第66页/共71页2024/6/1567凸包模板：凸包模板：/xiaoxia版#include#include#include typedef structdouble 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,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&(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+)while(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+)len=len+Distance(resulti,resulti+1);printf(%.2lfn,len);return 0;第67页/共71页2023/8/967凸包模板：/xiaoxia版第67页/Any question?第68页/共71页Any question?第68页/共71页2024/6/1569课后作业：课后作业：ACM ProgrammingExercise（5）_Geometry 第69页/共71页2023/8/969课后作业：ACM Programmi2024/6/1570下一讲：下一讲：并查集并查集第70页/共71页2023/8/970下一讲：并查集第70页/共71页2024/6/1571Welcome to HDOJThank You 第71页/共71页2023/8/971Welcome to HDOJThank