第1次課計算幾何學(xué)

1、第1次課 計算幾何學(xué)沈云付上海大學(xué)計算機工程與科學(xué)學(xué)院幾個問題判斷兩線段是否相交兩點是否被第三點擋住問題多邊形形狀：凹、凸如何判定點是否在多邊形中問題多邊形中的格點問題本章主要內(nèi)容一、幾何基本知識二、基本算法三、凸包四、實例研究一、幾何基本知識1.1 矢量的概念1.2 矢量加減法1.3 矢量叉積1.4 折線段的拐向判斷1.5 判斷點是否在線段上1.6 跨立試驗與判斷兩線段是否相交1.7 整數(shù)點與Pick定理1.1 矢量的概念1、 線段 設(shè)A(x1,y1)，B (x2,y2)是平面上任意兩點線段AB上的任一點C (x,y)滿足 x=x1+(1- )x2 y=y1+(1- )y2012、有向線段A

2、B（向量）：始點A，終點B 3、給定兩個向量OA和OB（簡記A，B）4、以O(shè)，A，B，A+B為頂點的平行四邊形面積OA OB= = x1y2-x2y1= -(OB OA) x1 x2 y1 y21.2 矢量加減法設(shè)二維矢量P = ( x1, y1 )，Q = ( x2 , y2 ) 。矢量加法定義為： P + Q = ( x1 + x2 , y1 + y2 )。矢量加法的幾何意義是以向量P、Q為鄰邊的平行四邊形的對角線 矢量減法定義為： P Q = ( x1 x2 , y1 y2 ) 1.3 矢量叉積2、叉積的性質(zhì)：1、矢量叉積：OA OB定義為以O(shè)，A，B，A+B為頂點的平行四邊形的帶符號的

