ACMlecture-05计算几何基础课件

2023/10/61今天，你了吗？AC第1页/共71页2023/10/61今天，你了吗？AC第1页/2023/10/62每周一星（4）：07053410陈晟

第2页/共71页2023/10/62每周一星（4）：07053410陈晟第2023/10/63第五讲计算几何初步(ComputationalGeometryBasic)第3页/共71页2023/10/63第五讲计算几何初步第3页/共71页2023/10/64第一单元线段属性第4页/共71页2023/10/64第一单元线段属性第4页/共71页2023/10/65第5页/共71页2023/10/65第5页/共71页2023/10/66第6页/共71页2023/10/66第6页/共71页2023/10/67第7页/共71页2023/10/67第7页/共71页2023/10/68第8页/共71页2023/10/68第8页/共71页2023/10/69第9页/共71页2023/10/69第9页/共71页2023/10/610第10页/共71页2023/10/610第10页/共71页2023/10/611第11页/共71页2023/10/611第11页/共71页2023/10/612第12页/共71页2023/10/612第12页/共71页2023/10/613思考：1、传统的计算线段相交的方法是什么？2、传统方法和本方法的区别是什么？第13页/共71页2023/10/613思考：1、传统的计算线段相交的方法是什2023/10/614特别提醒：以上介绍的线段的三个属性，是计算几何的基础，在很多方面都有应用，比如求凸包等等，请务必掌握！第14页/共71页2023/10/614特别提醒：以上介绍的线段的三个属性，是2023/10/615第二单元多边形面积和重心第15页/共71页2023/10/615第二单元多边形面积和重心第15页/共72023/10/616基本问题（1）：给定一个简单多边形，求其面积。输入：多边形（顶点按逆时针顺序排列）输出：面积S第16页/共71页2023/10/616基本问题（1）：给定一个简单多边形，求2023/10/617思考如下图形：第17页/共71页2023/10/617思考如下图形：第17页/共71页2023/10/618Anygoodidea?第18页/共71页2023/10/618Anygoodidea?第18页/2023/10/619先看最简单的多边形——三角形第19页/共71页2023/10/619先看最简单的多边形——三角形第19页/2023/10/620三角形的面积：在解析几何里，△ABC的面积可以通过如下方法求得：点坐标=>边长=>海伦公式=>面积第20页/共71页2023/10/620三角形的面积：在解析几何里，△ABC2023/10/621思考：此方法的缺点：计算量大精度损失更好的方法？第21页/共71页2023/10/621思考：此方法的缺点：计算量大精度损失更2023/10/622计算几何的方法：在计算几何里，我们知道，△ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。ABC成左手系，负面积ABC成右手系，正面积BCACBA第22页/共71页2023/10/622计算几何的方法：在计算几何里，我们知道2023/10/623大功告成：

Area(A,B,C)=1/2*(↑AB)×(↑AC)

=∣

∣/2特别注意：以上得到是有向面积（有正负）！Xb–XaYb–YaXc–XaYc–Ya第23页/共71页2023/10/623大功告成： Area(A,B,C)=2023/10/624凸多边形的三角形剖分很自然地，我们会想到以P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：

A=sigma(Ai)(i=1…N-2)P1P2P3P4P5P6A1A2A3A4第24页/共71页2023/10/624凸多边形的三角形剖分很自然地，我们会想2023/10/625凹多边形的面积？P1P4P3P2第25页/共71页2023/10/625凹多边形的面积？P1P4P3P2第252023/10/626依然成立！！！多边形面积公式：A=sigma(Ai)(i=1…N-2)结论：“有向面积”A比“面积”S其实更本质！第26页/共71页2023/10/626依然成立！！！多边形面积公式：A=si2023/10/627任意点为扇心的三角形剖分：我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？比如，以多边形内部的一个点为扇心，就可以把多边形剖分成N个三角形。P0P1P2P6P5P4P3第27页/共71页2023/10/627任意点为扇心的三角形剖分：我们能把多边2023/10/628前面的三角剖分显然对于多边形内部任意一点都是合适的！我们可以得到：A=sigma(Ai)（i=1…N

）即：A=sigma∣

∣/2

（i=1…N

）Xi–X0Yi–Y0X(i+1)–X0Y(i+1)–Y0第28页/共71页2023/10/628前面的三角剖分显然对于多边形内部任意一2023/10/629能否把扇心移到多边形以外呢？P0P1P2P3P4第29页/共71页2023/10/629能否把扇心移到多边形以外呢？P0P1P2023/10/630既然内外都可以，为什么不设P0为坐标原点呢？OP1P2P3P4现在的公式？第30页/共71页2023/10/630既然内外都可以，为什么不设P0为坐标原2023/10/631简化的公式：A=sigma∣

∣/2（i=1…N

）XiYiX(i+1)Y(i+1)面积问题搞定！第31页/共71页2023/10/631简化的公式：A=sigma∣∣2023/10/632基本问题（2）：给定一个简单多边形，求其重心。输入：多边形（顶点按逆时针顺序排列）输出：重心点C第32页/共71页2023/10/632基本问题（2）：给定一个简单多边形，求2023/10/633从三角形的重心谈起：三角形的重心是：

