GIS算法的計算幾何基礎2

1、1GIS算法的計算幾何基礎(2)GISGIS算法基礎算法基礎第二章第二章2本 講 內 容v1 判斷矩形是否包含點v2 判斷線段、折線、多邊形是否在矩形中v3 判斷矩形是否在矩形中v4 判斷圓是否在矩形中v5 判斷點是否在多邊形內v 6 判斷線段是否在多邊形內判斷線段是否在多邊形內 v 7 判斷折線是否在多邊形內判斷折線是否在多邊形內 v 8 判斷多邊形是否在多邊形內判斷多邊形是否在多邊形內v 9 判斷矩形是否在多邊形內判斷矩形是否在多邊形內 v10 判斷圓是否在多邊形內判斷圓是否在多邊形內 3本 講 內 容v11 判斷點是否在圓內判斷點是否在圓內 v12 判斷線段、折線、矩形、多邊形是否在判斷

2、線段、折線、矩形、多邊形是否在圓內圓內 v13 判斷圓是否在圓內判斷圓是否在圓內 v14 計算兩條共線的線段的交點計算兩條共線的線段的交點v15 計算線段或直線與線段的交點計算線段或直線與線段的交點 41 矩形是否包含點v只要判斷點的橫坐標與縱坐標是否夾在矩形的左右只要判斷點的橫坐標與縱坐標是否夾在矩形的左右邊和上下邊之間。邊和上下邊之間。52判斷線段、折線、多邊形是否在矩形中v矩形是凸集，所以只需判斷所有的端點是否在矩形矩形是凸集，所以只需判斷所有的端點是否在矩形中。中。63 判斷矩形是否在矩形中v比較左右邊界和上下邊界比較左右邊界和上下邊界74 判斷圓是否在矩形中v圓心在矩形中，且圓的半徑

3、小于等于圓心到矩形四圓心在矩形中，且圓的半徑小于等于圓心到矩形四邊的距離的最小值。邊的距離的最小值。8v常用算法：常用算法：射線法（奇偶法）射線法（奇偶法）轉角法：環(huán)繞數（多邊形環(huán)繞點的次數）為轉角法：環(huán)繞數（多邊形環(huán)繞點的次數）為0，則點在多邊形外，否則，點在多邊形內。，則點在多邊形外，否則，點在多邊形內。5 判斷點是否在多邊形內95.1 射線法v射線法計算從點射線法計算從點P P開始的射線穿過多邊形邊界的次數，多邊開始的射線穿過多邊形邊界的次數，多邊形的邊界將多邊形內部與外部分開。如果結果為偶數，則點形的邊界將多邊形內部與外部分開。如果結果為偶數，則點在多邊形外部，否則，若為奇數，則點在多

4、邊形內部。在多邊形外部，否則，若為奇數，則點在多邊形內部。105.1 射線法v必須決定在多邊形邊界上的點是在多邊形內部還是外部。必須決定在多邊形邊界上的點是在多邊形內部還是外部。一一個標準的約定個標準的約定是是在左邊界或者下邊界上的點認為是在多邊形在左邊界或者下邊界上的點認為是在多邊形內部，在右邊界或者上邊界的點認為是在多邊形外部內部，在右邊界或者上邊界的點認為是在多邊形外部。在這。在這種約定下，如果兩個不同的多邊形共享一個邊，那么在這條種約定下，如果兩個不同的多邊形共享一個邊，那么在這條邊上的點會在一個多邊形的內部而在另一個多邊形的外部。邊上的點會在一個多邊形的內部而在另一個多邊形的外部。

5、115.1 射線法v一個一個簡單的射線法簡單的射線法是是選擇一條水平的、向點選擇一條水平的、向點P P的右側延伸的、的右側延伸的、平行于平行于X X軸的射線軸的射線。v為了計算總的交點的數目，算法簡單的遍歷多邊形的所有邊，為了計算總的交點的數目，算法簡單的遍歷多邊形的所有邊，測試是否穿越邊，穿越時增加交點的數目。測試是否穿越邊，穿越時增加交點的數目。v穿越測試必須處理好一些特殊的情形。完全穿越測試必須處理好一些特殊的情形。完全規(guī)則規(guī)則如下：如下：（1 1）方向向上的邊）方向向上的邊包括其開始點，不包括其終止點包括其開始點，不包括其終止點；（2 2）方向向下的邊）方向向下的邊不包括其開始點，包括

