計算幾何在程序設(shè)計競賽中的應用ppt課件

1、計算幾何在程序設(shè)計競賽中的應用計算幾何在程序設(shè)計競賽中的應用軟件學院2019級穆浩英預備知識預備知識(I)差乘：計算幾何的基本問題計算幾何的基本問題是位置和方向，基本是位置和方向，基本運算是向量的差乘和運算是向量的差乘和點乘點乘aba x b =xayb-xbya=xa yaxb yb = a b sin兩個向量差積的幾何意義是以兩個向量差積的幾何意義是以兩向量為鄰邊的平行四邊形的兩向量為鄰邊的平行四邊形的有向面積，若有向面積，若為右手螺旋為右手螺旋方向結(jié)果為正，否則為負。方向結(jié)果為正，否則為負。（為有向夾角）為有向夾角） 所以，計算幾何中的位置是指左右。如果所以，計算幾何中的位置是指左右。如

2、果axb0則則a在在b的右邊的右邊否則否則a在在b的左邊的左邊預備知識預備知識(II)差積應用(1)：判斷兩條線段是否相交計算幾何的基本問題計算幾何的基本問題是位置和方向，基本是位置和方向，基本運算是向量的差乘和運算是向量的差乘和點乘點乘首先，將線段作向量處理。首先，將線段作向量處理。如果點如果點(x3,y3)、(x4,y4)分別在分別在A的的兩側(cè)兩側(cè),同時點同時點(x1,y1)、點、點(x2,y2)分別分別在在B的兩側(cè)的兩側(cè)(xy)，則可以確定，則可以確定A與與B相交相交.我們定義一種運算我們定義一種運算cross(a,b,c)，它，它的返回值為向量的返回值為向量與向量與向量的的差積。差積。

3、那么：那么： if(cross(a,b,c)*cross(a,b,d)0 &cross(c,d,a)*cross(c,d,b)0) return TRUE；a(x1,y1)b(x2,y2)c(x3,y3)d(x4,y4)AB(x3,y3)(x4,y4)在A的兩邊預備知識預備知識(III)特殊情況：計算幾何的基本問題計算幾何的基本問題是位置和方向，基本是位置和方向，基本運算是向量的差乘和運算是向量的差乘和點乘點乘efghabcd（一）（一）（二）（二）cross(a,b,d) =0 ,cross(e,f,h)=0,但一可以認為相交，（二但一可以認為相交，（二則不可以認為相交則不可以認為相交 。判

4、斷交點是否在線段上。判斷交點是否在線段上預備知識預備知識(VI)為解決上述問題，我們引入點乘：計算幾何的基本問題計算幾何的基本問題是位置和方向，基本是位置和方向，基本運算是向量的差乘和運算是向量的差乘和點乘點乘baa .b = xa*xb + ya*yb = a b cosabc當當cross(a,b,c)=0時，假如時，假如 . 小于等于小于等于0，那么，那么c點在點在ab上，否則上，否則c點在點在ab外外預備知識預備知識(V)設(shè)設(shè)dot(a,b,c) 返回返回.的值。我們來看的值。我們來看dot(a,b,c)值與值與c在在ab上投影上投影c的關(guān)系的關(guān)系.計算幾何的基本問題計算幾何的基本問題

5、是位置和方向，基本是位置和方向，基本運算是向量的差乘和運算是向量的差乘和點乘點乘abccccdot(a,b,c) = 0c在在a上上 cdot(a,b,c) ab 2 c在在ab前前 0 dot(a,b,c) ab 2c在在ab上上 基本問題舉例基本問題舉例()1.位置 (左右)判斷例：zju1041問題描述：在有n個點的面上有一個給定了半徑和圓心坐標的半圓，半圓可以繞圓心轉(zhuǎn)動但不可以平移，求半圓最多能包含多少點，邊界上的點認為在圓內(nèi)。基本問題舉例基本問題舉例()基本思路：1.到圓心的距離大于半徑的點直到圓心的距離大于半徑的點直接排除。接排除。2.以圓心和任意一點確定一以圓心和任意一點確定一