(x1+x2+x3)/3，(y1+y2+y3)/3可以推广否？Sigma(xi)/N,sigma(yi)/N(i=1…N)???第33页/共71页2023/10/633从三角形的重心谈起：三角形的重心是：可2023/10/634看看一个特例：.第34页/共71页2023/10/634看看一个特例：.第34页/共71页2023/10/635原因：错误的推广公式是“质点系重心公式”，即如果认为多边形的质量仅分布在其顶点上，且均匀分布，则这个公式是对的。但是，现在多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的！第35页/共71页2023/10/635原因：错误的推广公式是“质点系重心公式2023/10/636Solution:剖分成N个三角形，分别求出其重心和面积，这时可以想象，原来质量均匀分布在内部区域上，而现在质量仅仅分布在这N个重心点上（等假变换），这时候就可以利用刚才的质点系重心公式了。不过，要稍微改一改，改成加权平均数，因为质量不是均匀分布的，每个质点代表其所在三角形，其质量就是该三角形的面积（有向面积！），——这就是权！第36页/共71页2023/10/636Solution:剖分成N个三角形，分2023/10/637公式：C=sigma(Ai*Ci)/A(i=1…N)Ci=Centroid(△OPiPi+1)=

(O+↑Pi+↑Pi+1)/3C=sigma((↑Pi+↑Pi+1)(↑Pi×↑Pi+1))/(6A)第37页/共71页2023/10/637公式：C=sigma(Ai*Ci)全部搞定！第38页/共71页全部搞定！第38页/共71页2023/10/639第三单元凸包(ConvexHull)第39页/共71页2023/10/639第三单元凸包(ConvexHull2023/10/640第40页/共71页2023/10/640第40页/共71页2023/10/641第41页/共71页2023/10/641第41页/共71页2023/10/642第42页/共71页2023/10/642第42页/共71页2023/10/643第43页/共71页2023/10/643第43页/共71页2023/10/644第44页/共71页2023/10/644第44页/共71页2023/10/645第45页/共71页2023/10/645第45页/共71页2023/10/646第46页/共71页2023/10/646第46页/共71页2023/10/647第47页/共71页2023/10/647第47页/共71页2023/10/648第48页/共71页2023/10/648第48页/共71页2023/10/649第49页/共71页2023/10/649第49页/共71页2023/10/650第50页/共71页2023/10/650第50页/共71页2023/10/651第51页/共71页2023/10/651第51页/共71页2023/10/652第52页/共71页2023/10/652第52页/共71页2023/10/653第53页/共71页2023/10/653第53页/共71页2023/10/654第54页/共71页2023/10/654第54页/共71页2023/10/655第55页/共71页2023/10/655第55页/共71页2023/10/656第56页/共71页2023/10/656第56页/共71页2023/10/657第57页/共71页2023/10/657第57页/共71页2023/10/658第58页/共71页2023/10/658第58页/共71页2023/10/659第59页/共71页2023/10/659第59页/共71页2023/10/660第60页/共71页2023/10/660第60页/共71页2023/10/661第61页/共71页2023/10/661第61页/共71页2023/10/662第62页/共71页2023/10/662第62页/共71页2023/10/663第63页/共71页2023/10/663第63页/共71页2023/10/664第64页/共71页2023/10/664第64页/共71页2023/10/665第65页/共71页2023/10/665第65页/共71页2023/10/666第66页/共71页2023/10/666第66页/共71页2023/10/667凸包模板：//xiaoxia版#include<stdio.h>#include<math.h>#include<stdlib.h>typedefstruct{ doublex; doubley;}POINT;POINTresult[102]; //保存凸包上的点POINTa[102]; intn,top;doubleDistance(POINTp1,POINTp2) //两点间的距离{ returnsqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));}doubleMultiply(POINTp1,POINTp2,POINTp3)//叉积{ return((p2.x-p1.x)*(p3.y-p1.y)-(p2.y-p1.y)*(p3.x-p1.x));}intCompare(constvoid*p1,constvoid*p2){ POINT*p3,*p4; doublem;p3=(POINT*)p1;p4=(POINT*)p2; m=Multiply(a[0],*p3,*p4); if(m<0)return1; elseif(m==0&&(Distance(a[0],*p3)<Distance(a[0],*p4))) return1; elsereturn-1;}voidTubao(){inti;result[0].x=a[0].x;result[0].y=a[0].y;result[1].x=a[1].x;result[1].y=a[1].y;result[2].x=a[2].x;result[2].y=a[2].y;top=2;for(i=3;i<=n;i++){while(Multiply(result[top-1],result[top],a[i])<=0) top--;result[top+1].x=a[i].x;result[top+1].y=a[i].y;top++;}}intmain(){inti,p;doublepx,py,len,temp;while(scanf("%d",&n)!=EOF,n){for(i=0;i<n;i++)scanf("%lf%lf",&a[i].x,&a[i].y);if(n==1){printf("0.00\n");continue;}elseif(n==2){printf("%.2lf\n",Distance(a[0],a[1]));continue;}py=-1;for(i=0;i<n;i++) {if(py==-1||a[i].y<py){px=a[i].x;py=a[i].y; p=i;}elseif(a[i].y==py&&a[i].x<px){px=a[i].x;