6、其終止點不包括其開始點，包括其終止點；（3 3）水平邊不參加穿越測試水平邊不參加穿越測試；（4 4）射線和多邊形的邊的交點必須嚴格在點）射線和多邊形的邊的交點必須嚴格在點P P的右邊的右邊。125.1 射線法135.1 射線法v射線法的有效性是基于射線法的有效性是基于一個簡單的閉合曲線將二維平面分成一個簡單的閉合曲線將二維平面分成兩個相連接的部分：有邊界的內部和無邊界的外部兩個相連接的部分：有邊界的內部和無邊界的外部。v曲線必須是簡單的（沒有自相交），否則平面會被分成兩個曲線必須是簡單的（沒有自相交），否則平面會被分成兩個以上的部分，并且不能保證穿越邊界時不會改變出入特性以上的部分，并且不能保

7、證穿越邊界時不會改變出入特性。v對于一個閉合的曲線，可能將二維平面分成多個部分，但是對于一個閉合的曲線，可能將二維平面分成多個部分，但是其中只有一個沒有邊界且在曲線外部的部分。其中只有一個沒有邊界且在曲線外部的部分。v有邊界的部分可能在曲線內部也可能在曲線外部。有邊界的部分可能在曲線內部也可能在曲線外部。v兩個有共同邊界的有邊界部分可能都在曲線內部，那么穿越兩個有共同邊界的有邊界部分可能都在曲線內部，那么穿越過共享的邊界并不會改變出入特性。過共享的邊界并不會改變出入特性。145 判斷點是否在多邊形內v判斷出現錯誤！判斷出現錯誤！155.2 轉角法v轉角法能夠很精確的判定一個點是否在多邊形內部。