6、有有向線段作為半徑位置，分別計數(shù)向線段作為半徑位置，分別計數(shù)該有向線段左邊點的個數(shù)該有向線段左邊點的個數(shù)(nl)和和右邊點的個數(shù)右邊點的個數(shù)(nr)。3.重復步驟重復步驟2直到所有點都被枚舉直到所有點都被枚舉過。過。4.枚舉過程中出現(xiàn)的最大的枚舉過程中出現(xiàn)的最大的nl或或nr就是所求的結(jié)果。就是所求的結(jié)果。nl =nr =Max =34452433452534基本問題舉例()代碼：代碼：#includeusing namespace std;struct point int x,y;pp150;int det(int x1,int y1,int x2,int y2) return(x1*y2-

7、x2*y1);int main() int rx,ry; double r; while(cinrxryr & r0) int max = 0; r=r*r; int n,i; int p = 0;cinn;for(i = 0 ;i xy; if(x-rx)*(x-rx)+(y-ry)*(y-ry)=r) ppp.x=x; ppp+.y=y; for(i = 0 ;i p ; i +) int num_l=0，num_r=0，j; for(j = 0; j 0) num_l+; if(dmax) max = num_l;if(num_rmax) max = num_r;coutmax= 0)l

8、ine makeline(point p1,point p2) line l; int sign = 1; l.a=p2.y-p1.y; if( l.a0 ) sign = -1; l.a=sign*l.a; l.b=sign*(p1.x-p2.x); l.c=sign*(p1.y*p2.x-p1.x*p2.y); return l; 基本問題舉例（基本問題舉例（）l相關(guān)算法l判斷兩線段是否相交，如果相交則求出交點l相交用差積cross(a,b,c)*cross(a,b,d)0 &cross(c,d,a)*cross(c,d,b) cutting_num) & cutting_num 0) l

