GIS算法的計算幾何基礎(chǔ)1

1GIS算法的計算幾何基礎(chǔ)《GIS算法基礎(chǔ)》第二章2本講內(nèi)容1維數(shù)擴展的9交集模型2矢量的概念3折線段的拐向判斷4判斷點是否在線段上5判斷兩線段是否相交6判斷矩形是否包含點7判斷線段、折線、多邊形是否在矩形中8判斷矩形是否在矩形中9判斷圓是否在矩形中10判斷點是否在多邊形內(nèi)31、維數(shù)擴展的9交集模型1.1概述1.2模型介紹1.3空間關(guān)系的判定41.1概述關(guān)系運算：指的是用于檢驗兩個幾何對象的特定的拓撲空間關(guān)系的邏輯方法。幾何對象的拓撲空間關(guān)系在GIS中是一個重要的研究主題。最基本的比較方法：比較兩個幾何對象的內(nèi)部、邊界和外部的交集，并基于交集矩陣產(chǎn)生的實體來對兩個幾何對象空間關(guān)系分類。

普通的拓撲學(xué)對內(nèi)部、外部和邊界的概念進行了定義，適用于在二維空間中對二維對象的空間關(guān)系的定義。51.1概述普通拓撲學(xué)中的概念應(yīng)用于二維空間中的一維或者零維對象時，需要組合拓撲學(xué)的方法。

組合拓撲學(xué)定義：幾何體的邊界由一組較低維數(shù)的幾何體構(gòu)成。點(point)或者多點(multipoint)的邊界為一個空集。非閉合曲線的邊界由其兩個端點組成，閉合曲線的邊界為空。多曲線(multicurve)的邊界為它的組成弧段的奇數(shù)弧段構(gòu)成。多邊形的邊界是其環(huán)的集合。多多邊形(multipolygon)的邊界是組成它的多邊形環(huán)的集合。61.1概述幾何對象域通常認為是拓撲閉合的，組成幾何體內(nèi)部的點不會因為其外部的點被刪除而刪除。組成幾何體外部的點不在幾何體內(nèi)部或者邊界上。4交集模型：最大維數(shù)在一維和二維空間中兩個幾何體的空間關(guān)系研究一般只考慮對比內(nèi)部和邊界的交集，并定義為4交集模型。9交集模型：4交集模型考慮輸入幾何體的外部時就擴展為9交集模型。7拓撲關(guān)系描述——九交模型(Egenhofer,1991)81.1概述9-交空間關(guān)系模型(9-IntersectionModel,9-IM)對于該矩陣中的每一元素，都有“空”與“非空”兩種取值，9個元素總共可產(chǎn)生29=512種情形。B(A)∩B(B)B(A)∩I(B)B(A)∩E(B)I(A)∩B(B)I(A)∩I(B)I(A)∩E(B)E(A)∩B(B)E(A)∩I(B)E(A)∩E(B)9拓撲關(guān)系描述——面/面拓撲關(guān)系(Egenhofer,1991)DisjointMeetOverlapContainEqualCoveredByInsideCover面與面間有效的拓撲關(guān)系共有8個10拓撲關(guān)系描述——線/面拓撲關(guān)系(Egenhofer,1991)LR11LR12LR13LR22LR31LR32LR33LR42LR44LR46LR62LR64LR66LR71LR72LR73LR74LR75LR76線與面間有效的拓撲關(guān)系共有19個11拓撲關(guān)系描述——線/線拓撲關(guān)系(Egenhofer,1991)LL1LL2LL3LL4LL5LL6LL7LL8LL9LL10LL11LL12LL13LL14LL15LL16LL17LL18LL19LL20LL21線與線間有效的拓撲關(guān)系共有33個，這里只給出了21個121.2模型介紹幾何體a，假設(shè)I(a)，B(a)和E(a)分別表示為a的內(nèi)部、邊界和外部。I(a)，B(a)和E(a)任意兩個的交集就生成一個混合維數(shù)的幾何體集合x。假設(shè)dim(x)返回x中幾何體最大維數(shù)。基于維數(shù)擴展的9交集矩陣（DE-9IM，DimensionallyExtended9IntersectionModel

