计算几何基础130

1、2021-11-71acm acm 程序设计程序设计计算机学院计算机学院 刘春英刘春英2021-11-72调课一周2021-11-7306057229许璟亮许璟亮2021-11-74计算几何初步计算几何初步(computational geometry basic)2021-11-75第一单元线 段 属 性2021-11-762021-11-772021-11-782021-11-792021-11-7102021-11-7112021-11-7122021-11-7132021-11-714思考：1、传统的计算线段相交的方法是什么？2、传统方法和本方法的区别是什么？2021-11-715特别

2、提醒：l以上介绍的线段的三个属性，是计算几何的基础，在很多方面都有应用，比如求凸包等等，请务必掌握！2021-11-716第二单元多边形面积 和重心2021-11-717基本问题（1）：l给定一个简单多边形，求其面积。l输入：多边形（顶点按逆时针顺序排列）l输出：面积s2021-11-718思考如下图形：2021-11-719any good idea?2021-11-720先讨论最简单的多边形三角形2021-11-721三角形的面积：l在解析几何里， abc的面积可以通过如下方法求得：l点坐标 = 边长 = 海伦公式 = 面积2021-11-722计算量大精度损失更好的方法？2021-11-

3、723l在计算几何里，我们知道，abc的面积就是“向量ab”和“向量ac”两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。abc成左手系，负面积abc成右手系，正面积bcacba2021-11-724larea(a,b,c)= 1/2 * (ab) (ac) = /2l特别注意： 以上得到是有向面积（有正负）有向面积（有正负）！ xb x a yb y axc x a yc y a2021-11-725凸多边形的三角形剖分l很自然地，我们会想到以 p1为扇面中心，连接p1pi就得到n-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积： a=s

4、igma(ai) (i=1n-2)p1p2p3p4p5p6a1a2a3a42021-11-726凹多边形的面积？p1p4p3p22021-11-727多边形面积公式：a=sigma(ai) (i=1n-2)结论： “有向面积”a比“面积”s其实更本本质质！2021-11-728l我们能把多边形分成n-2个三角形，为什么不能分成n个三角形呢？l比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 n个三角形。p0p1p2p6p5p4p32021-11-729前面的三角剖分显然对于多边形内部任意一点都是合适的！我们可以得到：a=sigma(ai) （ i=1n ）即：a= sigma /2 （

5、i=1n ） xi x0 yi y0x(i+1) x0 y(i+1) y02021-11-730p0p1p2p3p42021-11-731op1p2p3p4现在的公式？2021-11-732简化的公式：a=sigma /2（ i=1n ） xi yix(i+1) y(i+1)面积问题面积问题搞定！搞定！2021-11-733基本问题（2）：l给定一个简单多边形，求其重心。l输入：多边形（顶点按逆时针顺序排列）l输出：重心点c2021-11-734三角形的重心是： (x1+x2+x3) / 3，(y1+y2+y3) / 3可以推广否？sigma(xi)/n , sigma(yi)/n (i=1n

6、) ?2021-11-735.2021-11-736l错误的推广公式是“质点系重心公式”，即如果认为多边形的质量仅分布在其顶点上，且均匀分布，则这个公式是对的。l但是，现在多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的！2021-11-737l剖分成n个三角形，分别求出其重心和面积，这时可以想象，原来质量均匀分布在内部区域上，而现在质量仅仅分布在这n个重心点上（等假变换），这时候就可以利用刚才的质点系重心公式了。l不过，要稍微改一改，改成加权平均加权平均数，因为质量不是均匀分布的，每个质点代表其所在三角形，其质量就是该三角形的面积（有向面积有向面积！），这就是权！2021-1

7、1-738lc=sigma(ai * ci) / a (i=1n)lci=centroid( o pi pi+1)l = (o + pi +pi+1 )/3lc=sigma(pi +pi+1)(pi pi+1) ) /(6a)2021-11-7392021-11-740凸包( convex hull )2021-11-7412021-11-7422021-11-7432021-11-7442021-11-7452021-11-7462021-11-7472021-11-7482021-11-7492021-11-7502021-11-7512021-11-7522021-11-7532021-

8、11-7542021-11-7552021-11-7562021-11-7572021-11-7582021-11-7592021-11-7602021-11-7612021-11-7622021-11-7632021-11-7642021-11-7652021-11-7662021-11-7672021-11-768/xiaoxia版#include #include #include typedef structdouble x;double y;point;point result102;/保存凸包上的点point a102;int n,top;double distance(point

9、 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,*

10、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

11、; 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.