今天， AC 你 了吗？ 2018/11/21
(Computational Geometry Basic) 第六讲 计算几何初步 (Computational Geometry Basic) 2018/11/21
第一单元 线 段 属 性 2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
思考： 1、传统的判断线段相交的方法是什么？ 2、传统方法和本方法的区别是什么？ 2018/11/21
特别提醒： 以上介绍的线段的三个属性，是计算几何的基础，在很多方面都有应用，比如求凸包等等，请务必掌握！ 2018/11/21
第二单元 多边形面积 和重心 2018/11/21
基本问题（1）： 给定一个简单多边形，求其面积。 输入：多边形（顶点按逆时针顺序排列） 输出：面积S 2018/11/21
思考如下图形： 2018/11/21
Any good idea? 2018/11/21
先讨论最简单的多边形——三角形 2018/11/21
三角形的面积： 在解析几何里， △ABC的面积可以通过如下方法求得： 点坐标 => 边长 => 海伦公式 => 面积 点坐标 => 边长 => 海伦公式 => 面积 2018/11/21
思考：此方法的缺点： 计算量大 精度损失 更好的方法？ 2018/11/21
计算几何的方法： 在计算几何里，我们知道，△ABC的面积就是“向量AB”和“向量AC”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。 B C A C B A ABC成左手系，负面积 ABC成右手系，正面积 2018/11/21
大功告成： Area(A,B,C)= 1/2 * (↑AB) × (↑AC) =∣ ∣/2 特别注意： 以上得到是有向面积（有正负）！ =∣ ∣/2 特别注意： 以上得到是有向面积（有正负）！ Xb – X a Yb –Y a Xc – X a Yc –Y a 2018/11/21
凸多边形的三角形剖分 很自然地，我们会想到以 P1为扇面中心，连接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积： A=sigma(Ai) (i=1…N-2) P1 P2 P3 P4 P5 P6 A1 A2 A3 A4 2018/11/21
凹多边形的面积？ P1 P4 P3 P2 2018/11/21
依然成立！！！ 多边形面积公式：A=sigma(Ai) (i=1…N-2) 结论： “有向面积”A比“面积”S其实更本质！ 2018/11/21
任意点为扇心的三角形剖分： 我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？ P3 P2 P4 P0 P1 P5 P6 2018/11/21
前面的三角剖分显然对于多边形内部任意一点都是合适的！ 我们可以得到： A=sigma(Ai) （ i=1…N ） 即：A= sigma∣ ∣/2 （ i=1…N ） Xi – X0 Yi –Y0 X(i+1) – X0 Y(i+1) –Y0 2018/11/21
能不能把扇心移到多边形以外呢？ P0 P1 P2 P3 P4 2018/11/21
既然内外都可以，为什么不设P0为坐标原点呢？ O P1 P2 P3 P4 现在的公式？ 2018/11/21
简化的公式： 面积问题搞定！ A=sigma∣ ∣/2 （ i=1…N ） Xi Yi X(i+1) Y(i+1) 2018/11/21
基本问题（2）： 给定一个简单多边形，求其重心。 输入：多边形（顶点按逆时针顺序排列） 输出：重心点C 2018/11/21
从三角形的重心谈起： 三角形的重心是： (x1+x2+x3) / 3，(y1+y2+y3) / 3 可以推广否？ Sigma(xi)/N , sigma(yi)/N (i=1…N) ??? 2018/11/21
看看一个特例： . 2018/11/21
原因： 错误的推广公式是“质点系重心公式”，即如果认为多边形的质量仅分布在其顶点上，且均匀分布，则这个公式是对的。 但是，现在多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的！ 2018/11/21
Solution: 剖分成N个三角形，分别求出其重心和面积，这时可以想象，原来质量均匀分布在内部区域上，而现在质量仅仅分布在这N个重心点上（等假变换），这时候就可以利用刚才的质点系重心公式了。 不过，要稍微改一改，改成加权平均数，因为质量不是均匀分布的，每个质点代表其所在三角形，其质量就是该三角形的面积（有向面积！），——这就是权！ 2018/11/21
公式： C=sigma(Ai * Ci) / A (i=1…N) Ci=Centroid(△ O Pi Pi+1) C=sigma((↑Pi +↑Pi+1)(↑Pi ×↑Pi+1) ) /(6A) 2018/11/21
全部搞定！ 2018/11/21
第三单元 凸包( Convex Hull ) 2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
2018/11/21
凸包模板： //xiaoxia版 #include <stdio.h> #include <math.h> #include <stdlib.h> typedef struct { double x; double y; }POINT; POINT result[102]; //保存凸包上的点 POINT a[102]; 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(a[0],*p3,*p4) ; if(m<0) return 1; else if(m==0&&(Distance(a[0],*p3)<Distance(a[0],*p4))) return 1; else return -1; void Tubao() int i; 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++; int main() int i,p; double px,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; else if(n==2) printf("%.2lf\n",Distance(a[0],a[1])); py=-1; if(py==-1 || a[i].y<py) px=a[i].x; py=a[i].y; p=i; else if(a[i].y==py && a[i].x<px) //swap(a[0],a[p]) temp=a[0].x; a[0].x=a[p].x; a[p].x=temp; temp=a[0].y; a[0].y=a[p].y; a[p].y=temp; qsort(&a[1],n-1,sizeof(double)*2,Compare); a[n].x=a[0].x; a[n].y=a[0].y; Tubao(); len=0.0; for(i=0;i<top;i++) len=len+Distance(result[i],result[i+1]); printf("%.2lf\n",len); return 0; 2018/11/21
Any Question? 2018/11/21
Thank you! See you next week. 2018/11/21