）為：131.2模型介紹如果計算兩個閉合的正多邊形的交集內(nèi)部并確定交集的維數(shù)，就沒有必要分別用幾個幾何體表示兩個多邊形內(nèi)部。每一單元交集的維數(shù)都嚴格受到兩個幾何形體類型的限制。線面關(guān)系中，內(nèi)部——內(nèi)部單元的維數(shù)只能是{-1，1}；面面關(guān)系中，內(nèi)部——內(nèi)部單元的維數(shù)為{-1，2}，這些情況下所要做的只是尋找交集。141.2模型介紹151.2模型介紹空間關(guān)系的描述可以歸納為：兩個幾何體，以表示兩個幾何體DE-9IM結(jié)果合理值集合的模式矩陣形式輸入。只要兩個幾何體的空間關(guān)系符合模式矩陣表示的合理值中的一個，則返回TRUE。161.2模型介紹模式矩陣由9種模式值集合構(gòu)成，一種集合對應(yīng)矩陣一個單元。可能的模式值p為{T，F(xiàn)，*，0，1，2}，對于任何單元的所屬何種交集含義x如下：P=T=>dim(x)∈{0，1，2}，例如，x≠ΦP=F=>dim(x)=-1，例如，x=ΦP=*=>dim(x)∈{-1，0，1，2}，例如，沒關(guān)系P=0=>dim(x)=0P=1=>dim(x)=1P=2=>dim(x)=2171.2模型介紹模式矩陣可以用一個以行號為順序的9個元素的數(shù)組或者列表表示。如下所示代碼用于檢測兩個區(qū)域是否疊置：181.3空間關(guān)系的判定優(yōu)點：基于模式矩陣的空間關(guān)系的確定可以檢測大部分的空間關(guān)系，并且能對特殊的空間關(guān)系進行檢測。缺點：語言抽象化，不人性化。人性化的語言定義的五種用于DE-9IM的空間關(guān)系命名：相離、相接、相交、真包含和疊置。這些定義中P用于表示零維的幾何體（點或者多點），L表示一維幾何體（線或者多線），而A表示二維幾何體（面和多面）。191.3空間關(guān)系的判定（1）相離（Disjoint）假設(shè)兩個幾何體（閉合）a和b：

a.Disjoint(b)a

∩b=ΦDE-9IM中表示為：201.3空間關(guān)系的判定（2）相接（touches）兩個幾何體a和b相接關(guān)系適用于A/A，L/L，L/A，P/A和P/L，而不適用于P/P。其定義如下：211.3空間關(guān)系的判定221.3空間關(guān)系的判定（3）相交（Crosses）相交關(guān)系適用于P/L，P/A，L/L和L/A的情況。231.3空間關(guān)系的判定（4）真包含（Withins）真包含關(guān)系定義如下：241.3空間關(guān)系的判定（5）重置（overlaps）疊置關(guān)系定義的情況為A/A，L/L和P/P。定義如下：251.3空間關(guān)系的判定（6）包含（contains）a.contains(b)b.within(a)(7)相交（Intersects）a.Intersects(b)=!a.Disjoint(b)261.3空間關(guān)系的判定272矢量的概念有向線段（directedsegment)：端點有次序之分的線段。如果有向線段p1p2的起點p1在坐標原點，則稱為矢量p2。內(nèi)容：矢量加減法矢量的叉積283折線段的拐向判斷方法：根據(jù)矢量叉積的性質(zhì)判斷。對于有公共端點的線段p0p1和p1p2，通過計算(p2-p0)×(p1-p0)的符號判斷折線的拐向：294判斷點是否在線段上設(shè)點為Q，線段為P1P2，判斷點Q在該線段上的依據(jù)是(Q-P1)×(P2-P1)=0且Q在以P1P2為對角線的矩形內(nèi)。判斷的實現(xiàn)：305判斷兩直線相交算法1：（1）快速排除：以兩條直線為端點的矩形不相交。（方法？）若矩形不相交，則直線不會相交。315判斷兩直線相交（2）跨立試驗：如果兩線段相交，則必然跨立對方。即一直線的兩端點必然位于另一直線兩側(cè)。算法2：

