計算幾何基礎ppt課件

1、ACM ACM 程序設計程序設計計算機學院計算機學院 劉春英劉春英調課一周06057229許璟亮許璟亮計算幾何初步計算幾何初步(Computational Geometry Basic)線 段 屬 性1、傳統的計算線段相交的方法是什么？2、傳統方法和本方法的區(qū)別是什么？l以上引見的線段的三個屬性，是計算幾何的根底，在很多方面都有運用，比如求凸包等等，請務必掌握！多邊形面積 和重心l給定一個簡單多邊形，求其面積。l輸入：多邊形頂點按逆時針順序陳列l(wèi)輸出：面積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(wèi)輸出：重心點C三角形的重心是： (x1+x2+x3) / 3，(y1+y2+y3) / 3可以推行否？Sigma(xi)/N , sigma(yi)/N (i=1N) ?.l錯誤的推行公式是“質點系重心公式，即假設以為多邊形的質量僅分布在其頂點上，且均勻分布，那么這個公式是對的。l但是，如今多邊形的質量是均勻分布在其內部區(qū)域上的，也就是說，是與面積有關的！l剖分成N個三角形，分別求出其重心和面積，這時可以想象，原來質量均勻分布在內部區(qū)域上，而如今質量僅僅分布在這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;