3、面積。OA OBAB AC0 OB在OA的逆時針方向=0 O、A、B共線 0 AC在AB的逆時針方向= 0 A、B、C共線0 AB、BC在B處右轉(zhuǎn)：AB AC0A、B、C三點共線： AB AC 01.5 判斷點是否在線段上判斷點C在線段AB上的依據(jù)是：點C在線段AB所在的直線L上，C 在以A、B為對角頂點的矩形內(nèi)。BCA點在線段上的條件ON_SEGMENT算法描述：C點在直線AB上：AB AC=0C點不在線段AB的延長線或反向延長線上： (min(xA,xB) = xC)且(xC = max(xA,xB) 且 (min(yA,yB) = yC)且(yC = max(yA,yB)1.6 跨立試驗

4、與判斷兩線段是否相交 1、線段相交 設(shè)有4點：P1、P2、 Q1 、 Q2，問線段P1P2與 Q1Q2是否相交？P1Q2Q1P21.6 跨立試驗與判斷兩線段是否相交2、跨立試驗P1Q2Q1P2線段P1P2與 Q1Q2相交的條件（1）Q1、Q2在線段P1P2的兩側(cè)（2）P1、 P2在線段Q1Q2的兩側(cè)1.6 跨立試驗與判斷兩線段是否相交3、跨立試驗的叉積表示P1Q1Q1P2P1Q1 P1P2P1P2 P1Q20Q1P1 Q1Q2Q1Q2 Q1P20 1.6 跨立試驗與判斷兩線段是否相交 4、叉積與跨立試驗的應(yīng)用1）面積 平面上任意給定n個點，順次連接構(gòu)成一個折邊n邊形，求其面積。(2001ACM

5、/ICPC，上海大學(xué))面積S= /2p1p2p3p4piPi+1pn1.7 整數(shù)點與Pick定理 1、線段上格點問題格點：就是平面上坐標(biāo)為整數(shù)的點。問題：平面中一條線段上有多少個整數(shù)點？A(x1,y1)B(x2,y2)C(x,y)2、線段上的格點數(shù)算法/求數(shù)a、b的最大公因數(shù)int gcd ( int a,int b) if(b=0) return a;else return gcd(b,a%b);/線段AB上的格點個數(shù)由下列程序段給出：int OnSegment(int n,POINT A,POINT B) return gcd(fabs(A.x-B.x),fabs(A.y-B.y)+1;

6、1.7 整數(shù)點與Pick定理1.7 整數(shù)點與Pick定理3、多邊形中的格點問題給定直線x+y=n第一象限中有幾個格點？線上格點與原點連線構(gòu)成三角形，每個三角形中有幾個格點？數(shù)目相同嗎？1.7 整數(shù)點與Pick定理4、Pick定理：設(shè)以整數(shù)點為頂點的多邊形的面積為S，多邊形內(nèi)部的整數(shù)點數(shù)為N，多邊形邊界上的整數(shù)點數(shù)為L，則 S=L/2 + N-1。1.7 整數(shù)點與Pick定理5、計算多邊形邊上的網(wǎng)格點個數(shù)：int OnEdge(int n,POINT * p)int i,ret=0;for (i=0;in;i+) ret+=gcd(fabs(pi.x-p(i+1)%n.x),fabs(pi.y-

7、p(i+1)%n.y);return ret;多邊形內(nèi)部的網(wǎng)格點個數(shù)由下列程序段給出：int InSide(int n,POINT* p)int i, area =0;/ area是面積for (i=0;i0?(x):-(x)eps) int inside_polygon(point p,int n,point *pt) /設(shè)多邊形有n個頂點，pt是頂點數(shù)組point p1;int i=0,count;while (in) /隨機取一個足夠遠的點p1 p1.x=rand()+offset,p1.y=rand()+offset; /以p為始點、p1為終點作射線L; count=0; for (i

8、=0;in;i+)/依次對每條邊s=ptipti+1 考察 if (zero(CrossProd(p,pti,pt(i+1)%n) &(pti.x-p.x)*(pt(i+1)%n.x-p.x) eps&(pti.y-p.y)*(pt(i+1)%n.y-p.y)eps & CrossProd(pti,p,pt(i+1)%n) *CrossProd(pti,pt(i+1)%n,p1)eps) /若pp1與ptipti+1相交 count+;/則統(tǒng)計交點數(shù) return count%2;算法的時間復(fù)雜度為O(n) 三、凸包3.1 凸包的概念與實例3.2 Graham掃描法3.3 Jarris步進法3

9、.4 Graham掃描法與Jarris步進法的程序?qū)崿F(xiàn)3.1 凸包的概念與實例 給定平面上任意給定n個點的集合S=P1,P2, P3, , Pn1、凸包ch(S)：是一個最小的凸多邊形P，且滿足S中每個點或者在P的邊界上，或者在P的內(nèi)部 2、凸包求法- Graham掃描法- Jarris步進法p3p8p6p2p0p4p13p1p11p5p12p9p10p73.2 Graham掃描法1、點集Q中處于最低位置（y坐標(biāo)值最?。┑囊粋€點p0是凸包ch(Q)的一個頂點，最高位置的點也是凸包的一個頂點。3、用叉積確定點以極角遞增的順序進行掃描2、從p0開始向其它各點作射線進行掃描，考察射線上最遠的點是否為

10、凸包上的點p3p8p6p2p0p4p13p1p11p5p12p9p10p7Graham掃描法思想和步驟:Graham掃描法步驟設(shè)p0為Q中y坐標(biāo)值最小的點。若具有y坐標(biāo)最小值的頂點有多個，則取最左邊的那個點對Q的剩余點按逆時針相對p0的極角進行排序。若有多個這樣的點，則取一個與p1 距離最遠的點，不妨設(shè)序列P1,P2, P3，, Pm已選好確定凸包上的點：設(shè)定堆棧S，先將p0,p1,p2依次入棧，其它的點將被入棧一次，不是凸包上的點將從棧頂彈出。依據(jù)次棧頂元素ptop-1、棧頂元素ptop和點pi點是否構(gòu)成關(guān)于ptop左轉(zhuǎn)而確定pi是否入棧。見后頁檢驗過程。最后，棧里的元素即為凸包的頂點檢驗棧

11、頂元素是否為凸包的點若棧頂元素ptop和次棧頂元素ptop-1及所考察的點pi所形成角不是向左轉(zhuǎn)，則棧頂元素出棧；繼續(xù)考察棧頂元素ptop、次棧頂元素ptop-1、所考察的點pi，做a）的工作點pi進棧Graham掃描法偽代碼void graham(int n) 令P0為Q中X-Y坐標(biāo)下y坐標(biāo)排序最小的點; m=n-1; 按前面的取好序列P1，P2，P3，Pm; 設(shè)定一個棧S；依次壓P0, P1, P2進棧S；棧頂位置top=2; for ( i=3; i0算法偽代碼設(shè)Pk為最高點；P0為棧頂元素；只要棧頂元素不是Pk，循環(huán)做以下工作 Pm Pk； /依次考察其他點Pi是否有相對于Ptop的最

12、小極角 for(i=1; i0) | (PtopPi與PtopPm共線) &(| PtopPi|)|PtopPm| ) Pm=Pi; 用到的算法求最小數(shù)、最大數(shù)排序點對交換距離計算（比較）工具：叉積3.4 Graham掃描法與Jarris步進法的程序?qū)崿F(xiàn)參見教材四、實例研究4.1 有缺陷的衛(wèi)星4.2 籬笆4.3 處于危險之中的飛行員4.4 穿街走巷4.5 三角形4.1 有缺陷的衛(wèi)星問題描述 Discovery有限公司用有新智能照相機的衛(wèi)星。該照相機有一個軟件探測圖像中城市和道路及區(qū)域。衛(wèi)星沒有完全測試就發(fā)射，此后公司收到了一些有缺陷的圖片，包括一個或多個多余區(qū)域：外部區(qū)域。外部區(qū)域是一個平面區(qū)

13、域，它包括具有無限面積的每個其它區(qū)域。 Discovery沒有完全測試軟件就發(fā)射了這顆衛(wèi)星。因此他們此后收到了一些有缺陷的圖片，包括一個或多個多余區(qū)域：外部區(qū)域。外部區(qū)域是一個平面區(qū)域，它包括具有無限面積的每個其他區(qū)域。 圖像具有的性質(zhì)1圖像中所有城市都至少有兩條通向其它城市的道路。2每對城市之間有道路相連。3每對城市至多有一條直路。4除了在城市處，直路之間是不交叉的。 寫一個程序讀取一個有缺陷的圖像，同時報告外部區(qū)域。 城市和道路圖像示例 輸入與輸出輸入 第1行是一個整數(shù)N (1 N 20)，表示圖像數(shù)。 每個圖像的第1行是城市個數(shù)（150），接著的每行有2個整數(shù)x，y，是城市的位置。在接著

14、的一行上有一個整數(shù)（150），它是面的個數(shù)，隨后是這些面的信息（從1開始編號）。面的信息是由能構(gòu)成面的若干個城市個數(shù)和諸城市的編號組成的，城市以順時針（或逆時針）方向排列的。輸出 對每組測試數(shù)據(jù)，輸出邊界面的編號。兩組輸出之間無空行。 輸入與輸出樣例 輸入樣例輸出樣例152 64 44 78 64 1034 1 2 4 34 1 3 4 54 1 2 4 5 3分析（1）本問題要求求出包圍整個圖像中所有城市的一個面的編號，使其他的所有面都在這個面之中。所要求的面必須最大，包含其他所有的面，沒有必要對所有城市構(gòu)成的點集求凸包，而只需求具有面積最大的那個面。對所有面求面積，選取具有最大面積者即可。

15、 多邊形的面積 求多邊形面積的方法有很多。 在前面關(guān)于叉積與跨立試驗一節(jié)時介紹過多邊形面積求法 。采用將多邊形劃分為若干三角形進行求解。在采用叉積方法時三角形的劃分可以很隨意，根據(jù)三個頂點求三角形的面積也有多種。而不必考慮多邊形是凸還是凹。另外還可取原點O(0，0)與多邊形的相鄰兩個頂點A(x1，y1)、B(x2 ，y2)構(gòu)成一個三角形。 三角形OAB的面積是 =參考程序 略4.2 籬笆 問題描述 某平地上有一塊用籬笆圍起來的區(qū)域。籬笆高度h，在平面投影下形成一個封閉的（無自相交的）多邊形線條，其N個頂點用坐標(biāo)(Xi, Yi)表示。在位置(0, 0)處豎立著一盞燈。該燈可能在籬笆墻的外面或里面

16、，但不會在它的邊上，如圖所示，（細(xì)線顯示的部分沒有被照到）： 籬笆是完全黑的，即它既不反射光，也不散射光，更不透光。落到籬笆的任意一個照亮點的強度用下面的公式表示： I0=k/r 其中，k是一個不依賴于問題中的點的常數(shù)值，r是這個點到平面投影中燈的距離。寬度dl高為h的極小豎立窄板照度是 dI=I0|cos|dlh 這里I0是光在籬笆上的強度，是平面投影中該點處的籬笆的邊與對著燈的方向構(gòu)成的角。 現(xiàn)要求你寫一個程序找到籬笆的全部照度，該照度是以所有它的亮度的板上的照度之和來定義的。 輸入與輸出輸入 第一行有整數(shù)k，h，N，之間用空格隔開。k和h是實常數(shù)，N（3N100）是籬笆的頂點數(shù)。接下來有

17、N行，每一行有2個實數(shù)Xi，Yi，之間有一個空格。輸出 輸出籬笆的總照度值，四舍五入到小數(shù)點后兩位。 輸入與輸出樣例輸入樣例輸出樣例0.5 1.7 31.0 3.02.0 -1.0-4.0 -1.05.34分析 不妨設(shè)燈在坐標(biāo)原點。 寬度dl高為h的極小豎立窄板照度是 dI=I0(|cos|h) dl 一條邊的總照度為 x1，x2為一條邊的左右端點， 為這條邊對原點所張的角度。 本題實際上要求整個籬笆區(qū)域?qū)υc所張開的總角度。分析 定義籬笆為一有向回路，每條邊都是有向的。如果按照邊的方向?qū)υc所張開的角為順時針方向形成的角，那么定義角度為正，逆時針向為負(fù)。 對于包含原點的區(qū)域，轉(zhuǎn)動的角度應(yīng)該為

18、正負(fù)2；對于不包含原點的區(qū)域，最大轉(zhuǎn)動角度是這個區(qū)域?qū)υc所張開的角度。但可能還有一種情況，那就是區(qū)域不包含原點，但是總共張開的角度大于2 ，那么按2計算。程序?qū)崿F(xiàn)分析 數(shù)據(jù)結(jié)構(gòu)：用POINT存儲點的位置，用INTERVAL存儲線段。定義函數(shù)：原點O與點(x,y)構(gòu)成的射線關(guān)于x軸正向的夾角double Calc_angle(double x, double y) ;確定線段以a和b點為兩端點對原點與x軸正向的夾角INTERVAL Calc_range(POINT a, POINT b) ;確定x在a和b之間bool between(double a, double x, double b)

