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

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

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

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

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

a.Disjoint(b)a

∩b=ΦDE-9IM中表示為：201.3空間關(guān)系的判定（2）相接（touches）兩個(gè)幾何體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)：端點(diǎn)有次序之分的線段。如果有向線段p1p2的起點(diǎn)p1在坐標(biāo)原點(diǎn)，則稱為矢量p2。內(nèi)容：矢量加減法矢量的叉積283折線段的拐向判斷方法：根據(jù)矢量叉積的性質(zhì)判斷。對(duì)于有公共端點(diǎn)的線段p0p1和p1p2，通過(guò)計(jì)算(p2-p0)×(p1-p0)的符號(hào)判斷折線的拐向：294判斷點(diǎn)是否在線段上設(shè)點(diǎn)為Q，線段為P1P2，判斷點(diǎn)Q在該線段上的依據(jù)是(Q-P1)×(P2-P1)=0且Q在以P1P2為對(duì)角線的矩形內(nèi)。判斷的實(shí)現(xiàn)：305判斷兩直線相交算法1：（1）快速排除：以兩條直線為端點(diǎn)的矩形不相交。（方法？）若矩形不相交，則直線不會(huì)相交。315判斷兩直線相交（2）跨立試驗(yàn)：如果兩線段相交，則必然跨立對(duì)方。即一直線的兩端點(diǎn)必然位于另一直線兩側(cè)。算法2：

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

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

55弧長(zhǎng)法將坐標(biāo)原點(diǎn)平移到被測(cè)點(diǎn)P，這個(gè)新坐標(biāo)系將平面劃分為4個(gè)象限