1、第二章 GIS算法的幾何基礎(chǔ),2.1 維數(shù)擴展的9交集模型 2.2 矢量的概念 2.3 折線段的拐向判斷 2.4 判斷點是否在線段上 2.5 判斷兩線段是否相交 2.6 判斷線段和直線是否相交 2.7 判斷矩形是否包含點 2.8 判斷線段、折線、多邊形是否在矩形中 2.9 判斷矩形是否在矩形中 2.10 判斷圓是否在矩形中 2.11 判斷點是否在多邊形內(nèi) 2.12 判斷線段是否在多邊形內(nèi),第二章 GIS算法的幾何基礎(chǔ),2.13 判斷折線是否在多邊形內(nèi) 2.14 判斷多邊形是否在多邊形內(nèi) 2.15 判斷矩形是否在多邊形內(nèi) 2.16 判斷圓是否在多邊形內(nèi) 2.17 判斷點是否在圓內(nèi) 2.18 判斷

2、線段、折線、矩形、多邊形是否在圓內(nèi) 2.19 判斷圓是否在圓內(nèi) 2.20 計算兩條共線的線段的交點 2.21 計算線段或直線與線段的交點 2.22 求線段或直線與圓的交點,2.1 維數(shù)擴展的9交集模型(10-1),模型介紹 設(shè)有現(xiàn)實世界中的兩個簡單實體A、B,B(A)、B(B)表示A、 B的邊界,I(A)、I(B)表示A、B的內(nèi)部,E(A)、E(B)表示A、B外部。Egenhofer(1993)構(gòu)造出一個由邊界、內(nèi)部、外部的點集組成的9交空間關(guān)系模型(9IM)如下: （1）,2.1 維數(shù)擴展的9交集模型(10-2),運用維數(shù)擴展法,將9IM進行擴展,利用點、線、面的邊 界、內(nèi)部、余之間的交集的

3、維數(shù)來作為空間關(guān)系描述的框架。 對于幾何實體的邊界,它是比其更低一維的幾何實體的集合。為此, 點的邊界為空集;線的邊界為線的兩個端點,當線為閉曲線時,線的 邊界為空;面的邊界由構(gòu)成面的所有線構(gòu)成。若設(shè)P為一個點集,定 義點集的求維函數(shù)DIM如下:,2.1 維數(shù)擴展的9交集模型(10-3),利用維數(shù)擴展法,式(1)可擴展為 （2） 根據(jù)DE-9IM,對于點集拓撲空間X,當需要進行關(guān)系判別時,可對矩陣的9元取值進行分析、比較。令C為各單元交的點集,其取值P可能為T,F,*,0,1,2。各個取值的具體含義為： 1)P=T DIM(C)0,1,2,即交集C包含有點、線、面; 2)P=F DIM(C)=

4、-1,即交集C為空;,2.1 維數(shù)擴展的9交集模型(10-4),3)P=* DIM(C)-1,0,1,2,即兩目標交集既有點、線、面,又含有某些部分的交為空的情形,該情況在關(guān)系判別時,一般不予以考慮; 4)P=0 DIM(C)=0; 5)P=1 DIM(C)=1; 6)P=2 DIM(C)=2。,2.1 維數(shù)擴展的9交集模型(10-5),式(2)中各元素通過取值T,F,*,0,1,2,可產(chǎn)生的 情形為 =10077696種,關(guān)系非常復(fù)雜,通過對大量的空間關(guān) 系進行歸納和分類,得出5種基本的空間關(guān)系:相離關(guān)系(Disjoint)、相接關(guān)系(Touch)、相交關(guān)系(Cross)、真包含關(guān)系(Wit

5、hin)、疊置關(guān)系(Overlap),并將這5種關(guān)系定義為空間關(guān)系的最小集,其特征為: 1) 相互之間不能進行轉(zhuǎn)化; 2) 能覆蓋所有的空間關(guān)系模式; 3) 能應(yīng)用于同維與不同維的幾何目標; 4) 每一種關(guān)系對應(yīng)于唯一的DE-9IM矩陣; 5) 任何其它的DE-9IM關(guān)系可以通過用這5種基本關(guān)系進行表達。 另外,為了用戶的使用方便,還定義幾個基本的空間關(guān)系即: 相等(Equal)、包含(Contain)、覆蓋(Cover)、和被覆 蓋(CoverdBy)。,2.1 維數(shù)擴展的9交集模型(10-6),在地理信息系統(tǒng)中,空間數(shù)據(jù)具有屬性特征、空間特 征和時間特征,基本數(shù)據(jù)類型包括屬性數(shù)據(jù)、幾何數(shù)據(jù)