19、;參考程序：參見教材復(fù)雜性 如果有N個點，那么空間復(fù)雜度為O(N)，時間復(fù)雜度為O(N)。4.3 處于危險之中的飛行員 問題描述 第二次世界大戰(zhàn)中的一天，一架蘇聯(lián)轟炸機的油料耗盡了，飛行員不得不跳傘進入敵占區(qū)。他有危險了！他很快冷靜下來。他必須知道他是否在敵人的營區(qū)。如果他不幸進入敵人的營區(qū)，他必須獲得這樣一個密碼數(shù)，利用它可以使任何人毫無困難地通過警戒線。 營區(qū)是一個用柵欄圍起來的一塊區(qū)域，在飛機上看，柵欄是（無自交）封閉多邊形線， 其n個頂點用笛卡爾坐標(biāo)（xi ，yj）表示。飛行員所在位置是坐標(biāo)原點（0，0），他可以確定不在柵欄的邊上，即他要么在里面要么在外面。 如何獲得營區(qū)的密碼數(shù)？營區(qū)

20、有兩個不同的素數(shù)p，q， pq，任何人都容易獲得。密碼數(shù)表示有多少個正整數(shù)不可能寫成形如px+qy的形式，其中 x, y 是非負(fù)整數(shù)。 例如，給定p=3和q=5，那么有四個正整數(shù)1、2、4、7不可能有所述的形式。因此，這密碼數(shù)是4。 你的任務(wù)：判定飛行員是否在營區(qū)，如果他在營區(qū)，取得這密碼數(shù)。輸入與輸出輸入 有多組測試數(shù)據(jù)。每一組測試數(shù)據(jù)的第一行有一個整數(shù)n，（3n16），n=0意味著輸入結(jié)束。n是柵欄的頂點數(shù)。接下來有n行，每行有兩個實數(shù)xi 和yi，之間有一個或多個空格。接下來的一行，有兩個素數(shù)p, q, 2p, q1000，用它們你去獲得密碼數(shù)。 頂點是順時針或逆時針方向顯示的。輸出 對