9、ine_seg cuttings8; int line_num=0; for(int i=0;i l;if(line_num=0 | !line_already_exists(l,cuttings,line_num) )cuttingsline_num+=l; int main(int argc, char *argv)/ int partion_num = line_on_edge(cuttings0)?1:2; for(int i=1;iline_num;i+) if(line_on_edge(cuttingsi)continue; vector new_cross_pts; for(in

10、t j=0;j0&!point_already_exists(cross_pt,new_cross_pts) new_cross_pts.push_back(cross_pt); partion_num+=(1+new_cross_pts.size(); cout partion_num endl; return 0;基本問題舉例基本問題舉例()3.求多邊形的面積。求多邊形的面積。 前面已經(jīng)講過，兩向量的差積的幾何意義前面已經(jīng)講過，兩向量的差積的幾何意義是以這兩個向量為鄰邊的平行四邊形的有向面是以這兩個向量為鄰邊的平行四邊形的有向面積，我們可以利用這一點來求簡單多邊形的面積，我們可以利用這一點

11、來求簡單多邊形的面積。積。所謂簡單多邊形就是任何不相鄰的兩條邊所謂簡單多邊形就是任何不相鄰的兩條邊都沒有交點，包括凸多邊形和凹多邊形。都沒有交點，包括凸多邊形和凹多邊形。.基本問題舉例基本問題舉例()求下面多邊形的面積，已知個頂點的坐標。A=1/2Xi yi Xi+1 yi+1i=1nabcdefabcdef0基本問題舉例基本問題舉例()4.求凸包求凸包定義：直觀地講，對于一個平面點集或者一個定義：直觀地講，對于一個平面點集或者一個多邊形，它的凸包指的是包含它的最小凸多邊形，它的凸包指的是包含它的最小凸圖形或最小凸區(qū)域。圖形或最小凸區(qū)域?；締栴}舉例基本問題舉例()Graham-Scan算法算

12、法(了解了解Gift-Wrapping算法算法 )試探性凸包試探性凸包 我們嘗試從我們嘗試從p1(最低點，一定屬于凸包最低點，一定屬于凸包)動身，動身，沿著多邊形頂點逆時針的順序，試探性的增長沿著多邊形頂點逆時針的順序，試探性的增長凸包凸包.顯然，一個點如果屬于凸包，那么它到顯然，一個點如果屬于凸包，那么它到達下一個點一定需要左轉(zhuǎn)，否則，該點一定不達下一個點一定需要左轉(zhuǎn)，否則，該點一定不屬于凸包。屬于凸包。 P1P2P4P3P6P5P1P2P3P4P6P5凸包頂點凸包頂點基本問題舉例基本問題舉例()算法總結(jié)：算法總結(jié)：2.該算法帶有簡單的回溯，因此宜用棧實現(xiàn)，棧中存儲的是該算法帶有簡單的回溯，

13、因此宜用棧實現(xiàn)，棧中存儲的是 到目前為止的到目前為止的“局部凸包局部凸包”，如果當前邊對于棧頂邊右轉(zhuǎn)，就，如果當前邊對于棧頂邊右轉(zhuǎn)，就 退棧。一直到退棧。一直到“局部凸包完好。局部凸包完好。 1. Graham-Scan需要一個序，如果輸入是平面點集，首先需要一個序，如果輸入是平面點集，首先需要對所有的點按極角排序。顯然，需要對所有的點按極角排序。顯然， “極角大小比較用極角大小比較用“左右手關(guān)系比較左右手關(guān)系比較(差積差積) 即：即：BCi的極角比的極角比BCj的極角大的極角大BCi在在BCj左邊。左邊。基本問題舉例基本問題舉例()3.偽代碼：偽代碼：push(p1);push(p2);i=

14、3;while i=n doif pi 在棧頂邊在棧頂邊pt-1pt左手方向左手方向then push(pi) 并且并且i+；else pop();4.復雜度分析復雜度分析 上述上述while語句中，每個點顯然進棧一次，而最多出棧語句中，每個點顯然進棧一次，而最多出棧一次，故時間復雜度為一次，故時間復雜度為O(n).附加問題附加問題(需要離散化問題需要離散化問題)例：例：zju1128 問題描述：一些已知右下頂點和左上頂點問題描述：一些已知右下頂點和左上頂點坐標的矩形，這些矩形可能部分重疊，求它們坐標的矩形，這些矩形可能部分重疊，求它們所占的實際面積。例如：所占的實際面積。例如：附加問題附加問

15、題(需要離散化問題需要離散化問題)方案一、方案一、把矩形映射到數(shù)組把矩形映射到數(shù)組M 中，如果某矩形的位置為中，如果某矩形的位置為x1，y1）（）（x2，y2則則Mij=1其中其中x1=i=x2,y1=jx1,Xi2y1,Yi2=y2令令XY i j = 1 (i從從i1到到i2，j從從j1到到j(luò)2)3、統(tǒng)計面積：、統(tǒng)計面積： area+=XYij *(Xi-Xi-1)*(Yi Yi-1)X1X2X5X7Y3Y6Y8Y1Y2附加問題附加問題(需要離散化問題需要離散化問題)代碼代碼#includeusing namespace std;double x200,y200,in1004;bool x

16、y200200;double N=0.000001;int n_map;void input(); void solve(); double cacu(); 附加問題附加問題(需要離散化問題需要離散化問題)int main() while(cinn_map & n_map != 0) input();sort(x,x+2*n_map);sort(y,y+2*n_map);memset(xy,0,sizeof(xy);solve();double sum=cacu();coutsumendl;return 0;附加問題附加問題(需要離散化問題需要離散化問題)void input()for(int i = 0,k=0 ; i ini0ini1ini2ini3;xk = ini0;yk = ini1;k+;xk = ini2;yk = ini3;k+;附加問題附加問題(需要離散化問題需要離散化問題)void solve()for(int i = 0 ; i N & k N &