计算几何基础ppt课件

1、ACM ACM 程序设计程序设计计算机学院计算机学院 刘春英刘春英调课一周06057229许璟亮许璟亮计算几何初步计算几何初步(Computational Geometry Basic)线 段 属 性1、传统的计算线段相交的方法是什么？2、传统方法和本方法的区别是什么？l以上引见的线段的三个属性，是计算几何的根底，在很多方面都有运用，比如求凸包等等，请务必掌握！多边形面积 和重心l给定一个简单多边形，求其面积。l输入：多边形顶点按逆时针顺序陈列l输出：面积Sl在解析几何里， ABC的面积可以经过如下方法求得：l点坐标 = 边长 = 海伦公式 = 面积计算量大精度损失更好的方法？l在计算几何里，

2、我们知道，ABC的面积就是“向量AB和“向量AC两个向量叉积的绝对值的一半。其正负表示三角形顶点是在右手系还是左手系。ABC成左手系，负面积ABC成右手系，正面积BCACBAlArea(A,B,C)= 1/2 * (AB) (AC)l = /2l特别留意：l 以上得到是有向面积有正负！ Xb X a Yb Y aXc X a Yc Y al很自然地，我们会想到以 P1为扇面中心，衔接P1Pi就得到N-2个三角形，由于凸性，保证这些三角形全在多边形内，那么，这个凸多边形的有向面积：l A=sigma(Ai) (i=1N-2)P1P2P3P4P5P6A1A2A3A4P1P4P3P2多边形面积公式：

3、A=sigma(Ai) (i=1N-2)结论： “有向面积A比“面积S其实更本质！l我们能把多边形分成N-2个三角形，为什么不能分成N个三角形呢？l比如，以多边形内部的一个点为扇心，就可以把多边形剖分成 N个三角形。P0P1P2P6P5P4P3我们可以得到：A=sigma(Ai) i=1N 即：A= sigma /2 i=1N Xi X0 Yi Y0X(i+1) X0 Y(i+1) Y0P0P1P2P3P4OP1P2P3P4如今的公式？A=sigma /2 i=1N Xi YiX(i+1) Y(i+1)面积问题面积问题搞定！搞定！l给定一个简单多边形，求其重心。l输入：多边形顶点按逆时针顺序陈

4、列l输出：重心点C三角形的重心是： (x1+x2+x3) / 3，(y1+y2+y3) / 3可以推行否？Sigma(xi)/N , sigma(yi)/N (i=1N) ?.l错误的推行公式是“质点系重心公式，即假设以为多边形的质量仅分布在其顶点上，且均匀分布，那么这个公式是对的。l但是，如今多边形的质量是均匀分布在其内部区域上的，也就是说，是与面积有关的！l剖分成N个三角形，分别求出其重心和面积，这时可以想象，原来质量均匀分布在内部区域上，而如今质量仅仅分布在这N个重心点上等假变换，这时候就可以利用刚刚的质点系重心公式了。l不过，要略微改一改，改成加权平均数，由于质量不是均匀分布的，每个质

5、点代表其所在三角形，其质量就是该三角形的面积有向面积！，这就是权！lC=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)凸包( Convex Hull )/xiaoxia版#include #include #include typedef structdouble x;double y;POINT;POINT result102;/保管凸包上的点POINT a102;int n,top;double Distance(POINT p

6、1,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

7、) ;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;

8、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;