21、每組測試數(shù)據(jù)，先輸出飛行員的號碼，在下一行上告訴我們飛行員是否處于危險之中（如他在敵人營區(qū)）。如果他處于危險之中，在下面的一行上輸出這個密碼數(shù)。每組測試數(shù)據(jù)處理后輸出一空行。 輸入樣例4-1.0 -1.02.0 -1.02.0 2.0-1.0 2.03 55-2.5 -2.510.5 -2.510.5 -1.5-1.5 -1.5-2.5 20.52 70輸出樣例Pilot 1The pilot is in danger!The secret number is 4.Pilot 2The pilot is safe.分析該問題可歸結(jié)為如下問題：1.密碼如何求出？ 密碼的輸出與兩個素數(shù)有關(guān)。 2.

22、確定飛行員位置，即點是否在多邊形內(nèi)？ 這點很容易判定。前面已經(jīng)介紹。密碼計算設(shè)p，q是兩個素數(shù)，密碼數(shù)是不可能寫成形如px+qy的形式的正整數(shù)的個數(shù)，其中x，y是非負(fù)整數(shù)。在第5章已給出結(jié)論，密碼為 參考程序：略4.4 穿街走巷 問題描述比利快遞服務(wù)公司（BBMS） 。為發(fā)展業(yè)務(wù)，制定合理的收費，BBMS正根據(jù)快遞員能走的最短路線制定一項快遞收費標(biāo)準(zhǔn)。而你則要替BBMS編寫一個程序來確定這些路線的長度。 一些假設(shè)快遞員可以在地面上除建筑物內(nèi)部以外的任何地方騎車。地形不規(guī)則的建筑物可以認(rèn)為是若干矩形的合并。并規(guī)定，任何相交矩形擁有共同內(nèi)部，而且是同一建筑物的一部分。盡管兩個不同的建筑物可能非常接