8、需要計轉角法能夠很精確的判定一個點是否在多邊形內部。需要計算多邊形繞點多少次，算多邊形繞點多少次，環(huán)繞數為環(huán)繞數為0 0時，點在多邊形外部時，點在多邊形外部。165.2 轉角法v方法：定義二維平面中某個封閉曲線關于某點的環(huán)繞數。令C(u)=(x(u),y(u)，0u1，且C(0)=C(1)，是二維連續(xù)曲線。P是不在C(u)上的點。v令Cp(u)= C(u)-P為從點P到C(u)的矢量，并且它的單位方向矢量為W(u)=CP(u)/| CP(u)|。 W(u)坐標形式為： W(u)=(cos(u),sin(u)，v其中(u)是正的逆時針方向的角。環(huán)繞的次數(wn)就等于W(u)環(huán)繞S1的次數的整數

9、部分。計算公式為：10)(2121duudwn175.2 轉角法v若曲線C是由頂點V0,V1,Vn=V0構成的多邊形，那么積分可以簡化為計算帶符號的角度的總和。這些角PVi與PVi+1的夾角。因此，如果i=angle(PVi,PVi+1),則v這個公式效率不高，原因在于arccos函數很耗時。v改進：在改進：在S1中任取一點中任取一點Q，因為曲線，因為曲線W(u)環(huán)繞，則可能多次環(huán)繞，則可能多次經過經過Q點。當點。當W(u)按逆時針方向經過按逆時針方向經過Q點時，記為點時，記為+1次，順次，順時針經過時針經過Q點時，記為點時，記為-1次，那么總次數和就是次，那么總次數和就是W環(huán)繞環(huán)繞S1的的次

10、數，剛好等于環(huán)繞數（次數，剛好等于環(huán)繞數（wn）。）。)|arccos(2121101110niiiiiniiPVPVPVPVwn185.2 轉角法v用一個射線用一個射線R R，R R的起點為的起點為P P并向并向Q Q方向延伸。則方向延伸。則R R穿越曲線穿越曲線C C的的交點和交點和W W經過經過Q Q的點一一對應。在數學上，當的點一一對應。在數學上，當R R從從C C的右邊跨到的右邊跨到左邊時，穿越為正，左邊跨到右邊是，穿越為負。左邊時，穿越為正，左邊跨到右邊是，穿越為負。v可以通過可以通過C C的一個法線矢量與方向矢量的一個法線矢量與方向矢量Q Q的數量積的符號來判的數量積的符號來判斷

11、。斷。v當曲線當曲線C C是多邊形時，只需要對是多邊形時，只需要對C C的每一條邊做一次判斷。對的每一條邊做一次判斷。對于射線于射線R R來講，只要測試邊的端點在射線來講，只要測試邊的端點在射線R R的上方還是下方就的上方還是下方就足夠了。足夠了。v如果邊從射線的下方跨到上方，那么穿越如果邊從射線的下方跨到上方，那么穿越+1+1，從上方跨到下，從上方跨到下方，是方，是-1.-1.然后只要把所有的穿越值加起來就得到環(huán)繞數。然后只要把所有的穿越值加起來就得到環(huán)繞數。195.2 轉角法205.2 轉角法v可以不用計算實際的射線和邊的交點，但需要判斷點可以不用計算實際的射線和邊的交點，但需要判斷點P

12、P是否是否在邊的左邊。在邊的左邊。v對于方向向上的邊和向下的邊的判斷與在右邊的規(guī)則不同。對于方向向上的邊和向下的邊的判斷與在右邊的規(guī)則不同。對于方向向上的邊，如果穿過射線到達對于方向向上的邊，如果穿過射線到達P P的右邊，那么的右邊，那么P P是在是在邊的左邊。方向向下的邊如果穿越射線的正方向，那么邊的左邊。方向向下的邊如果穿越射線的正方向，那么P P在在邊的右邊。邊的右邊。21225 判斷點是否在多邊形內v兩種方法比較：v上圖中，重疊區(qū)域的點被環(huán)繞兩次，證明點在多邊形內上圖中，重疊區(qū)域的點被環(huán)繞兩次，證明點在多邊形內部兩次，但射線法測試的結果為點在多邊形外。環(huán)繞法部兩次，但射線法測試的結果為

13、點在多邊形外。環(huán)繞法的結果更加合理。的結果更加合理。23弧長法v弧長法要求多邊形是有向多邊形，一般規(guī)定沿多邊弧長法要求多邊形是有向多邊形，一般規(guī)定沿多邊形的正向，邊的左側為多邊形的內側域。形的正向，邊的左側為多邊形的內側域。v以被測點為圓心作單位圓，將全部有向邊向單位圓以被測點為圓心作單位圓，將全部有向邊向單位圓作徑向投影，并計算其中單位圓上弧長的代數和。作徑向投影，并計算其中單位圓上弧長的代數和。v若代數和為若代數和為0 0，則點在多邊形外部；，則點在多邊形外部；v若代數和為若代數和為2,2,則點在多邊形內部；則點在多邊形內部；v若代數和為若代數和為，則點在多邊形上。，則點在多邊形上。24弧

14、長法v該算法只需該算法只需O(1)O(1)的附加空間，時間復雜度為的附加空間，時間復雜度為O(n)O(n)，但系數很??；最大的優(yōu)點是具有很高的精度，只需但系數很?。蛔畲蟮膬?yōu)點是具有很高的精度，只需做乘法和減法，若針對整數坐標則完全沒有精度問做乘法和減法，若針對整數坐標則完全沒有精度問題。而且實現起來也非常簡單，比轉角法和射線法題。而且實現起來也非常簡單，比轉角法和射線法都要好寫且不易出錯。都要好寫且不易出錯。 25弧長法v將坐標原點平移到被測點將坐標原點平移到被測點P P，這個新坐標系將平面劃分，這個新坐標系將平面劃分為為4 4個象限，對每個多邊形頂點個象限，對每個多邊形頂點P P ，只考慮其

15、所在的象，只考慮其所在的象限，然后按鄰接順序訪問多邊形的各個頂點限，然后按鄰接順序訪問多邊形的各個頂點PiPi，分析，分析PiPi和和Pi+1Pi+1，有下列三種情況，有下列三種情況： （1 1）Pi+1Pi+1在在PiPi的下一象限。此時弧長和加的下一象限。此時弧長和加/2/2；（2 2）Pi+1Pi+1在在PiPi的上一象限。此時弧長和減的上一象限。此時弧長和減/2/2；（3 3）Pi+1Pi+1在在PiPi的相對象限。的相對象限。 首先計算首先計算f=yi+1f=yi+1* *x-xi+1x-xi+1* *y y（叉積），（叉積）， 若若f=0f=0，則點在多邊形上；，則點在多邊形上；

16、若若f0f0f0，弧長和加，弧長和加。最后對算出的代數和和上述的情況一樣判斷即可。最后對算出的代數和和上述的情況一樣判斷即可。26v射線法流程圖射線法流程圖27射線法流程圖解釋射線法流程圖解釋v1.已知點point(x,y)和多邊形Polygon(x1,y1;x2,y2;.xn,yn;)；v2.以point為起點，以無窮遠為終點作平行于X軸的直線line(x,y; -,y)；v3. 循環(huán)取得(for(i=0;in;i+)多邊形的每一條邊side(xi,yi; xi+1,yi+1)，且判斷是否平行于X軸，如果不平行continue，否則，i+；v4. 同時判斷point(x,y)是否在side上

17、，如果是，則返回1(點在多邊形上)，否則繼續(xù)下面的判斷；v5. 判斷線side與line是否有交點，如果有則count+，否則，i+。v6. 判斷交點的總數，如果為奇數則返回0（點在多邊形內），偶數則返回2（點在多邊形外）。28鉛垂線法296.判斷線段是否在多邊形內判斷線段是否在多邊形內 n線段在多邊形內線段在多邊形內 線段的兩個端點在多邊形內線段的兩個端點在多邊形內n兩種情況：兩種情況：u多邊形為凸多邊形：充要條件多邊形為凸多邊形：充要條件u多邊形為凹多邊形：必要條件多邊形為凹多邊形：必要條件定義：定義：n線段內交：兩線段相交且交點不在兩線段的端點。線段內交：兩線段相交且交點不在兩線段的端點

18、。n線段和多邊形的某條邊內交，因為多邊形的邊的左右兩線段和多邊形的某條邊內交，因為多邊形的邊的左右兩側分屬多邊形內外不同部分，所以線段一定會有一部分側分屬多邊形內外不同部分，所以線段一定會有一部分在多邊形外。在多邊形外。 線段和多邊形所有邊都不內交。線段和多邊形所有邊都不內交。v必要條件必要條件1v必要條件必要條件2306.判斷線段是否在多邊形內判斷線段是否在多邊形內v線段和多邊形交于線段的兩端點并不會影響并不會影響線段是否在多邊形內v但是如果多邊形的某個頂點和線段相交，還必須判斷兩相鄰交點之間的線段是否包含于多邊形內部。v （a) (b)v圖2.17線段和多邊形關系舉例316.判斷線段是否在

19、多邊形內判斷線段是否在多邊形內n判斷步驟：判斷步驟：u求出所有線段和多邊形邊的交點;u按照X-Y坐標排序(X坐標小的排在前面，對于X坐標相同的點，Y坐標小的排在前面，這種排序準則也是為了保證水平和垂直情況的判斷正確），這樣相鄰的兩個點就是在線段上相鄰的兩交點;u計算任意相鄰兩點的中點;u如果任意相鄰兩點的中點也在多邊形內，則該線段一定在多邊形內。326.判斷線段是否在多邊形內判斷線段是否在多邊形內v命題命題1 1：如果線段和多邊形的兩相鄰交點如果線段和多邊形的兩相鄰交點P P1 1、P P2 2的中點的中點P P也也在多邊形內，則在多邊形內，則P P1 1、P P2 2之間的所有點都在多邊形內

20、。之間的所有點都在多邊形內。v 證明證明( (反證法）：反證法）：u假設假設P1、P2之間含有不在多邊形內的點Qu由于多邊形是閉合曲線，所以其內外部之間有界，而P1屬于多邊形內部，Q屬于多邊形外部，P屬于多邊形內部，P1-Q-P完全連續(xù)，所以P1Q和QP一定跨越多邊形的邊界，因此在P1、P之間至少還有兩個該線段和多邊形的交點u這和P1、P2是相鄰兩交點矛盾，故命題成立。證畢。 336.判斷線段是否在多邊形內判斷線段是否在多邊形內v由命題1直接可得出推論： 推論推論2 2：v設多邊形和線段PQ的交點依次為P1,P2,Pn，其中Pi和Pi+1是相鄰兩交點，線段PQ在多邊形內的充要條件充要條件是：P

21、、Q在多邊形內且對于i = 1，2，n-1， PiPi+1的中點也在多邊形內。346.判斷線段是否在多邊形內判斷線段是否在多邊形內v程序設計思路：線段的兩端點都在多邊形內判斷線段和多邊形的邊是否內交倘若線段和多邊形的某條邊內交則線段一定在多邊形外如果線段和多邊形的每一條邊都不內交，則線段和多邊形的交點一定是線段的端點或者多邊形的頂點，只要判斷點是否在線段上就可以了。 356.判斷線段是否在多邊形內判斷線段是否在多邊形內v 這個過程中的排序因為交點數目肯定遠小于多邊形的頂點數目n，所以最多是常數級的復雜度，幾乎可以忽略不計。因此算法的時間復雜度也是O(n)。v偽代偽代碼碼36思考v如何判斷線段與

22、多邊形是否相交？377.判斷折線是否在多邊形內判斷折線是否在多邊形內v只要判斷折線的每條線段是否都在多邊形內。v設折線有m條線段，多邊 形有n個頂點，則該算法的時間復雜度為O( mn)。v偽代碼？偽代碼？388.判斷多邊形是否在多邊形內判斷多邊形是否在多邊形內 v只要判斷多邊形的每條邊是否都在多邊形內即可。v判斷一個有m個頂點的多邊形是否在一個有n個頂點的多邊形內復雜度為O(mn)。 v偽代碼？偽代碼？399.判斷矩形是否在多邊形內判斷矩形是否在多邊形內 v將矩形轉化為多邊形，然后再判斷是否在多邊形內。4010.判斷圓是否在多邊形內判斷圓是否在多邊形內 v只要計算圓心到多邊形的每條邊的最短距離

23、，如果該距離大于或等于圓半徑則該圓在多邊形內。v偽代碼？偽代碼？4111.判斷點是否在圓內判斷點是否在圓內 v計算圓心到該點的距離，如果小于或等于半徑則該點在圓內。v偽代碼？偽代碼？4212.判斷線段、折線、矩形、多邊形判斷線段、折線、矩形、多邊形是否在圓內是否在圓內 v圓是凸集，所以只要判斷是否每個頂點都在圓內即可。 v偽代碼？偽代碼？4313.判斷圓是否在圓內判斷圓是否在圓內 v設兩圓為設兩圓為O1、O2半徑分別為半徑分別為r1、r2，要判斷，要判斷O2是否在是否在O1內。內。v先比較先比較r1、r2的大小的大小v如果如果r1r2，則，則O2不可能在不可能在O1內內v如果兩圓心的距離大于如

24、果兩圓心的距離大于r1-r2，則，則 O2不在不在O1內內v反之反之O2在在O1內。內。v偽代碼？偽代碼？4414.計算兩條共線的線段的交點計算兩條共線的線段的交點 設L1是兩條線段中較長的一條，L2是較短的一條v如果L1包含了 L2的兩個端點，則是圖 (d)的情況，兩線段有無窮交點v如果L1只包含L2的一個端點，那么如果L1的某個端點等于被L1包含的 L2的那個端點，則是圖 (c)的情況，這時兩線段只有一個交點v否則就是圖 (b)的情況，兩線段也是有無窮的交點；v如果L1不包含L2的任何端點，則是圖 (a)的情況，這時兩線段沒有交點。 v偽代碼？偽代碼？4515.計算線段或直線與線段的交點計算線段或直線與線段的交點 設一條線段為L0 = P1P2，另一條線段或直線為L1 = Q1Q2，要計算的就是 L0和L1的交點。v第一步：判斷L0和L1是否相交，如果不相交則沒有交點，否則L0和L1一定有交點，下面就將L0和L1都看作直線都看作直線來考慮。v第二步：如果