定義A,B,C,D為二維空間點，則有向線段AB和CD的參數(shù)方程為：325判斷兩直線相交如果AB與CD相交，則：解方程得：設(shè)P為直線AB和CD的交點，則：335判斷兩直線相交如果且，則有向線段AB與CD相交。如果(Bx-AX)(Dy-Cy)-(By-Ay)(Dx-CX)=0，則AB與CD平行。如果(By-Ay)(Dx-Cx)-(Bx-Ax)(Dy-Cy)=0，則AB與CD共線。如果直線AB和CD相交，而交點不位于線段AB和CD之間，則交點位置可通過如下條件判斷：r>1，則P位于有向線段AB的延長線上；r<0，則P位于有向線段BA的延長線上；s>1，則P位于有向線段CD的延長線上；s<0，則P位于有向線段DC的延長線上；346矩形是否包含點只要判斷點的橫坐標與縱坐標是否夾在矩形的左右邊和上下邊之間。357判斷線段、折線、多邊形是否在矩形中矩形是凸集，所以只需判斷所有的端點是否在矩形中。368判斷矩形是否在矩形中比較左右邊界和上下邊界379判斷圓是否在矩形中圓心在矩形中，且圓的半徑小于等于圓心到矩形四邊的距離的最小值。38常用算法：①射線法（奇偶法）②轉(zhuǎn)角法：環(huán)繞數(shù)（多邊形環(huán)繞點的次數(shù)）為0，則點在多邊形外，否則，點在多邊形內(nèi)。10判斷點是否在多邊形內(nèi)3910.1射線法射線法計算從點P開始的射線穿過多邊形邊界的次數(shù)，多邊形的邊界將多邊形內(nèi)部與外部分開。如果結(jié)果為偶數(shù)，則點在多邊形外部，否則，若為奇數(shù)，則點在多邊形內(nèi)部。4010.1射線法必須決定在多邊形邊界上的點是在多邊形內(nèi)部還是外部。一個標準的約定是在左邊界或者下邊界上的點認為是在多邊形內(nèi)部，在右邊界或者上邊界的點認為是在多邊形外部。在這種約定下，如果兩個不同的多邊形共享一個邊，那么在這條邊上的點會在一個多邊形的內(nèi)部而在另一個多邊形的外部。