23、近，但永遠不會重疊。（快遞員可以從任意兩個建筑物之間穿過。他們能夠繞過最急的拐彎，可以貼著建筑物的邊緣疾駛。）起點和終點不會落在建筑物內(nèi)部?？傆幸粭l連接起訖點的線路。建筑物分布鳥瞰圖 StopStart輸入與輸出輸入：第一行：n 場景中描述建筑物的矩形個數(shù)，0n20。第二行：x1、y1、x2、y2 路線起訖點的x 和y坐標(biāo)。余下n行：x1、y1、x2、y2、x3、y3 矩形三個頂點的坐標(biāo)，所有x 、y坐標(biāo)是屬于0到1000（包含0和1000）的實數(shù)，每行中相鄰的坐標(biāo)由一個或多個空格分開。輸出： 給出從起點到終點的最短線路的長度，精確到小數(shù)點后第二位。輸入與輸出樣例輸入樣例輸出樣例56.5 9

24、10 31 5 3 3 6 65.25 2 8 2 8 3.56 10 6 12 9 127 6 11 6 11 810 7 11 7 11 11 7.28 算法分析可行路徑解由哪些點構(gòu)成？可行路徑的頂點構(gòu)成： 起點、終點、其他若干矩形頂點 要求：這些矩形頂點不能被其他矩形覆蓋 注意：可行路徑上相鄰兩頂點（除起點、終點）連線，是不與已知矩形的邊相交的線段，但原來矩形列的不相交邊也是可行路徑，不應(yīng)遺漏。最短路徑是一條可行路徑。算法分析可行路徑：兩頂點（除起止點）連線中，不與已知矩形的邊相交的線段注：原來矩形列的不相交邊也是可行路徑判斷一線段與其他線段是否相交用跨立試驗輸入三個頂點P1、 P2、

25、P3，如何判斷位置以求第4個頂點 P4 ？P1P2P3P1P2P3確定直角頂點通過斜率求距離：計算P1P22、P1P32、P2P32，最大者為對角線的平方最短路徑的頂點數(shù)據(jù)結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)：用表point表示頂點數(shù)據(jù)類型。用pp表示起點、終點、所有矩形頂點列表， pp1、 pp2表示起點、終點， pp3, pp4n+2放n矩形的4n個頂點。最短路線上的頂點取自于pp表。 建立一張線段表Lines，將每個矩形的4條矩形邊和2條對角線存入該表。設(shè)置Lines表的目的是為了判斷快遞員的行車路線是否符合規(guī)則。如果行車路線與表中任一條矩形邊相交，則說明快遞員進入了建筑物內(nèi)部，這種情況必須排除。 可行矩陣T

26、able Tableij=true ppippj可達 用intersect(P1, P2,P3, P4)記線段P1P2、 P3P4的跨立試驗 用Nobuilding(P1,P2)記邊P1P2是否進入矩形內(nèi)部。int Nobuilding(point P1, point P2) /計算框架 int flag=1; for(i=1;i6*n; i+) if (intersect(P1, P2,Linesi.A, Linesi.B) flag=0; break； Return flag;可行矩陣Table構(gòu)造int TAB（） Nobuilding=0; /false; for(i=1;i4*n+2

27、; i+) for(j=1;j4*n+2; j+) Tableij=Nobuildingppi,ppj); Tableji= Tableij; 記checki: checki=1, 頂點i在最短路徑上 checki=0, 頂點i不在最短路徑上記disti為起點至頂點i的最短路徑長度最短路徑求法采用BFS：類似于Dijkstra的最短路徑算法。1、開始時， 所有checki=0，dist起點=0，所有其他disti=maxint2、在checki=0的點中尋找有最小dist值的點i3、然后在checkj=0的點中尋找i可達的頂點j,使在連結(jié)起點到j(luò)的所有經(jīng)過i的路徑中，修正路徑distj，使值最小4、checki