6、和空 間關(guān)系數(shù)據(jù)。作為基本數(shù)據(jù)類型的空間關(guān)系數(shù)據(jù)主要指點/點、點/線、點/面、線/線、線/面、面/面之間的相互關(guān)系。利用DE-9IM方法,識別規(guī)則為:（1）相離：A.Disjoint(B) A.Relate(B,“FF*FF*”)（2）相接：A.Touch(B) A.Relate(B,“FT*”) OR A.Relate(B,“F*T*”) OR A.Relate(B,“F*T*”) （如圖） （3）相交：A.Cross(B) A.Relate(B,“P*T*”), Case A,BL,P=0,Else P=T （如圖）,2.1 維數(shù)擴展的9交集模型(10-7),(4)疊置：A.Overlap

7、(B) A.Relate(B,“T*T*T*”), Case A,BL,P=0,Else P=T （如圖）(5)真包含：A.Within(B) A.Relate(B,“TF*F*F*”)（如圖）(6)包含：A.Contain(B) B.In(A)(7)相等：A.Equal(B) A.Relate(B,“PF*FP*”),P=0,1,2(8)覆蓋：A.Cover(B) (I(A)I(B)=I(A) And (E(A)E(B)(9)被覆蓋：A.CoveredBy(B)B.Cover(A),2.1 維數(shù)擴展的9交集模型(10-8),2.1 維數(shù)擴展的9交集模型(10-9),2.1 維數(shù)擴展的9交集模

8、型(10-10),DE-9IM模版分析,2.2 矢量的概念(3-1),一、矢量的概念 如果一條線段的端點是有次序之分的，我們把這種線段 稱為有向線段。如果有向線段P1P2的起點P1在坐標原點，我們可以把它成為矢量P2(如圖)。,2.2 矢量的概念(3-2),二、矢量加減法 設(shè)二維矢量P=（x1,y1），Q=(x2,y2),則：,2.2 矢量的概念(3-3),三、矢量叉積 設(shè)二維矢量P=（x1,y1），Q=(x2,y2),則矢量叉積定義為： 由(0,0) 、P、Q和PQ所組成的平行四邊形的帶符號的面積，即：PQ=x1y2-x2y1 其結(jié)果是一個標量。顯然有性質(zhì)： PQ=-(QP)和P（-Q）=-

9、(PQ) 叉積的一個非常重要的性質(zhì)是可以通過它的符號判斷兩矢量相互之間的順逆時針關(guān)系： (1)若PQ 0，則P在Q的順時針方向； (2)若PQ 0，則P在Q的逆時針方向； (3)若PQ = 0，則P與Q共線，但可能同向也可能反向。,2.3 折線段的拐向判斷,折線段的拐向判斷方法可以直接由矢量叉積的性質(zhì)推出。 對于有公共端點的線段p0p1和p1p2，通過計算(p2 - p0)(p1 - p0) 的符號便可以確定折線段的拐向： (1)若(p2 - p0) (p1 - p0) 0,則p0p1在p1點拐向右側(cè)后得到p1p2。 (2)若(p2 - p0) (p1 - p0) 0,則p0p1在p1點拐向左

10、側(cè)后得到p1p2。 (3)若(p2 - p0) (p1 - p0) = 0,則p0、p1、p2三點共線。 具體情況可參考下圖：,p0,p1,p2,p1,p2,p0,p0,p1,p2,(2),(1),(3),2.4判斷點是否在線段上,設(shè)點為Q，線段為P1P2，判斷點Q在該線段上的依據(jù)是：(Q-P1)(P2-P1)=0且Q在以P1，P2為對角 頂點的矩形內(nèi)。前者保證Q點在直線P1P2上，后者是保證Q點不 在線段P1P2的延長線或反向延長線上，對于這一步驟的判斷可 以用以下過程實現(xiàn)： ON-SEGMENT(pi,pj,pk) ifmin(xi,xj)=xk=max(xi,xj)andmin(yi,y

11、j)=yk=max(yi,yj) thenreturntrue; elsereturnfalse; 特別要注意的是，由于需要考慮水平線段和垂直線段兩種特殊情況，min(xi,xj)=xk=max(xi,xj)和min(yi,yj)=yk=max(yi,yj)兩個條件必須同時滿足才能返回真值。,2.5 判斷兩線段是否相交 (3-1),我們分兩步確定兩條線段是否相交： (1)快速排斥試驗 設(shè)以線段P1P2為對角線的矩形為R，設(shè)以線段Q1Q2為對角線的矩形為T，如果R和T不相交，顯然兩線段不會相交。 (2)跨立試驗 如果兩線段相交，則兩線段必然相互跨立對方。若P1P2跨立 Q1Q2，則矢量(P1-Q

12、1)和(P2-Q1)位于矢量(Q2-Q1)的兩側(cè)，即 (P1-Q1)(Q2-Q1)*(P2-Q1)(Q2-Q1)0。,！,2.5 判斷兩線段是否相交(3-2),當(P1-Q1)(Q2-Q1)=0時，說明(P1-Q1)和(Q2-Q1)共線，但是因為已經(jīng)通過快速排斥試驗，所以P1一定在線段Q1Q2上； 當(Q2-Q1)(P2-Q1)=0時，說明P2一定在線段 Q1Q2上。所以判斷P1P2跨立Q1Q2的依據(jù)是： (P1-Q1)(Q2-Q1)*(Q2-Q1)(P2-Q1)=0 (3) 同理判斷Q1Q2跨立P1P2的依據(jù)是： (Q1-P1)(P2-P1)*(P2-P1)(Q2-P1)=0。 具體情況如下

13、圖所示：,2.5 判斷兩線段是否相交(3-3),通 過 快 速 排 斥 試 驗,通過快速排斥試驗,未通過快速排斥試驗,未 通 過 快 速 排 斥 試 驗,R,P1,P2,Q1,Q2,2.6 判斷線段和直線是否相交,有了上面的基礎(chǔ)，這個算法就很容易了。如果線段P1P2 和直線Q1Q2相交，則P1P2跨立Q1Q2，即： (P1-Q1)(Q2-Q1)*(Q2-Q1)(P2-Q1)=0。 2.7 判斷矩形是否包含點 只要判斷該點的橫坐標和縱坐標是否夾在矩形的左右邊和上下 邊之間。 2.8 判斷線段、折線、多邊形是否在矩形中 因為矩形是個凸集，所以只要判斷所有端點是否 都在矩形中就可以了。,2.9 判斷

14、矩形是否在矩形中,只要比較左右邊界和上下邊界就可以了。 2.10 判斷圓是否在矩形中 很容易證明，圓在矩形中的充要條件是：圓心在矩形中且圓的 半徑小于等于圓心到矩形四邊的距離的最小值。,2.11 判斷點是否在多邊形內(nèi),判斷點P是否在多邊形中是計算幾何中一個非?；镜?十分重要的算法。以點P為端點，向左方作射線L，由于多邊形 是有界的，所以射線L的左端一定在多邊形外，考慮沿著L從無窮遠 處開始自左向右移動，遇到和多邊形的第一個交點的時候，進入到 了多邊形的內(nèi)部，遇到第二個交點的時候，離開了多邊形，所 以很容易看出當L和多邊形的交點數(shù)目C是奇數(shù)的時候，P在多邊形 內(nèi)，是偶數(shù)的話P在多邊形外。 但

15、是有些特殊情況要加以考慮。如圖下圖(a)(b)(c)(d)所示。 在圖(a)中，L和多邊形的頂點相交，這時候交點只能計算一個；在 圖(b)中， L和多邊形頂點的交點不應(yīng)被計算；在圖(c)和(d)中， L和多邊形的一條邊重合，這條邊應(yīng)該被忽略不計。如果L和多邊形 的一條邊重合，這條邊應(yīng)該被忽略不計。,為了統(tǒng)一起見，我們在計算射線L和多邊形的交點的時候，1。對于多邊形的水平邊不作考慮；2。對于多邊形的頂點和L相交的情況，如果該頂點是其所屬的邊上縱坐標較大的頂點，則計數(shù)，否則忽略；3。對于P在多邊形邊上的情形，直接可判斷P屬于多邊行。由此得出算法的偽代碼如下：,2.11 判斷點是否在多邊形內(nèi),cou

16、nt0;以P為端點，作從右向左的射線L;for多邊形的每條邊sdoifP在邊s上thenreturntrue;ifs不是水平的thenifs的一個端點在L上if該端點是s兩端點中縱坐標較大的端點thencountcount+1elseifs和L相交thencountcount+1;ifcountmod2=1thenreturntrue;elsereturnfalse; 其中做射線L的方法是：設(shè)P的縱坐標和P相同，橫坐標為正 無窮大（很大的一個正數(shù)），則P和P就確定了射線L。 判斷點是否在多邊形中的這個算法的時間復(fù)雜度為O(n)。,另外還有一種算法是用帶符號的三角形面積之和與多 邊形面積進行比較

17、，這種算法由于使用浮點數(shù)運算所以會帶 來一定誤差，不推薦大家使用。,2.11 判斷點是否在多邊形內(nèi),2.12 判斷線段是否在多邊形內(nèi)(5-1),線段在多邊形內(nèi)的一個必要條件是線段的兩個端點都在 多邊形內(nèi)，但由于多邊形可能為凹，所以這不能成為判斷的充 分條件。如果線段和多邊形的某條邊內(nèi)交（兩線段內(nèi)交是指兩 線段相交且交點不在兩線段的端點），因為多邊形的邊的左右 兩側(cè)分屬多邊形內(nèi)外不同部分，所以線段一定會有一部分在多 邊形外(見圖a)。于是我們得到線段在多邊形內(nèi)的第二個必要條 件：線段和多邊形的所有邊都不內(nèi)交。 線段和多邊形交于線段的兩端點并不會影響線段是否在多邊形 內(nèi)；但是如果多邊形的某個頂點和

18、線段相交，還必須判斷兩相鄰交 點之間的線段是否包含于多邊形內(nèi)部（反例見圖b)。,2.12 判斷線段是否在多邊形內(nèi)(5-2),因此我們可以先求出所有和線段相交的多邊形的頂點， 然后按照X-Y坐標排序(X坐標小的排在前面，對于X坐標相同的 點，Y坐標小的排在前面，這種排序準則也是為了保證水平和垂 直情況的判斷正確)，這樣相鄰的兩個點就是在線段上相鄰的兩交 點，如果任意相鄰兩點的中點也在多邊形內(nèi)，則該線段一定在多 邊形內(nèi)。,2.12 判斷線段是否在多邊形內(nèi)(5-3),證明如下：命題1:如果線段和多邊形的兩相鄰交點P1，P2的中點P也在多邊 形內(nèi)，則P1,P2之間的所有點都在多邊形內(nèi)。 證明：假設(shè)P1

19、,P2之間含有不在多邊形內(nèi)的點，不妨設(shè)該點為Q， 在P1,P之間，因為多邊形是閉合曲線，所以其內(nèi)外部之間有 界，而P1屬于多邊行內(nèi)部，Q屬于多邊性外部，P屬于多邊性內(nèi) 部，P1-Q-P完全連續(xù)，所以P1Q和QP一定跨越多邊形的邊界， 因此在P1,P之間至少還有兩個該線段和多邊形的交點，這和P1P2 是相鄰兩交點矛盾，故命題成立。證畢。,2.12 判斷線段是否在多邊形內(nèi)(5-4),由命題1直接可得出推論： 推論2：設(shè)多邊形和線段PQ的交點依次為P1,P2,Pn，其中Pi和 Pi+1是相鄰兩交點，線段PQ在多邊形內(nèi)的充要條件是：P，Q在 多邊形內(nèi)且對于i=1,2,n-1，Pi,Pi+1的中點也在多

20、邊 形內(nèi)。 在實際編程中，沒有必要計算所有的交點，首先應(yīng)判斷線段 和多邊形的邊是否內(nèi)交，倘若線段和多邊形的某條邊內(nèi)交則線段一 定在多邊形外；如果線段和多邊形的每一條邊都不內(nèi)交，則線段和 多邊形的交點一定是線段的端點或者多邊形的頂點，只要判斷點是 否在線段上就可以了。,(5-5) 至此我們得出算法如下： if線端PQ的端點不都在多邊形內(nèi)thenreturnfalse; else 點集pointSet初始化為空;for多邊形的每條邊sdoif線段的某個端點在s上then將該端點加入pointSet;elseifs的某個端點在線段PQ上then將該端點加入pointSet;elseifs和線段PQ相

21、交/*這時候已經(jīng)可以肯定是內(nèi)交了*/ thenreturnfalse; else 將pointSet中的點按照X-Y坐標排序; forpointSet中每兩個相鄰點pointSeti, pointSeti+1 do ifpointSeti,pointSeti+1的 中點不在多邊形中 thenreturnfalse; else returntrue,這個過程中的排序因為交點數(shù)目肯定遠小于多邊形的頂點數(shù)目n，所以最多是常數(shù)級的復(fù)雜度，幾乎可以忽略不計。因此算法的時間復(fù)雜度也是O(n)。,2.13 判斷折線是否在多邊形內(nèi),只要判斷折線的每條線段是否都在多邊形內(nèi)即可。設(shè)折 線有m條線段，多邊形有n個頂

22、點，則該算法的時間復(fù)雜度為 O(mn)。 2.14 判斷多邊形是否在多邊形內(nèi) 只要判斷多邊形的每條邊是否都在多邊形內(nèi)即可。判斷一 個有m個頂點的多邊形是否在一個有n個頂點的多邊形內(nèi)復(fù)雜度為 O(mn)。,2.15 判斷矩形是否在多邊形內(nèi),將矩形轉(zhuǎn)化為多邊形，然后再判斷是否在多邊形內(nèi)。 2.16 判斷圓是否在多邊形內(nèi) 只要計算圓心到多邊形的每條邊的最短距離，如果該距離 大于等于圓半徑則該圓在多邊形內(nèi)。計算圓心到多邊形每條邊最 短距離的算法在后文闡述。 2.17 判斷點是否在圓內(nèi) 計算圓心到該點的距離，如果小于等于半徑則該點在圓內(nèi)。 2.18 判斷線段、折線、矩形、多邊形 是否在圓內(nèi) 因為圓是凸集

23、，所以只要判斷是否每個頂點都在 圓內(nèi)即可。,2.19 判斷圓是否在圓內(nèi),設(shè)兩圓為O1,O2，半徑分別為r1,r2，要判斷O2是否在O1 內(nèi)。先比較r1，r2的大小，如果r1r2則O2不可能在O1內(nèi)；否則如 果兩圓心的距離大于r1-r2，則O2不在O1內(nèi)；否則O2在O1內(nèi)。,2.20 計算兩條共線的線段的交點(2-1),對于兩條共線的線段，它們之間的位置關(guān)系有下圖所示的 幾種情況。圖(a)中兩條線段沒有交點；圖(b)和(d)中兩條線段 有無窮焦點；圖(c)中兩條線段有一個交點。 設(shè)line1是兩條線段中較長的一條，line2是較短的一條. (1)如果line1包含了line2的兩個端點，則是圖(

24、d)的情況，兩線 段有無窮交點； (2)如果line1只包含line2的一個端點，那么如果line1的某個端 點等于被line1包含的line2的那個端點，則是圖(c)的情況，這時 兩線段只有一個交點，否則就是圖(b)的情況，兩線段也是有無窮 的交點; (3)如果line1不包含line2的任何端點，則是圖(a)的情況，這時兩 線段沒有交點。,2.20 計算兩條共線的線段的交點(2-2),2.21 計算線段或直線與線段的交點(4-1),設(shè)一條線段為L0=P1P2，另一條線段或直線為L1=Q1Q2，要 計算的就是L0和L1的交點。步驟如下： 1.首先判斷L0和L1是否相交（方法已在前文討論過），

25、如果 不相交則沒有交點，否則說明L0和L1一定有交點，下面就將L0和L1 都看作直線來考慮。 2.如果P1和P2橫坐標相同，即L0平行于Y軸 a)若L1也平行于Y軸， i.若P1的縱坐標和Q1的縱坐標相同，說明L0和L1共線，假 如L1是直線的話他們有無窮的交點，假如L是線段的話可用“計 算兩條共線線段的交點”的算法求他們的交點（該方法在前文 已討論過）；ii.否則說明L0和L1平行，他們沒有交點； b)若L1不平行于Y軸，則交點橫坐標為P1的橫坐標，代入 到L1的直線方程中可以計算出交點縱坐標；,2.21 計算線段或直線與線段的交點(4-2),3.如果P1和P2橫坐標不同，但是Q1和Q2橫坐標相同，即L1 平行于Y軸，則交點橫坐標為Q1的橫坐標，代入到L0的直線方程 中可以計算出交點縱坐標； 4.如果P1和P2縱坐標相同，即L0平行于X軸 a)若L1也平行于X軸， i.若P1的橫坐標和Q1的橫坐標相同，說明L0和L1共線，假如L1是直線的話他們有無窮的交點，假如L1是線段的話可用計算兩條共線線段的交點的算法求他們的交點（該方法在前文已討論過）；ii.否則說明L0和L1平行，他們沒有交點； b)若L1不平行于X軸，則交點縱坐標為P1的縱