4110.1射線法一個簡單的射線法是選擇一條水平的、向點P的右側(cè)延伸的、平行于X軸的射線。為了計算總的交點的數(shù)目，算法簡單的遍歷多邊形的所有邊，測試是否穿越邊，穿越時增加交點的數(shù)目。穿越測試必須處理好一些特殊的情形。完全規(guī)則如下：（1）方向向上的邊包括其開始點，不包括其終止點；（2）方向向下的邊不包括其開始點，包括其終止點；（3）水平邊不參加穿越測試；（4）射線和多邊形的邊的交點必須嚴格在點P的右邊。4210.1射線法4310.1射線法射線法的有效性是基于一個簡單的閉合曲線將二維平面分成兩個相連接的部分：有邊界的內(nèi)部和無邊界的外部。曲線必須是簡單的（沒有自相交），否則平面會被分成兩個以上的部分，并且不能保證穿越邊界時不會改變出入特性。對于一個閉合的曲線，可能將二維平面分成多個部分，但是其中只有一個沒有邊界且在曲線外部的部分。有邊界的部分可能在曲線內(nèi)部也可能在曲線外部。兩個有共同邊界的有邊界部分可能都在曲線內(nèi)部，那么穿越過共享的邊界并不會改變出入特性。4410判斷點是否在多邊形內(nèi)判斷出現(xiàn)錯誤！4510.2轉(zhuǎn)角法轉(zhuǎn)角法能夠很精確的判定一個點是否在多邊形內(nèi)部。需要計算多邊形繞點多少次，環(huán)繞數(shù)為0時，點在多邊形外部。4610.2轉(zhuǎn)角法方法：定義二維平面中某個封閉曲線關(guān)于某點的環(huán)繞數(shù)。令C(u)=(x(u),y(u))，0≤u≤1，且C(0)=C(1)，是二維連續(xù)曲線。P是不在C(u)上的點。令Cp(u)=C(u)-P為從點P到C(u)的矢量，并且它的單位方向矢量為W(u)=CP(u)/|CP(u)|。W(u)坐標形式為：W(u)=(cos(u),sin(u))，其中(u)是正的逆時針方向的角。環(huán)繞的次數(shù)(wn)就等于W(u)環(huán)繞S1的次數(shù)的整數(shù)部分。計算公式為：4710.2轉(zhuǎn)角法若曲線C是由頂點V0,V1,…,Vn=V0構(gòu)成的多邊形，那么積分可以簡化為計算帶符號的角度的總和。這些角PVi與PVi+1的夾角。因此，如果i=angle(PVi,PVi+1),則這個公式效率不高，原因在于arccos函數(shù)很耗時。改進：在S1中任取一點Q，因為曲線W(u)環(huán)繞，則可能多次經(jīng)過Q點。當W(u)按逆時針方向經(jīng)過Q點時，記為+1次，順時針經(jīng)過Q點時，記為-1次，那么總次數(shù)和就是W環(huán)繞S1的次數(shù)，剛好等于環(huán)繞數(shù)（wn）。4810.2轉(zhuǎn)角法用一個射線R，R的起點為P并向Q方向延伸。則R穿越曲線C的交點和W經(jīng)過Q的點一一對應(yīng)。在數(shù)學(xué)上，當R從C的右邊跨到左邊時，穿越為正，左邊跨到右邊是，穿越為負。可以通過C的一個法線矢量與方向矢量Q的數(shù)量積的符號來判斷。當曲線C是多邊形時，只需要對C的每一條邊做一次判斷。對于射線R來講，只要測試邊的端點在射線R的上方還是下方就足夠了。如果邊從射線的下方跨到上方，那么穿越+1，從上方跨到下方，是-1.然后只要把所有的穿越值加起來就得到環(huán)繞數(shù)。4910.2轉(zhuǎn)角法5010.2轉(zhuǎn)角法可以不用計算實際的射線和邊的交點，但需要判斷點P是否在邊的左邊。對于方向向上的邊和向下的邊的判斷與在右邊的規(guī)則不同。對于方向向上的邊，如果穿過射線到達P的右邊，那么P是在邊的左邊。方向向下的邊如果穿越射線的正方向，那么P在邊的右邊。515210判斷點是否在多邊形內(nèi)兩種方法比較：上圖中，重疊區(qū)域的點被環(huán)繞兩次，證明點在多邊形內(nèi)部兩次，但射線法測試的結(jié)果為點在多邊形外。環(huán)繞法的結(jié)果更加合理。53弧長法弧長法要求多邊形是有向多邊形，一般規(guī)定沿多邊形的正向，邊的左側(cè)為多邊形的內(nèi)側(cè)域。以被測點為圓心作單位圓，將全部有向邊向單位圓作徑向投影，并計算其中單位圓上弧長的代數(shù)和。若代數(shù)和為0，則點在多邊形外部；若代數(shù)和為2π,則點在多邊形內(nèi)部；若代數(shù)和為π，則點在多邊形上。54弧長法該算法只需O(1)的附加空間，時間復(fù)雜度為O(n)，但系數(shù)很??；最大的優(yōu)點是具有很高的精度，只需做乘法和減法，若針對整數(shù)坐標則完全沒有精度問題。而且實現(xiàn)起來也非常簡單，比轉(zhuǎn)角法和射線法都要好寫且不易出錯。

55弧長法將坐標原點平移到被測點P，這個新坐標系將平面劃分為4個象限