第五章空間分析技術(shù)

1、第五章 空間查詢與空間分析第二節(jié)第二節(jié) 緩沖區(qū)分析緩沖區(qū)分析第三節(jié)第三節(jié) 空間疊置分析空間疊置分析第一節(jié)第一節(jié) 空間查詢空間查詢第三節(jié)第三節(jié) 空間網(wǎng)絡(luò)分析空間網(wǎng)絡(luò)分析一、空間分析的概念 1.空間分析的定義 2.空間分析的研究對象 3.空間分析的研究目標(biāo)空間分析(spatial analysis)是地理學(xué)的精髓，是為解答地理空間問題而進(jìn)行的數(shù)據(jù)分析與挖掘。目前，比較典型的空間分析定義有多種。 定義：是集空問數(shù)據(jù)分析和空間模擬于一體的技術(shù)，通過地理計算和空間表達(dá)挖掘潛在空間信息，以解決實際問題的過程?？臻g分析主要通過對空問數(shù)據(jù)和空間模型的聯(lián)合分析來挖掘空間目標(biāo)的潛在信息?？臻g目標(biāo)是空間分析的具體研

2、究對象。 1)認(rèn)知。有效獲取空間數(shù)據(jù)，并對其進(jìn)行科學(xué)的組織描述，利用數(shù)據(jù)再現(xiàn)事物本身。 例如繪制風(fēng)險圖。 2)解釋。理解和解釋地理空間數(shù)據(jù)的背景過程，認(rèn)識事件的本質(zhì)規(guī)律。 例如住房價格中的地理鄰居效應(yīng)。 3)預(yù)報。在了解、掌握事件發(fā)生現(xiàn)狀與規(guī)律的前提下，運(yùn)用有關(guān)預(yù)測模型對未來的狀況做出預(yù)測，例如傳染病的爆發(fā)。 4)調(diào)控。對地理空間發(fā)生的事件進(jìn)行調(diào)控，例如合理分配資源。 一、空間分析的概念 4.GIS與空間分析 目前，空間分析一般采用專業(yè)分析模型與GIS集成方式。 GIS軟件與空間分析軟件相結(jié)合的方式可分為兩種： 緊耦合，即把空間分析模塊作為一個高級應(yīng)用模塊嵌入GIS軟件包中，GIS不僅可以為空

3、間分析提供圖形顯示功能，而且GIS中的有關(guān)數(shù)據(jù)直接參與空間分析計算。 這種方式可以為用戶提供方便、全面、有效的使用功能，但造價高，實現(xiàn)周期長。松耦合，即在兩個相對獨(dú)立的GIS軟件和空間分析軟件之間增加數(shù)據(jù)交換接口，使空間分析數(shù)據(jù)及相關(guān)的影響因素和空間分析結(jié)果能夠在GIS中以各種簡單的或復(fù)雜的圖形方式顯示出來。 這種方式適用于短期且費(fèi)用較小的情況。 一、空間分析的概念 5.GIS環(huán)境下空間分析框架 一般性空間分析框架(右圖) (Anselin L,1998) 空間分析類型： A. Goodchild將空間分析分為兩大類： 產(chǎn)生式分析 (product model)， 通過這些分析可以獲取新的信息

4、， 尤其是綜合信息 咨詢式分析 (query model)， 旨在回答用戶的一些問題。 一、空間分析的概念 5.GIS環(huán)境下空間分析框架 B. 從GIS應(yīng)用角度看，空間分析大致可以歸納為如下兩大類： 基于點、線、面基本地理要素的空間分析，通過空間信息查詢與量測、緩沖區(qū)分析、疊置分析、網(wǎng)絡(luò)分析、地統(tǒng)計分析等空間分析方法挖掘出新的信息 地理問題模擬，解決應(yīng)用領(lǐng)域?qū)臻g數(shù)據(jù)處理與輸出的特殊要求，地理實體和空間關(guān)系通過專業(yè)模型得到簡化和抽象，而系統(tǒng)則通過模型進(jìn)行深入分析操作。 C.以空間數(shù)據(jù)及其特點作為框架來構(gòu)造空間分析的體系，主要考慮不 同數(shù)據(jù)之間的空間關(guān)系，將空間分析界定為以下五個方面： 空間位置

5、分析 空間分布分析 空間形態(tài)分析 空間關(guān)系分析 空間相關(guān)分析。 第第1節(jié)節(jié) 空間查詢空間查詢空間數(shù)據(jù)庫查詢條件屬性限制空間拓?fù)湎拗贫呓Y(jié)合GIS軟件查詢結(jié)果統(tǒng)計結(jié)果：圖、表、文字新圖層新的屬性域添加到屬性數(shù)據(jù)庫 圖形-屬性空間查詢語言閃爍、顏色等明顯表示 查詢方式空間查詢: 在GIS中根據(jù)一定的圖形條件或?qū)傩詶l件或兩者的結(jié)合條件,檢索出對應(yīng)的空間對象的屬性或圖形的一種工具。 一、空間查詢定義 二、空間查詢的方式 給出圖形信息：如鼠標(biāo)點取，拉框等方式。 1）檢索其相應(yīng)屬性； 2）檢索其空間拓?fù)潢P(guān)系 給出屬性特征條件 1）檢索對應(yīng)的空間實體 2）查詢屬性 單純查詢：單純地查詢屬性，或只查詢空間拓?fù)?/p>

6、關(guān)系。 聯(lián)合查詢：將空間數(shù)據(jù)與屬性數(shù)據(jù)聯(lián)合查詢。第第1 1 節(jié)節(jié) 空間查詢空間查詢 三、空間查詢的種類 幾何參數(shù)查詢 包括點的位置坐標(biāo)，兩點間的距離，一個或一段線目標(biāo)的長度， 一個面目標(biāo)的周長或面積等。 實現(xiàn)：查詢屬性庫或空間計算 空間定位查詢 給定一個點或一個幾何圖形，檢索該圖形范圍內(nèi)的空間對象及其屬性。 1）按點查詢： 給定一個鼠標(biāo)點，查詢離它最近的對象及屬性-點的捕捉。 2）開窗查詢-按矩形、圓、多邊形查詢 分為該窗口包含和穿過的區(qū)別。 實現(xiàn)：根據(jù)空間索引，檢索哪些對象可能位于該窗口， 然后根據(jù)點、線、面在查詢開窗內(nèi)的判別計算， 檢索到目標(biāo)。-空間運(yùn)算方法 第第1 1 節(jié)節(jié) 空間查詢空間

7、查詢 三、空間查詢的種類 屬性查詢 1） 查找 僅選擇一個屬性表，給定一個屬性值，找出對 應(yīng)的屬性記錄或圖形。在屏幕上已有一個屬性 表，用戶任意點取記錄，對應(yīng)的圖形以高亮顯示。 實現(xiàn)：執(zhí)行數(shù)據(jù)庫查詢語言，找到滿足 要求的記錄，得到它的目標(biāo)標(biāo)識， 再通過目標(biāo)標(biāo)識在圖形數(shù)據(jù)文件 中找到對應(yīng)的空間對象，并顯示出來。 第第1 1 節(jié)節(jié) 空間查詢空間查詢 三、空間查詢的種類 屬性查詢 2）SQL查詢 實現(xiàn)：交互式選擇各項，輸入后，系統(tǒng)再轉(zhuǎn)換為標(biāo)準(zhǔn)的SQL，由數(shù)據(jù)庫系統(tǒng)執(zhí)行或ODBC C語言執(zhí)行，得到結(jié)果，提取目標(biāo)標(biāo)識，在圖形文件中找到空間對象，并顯示。 3）擴(kuò)展SQL 空間數(shù)據(jù)查詢語言在數(shù)據(jù)庫查詢語言上

8、加入空間關(guān)系查詢。 空間數(shù)據(jù)類型 增加 空間操作算子 空間概念 主要優(yōu)點是：保留了SQL的風(fēng)格，便于熟悉SQL的用戶的掌握，通用性較好，易于與關(guān)系數(shù)據(jù)庫連接。第第1 1 節(jié)節(jié) 空間查詢空間查詢 鄰近度（Proximity）描述了地理空間中兩個地物距離相近的程度，其確定是空間分析的一個重要手段。 所謂緩沖區(qū)就是地理空間目標(biāo)的一種影響范圍或服務(wù)范圍。從數(shù)學(xué)的角度看，緩沖區(qū)分析的基本思想是給定一個空間對象或集合，確定它們的鄰域，鄰域的大小由鄰域半徑R決定。因此對象Oi的緩沖區(qū)定義為： ROxdxBii,:第2節(jié) 緩沖區(qū)分析 即對象 Oi 的半徑為R的緩沖區(qū)為距Oi的距離d小于R的全部點的集合。d一般

9、是最小歐氏距離，但也可是其它定義的距離。對于對象集合其半徑為R的緩沖區(qū)是各個對象緩沖區(qū)的并，即：niOOi, 2 , 1: niiBB1第2節(jié) 緩沖區(qū)分析第2節(jié) 緩沖區(qū)分析 另外還有一些特殊形態(tài)的緩沖區(qū)，如點對象有三角形，矩形和圈形等，對于線對象有雙側(cè)對稱，雙側(cè)不對稱或單側(cè)緩沖區(qū)，對于面對象有內(nèi)側(cè)和外側(cè)緩沖區(qū)。這些適合不同應(yīng)用要求的緩沖區(qū)，盡管形態(tài)特殊，但基本原理是一致的。 緩沖區(qū)計算的基本問題是雙線問題。雙線問題有很多另外的名稱，如圖形加粗，加寬線，中心線擴(kuò)張等，它們指的都是相同的操作。角分線法凸角圓弧法第2節(jié) 緩沖區(qū)分析 角平分線法 ：角分線法的缺點是難以最大限度保證雙線的等寬性，尤其是在

10、凸側(cè)角點在進(jìn)一步變銳時，將遠(yuǎn)離軸線頂點。根據(jù)上圖，遠(yuǎn)離情況可由下式表示： 2sin BRd 第2節(jié) 緩沖區(qū)分析 凸角圓弧法：在軸線首尾點處，作軸線的垂線并按雙線和緩沖區(qū)半徑截出左右邊線起止點；在軸線其它轉(zhuǎn)折點處，首先判斷該點的凸凹性，在凸側(cè)用圓弧彌合，在凹側(cè)則用前后兩鄰邊平行線的交點生成對應(yīng)頂點。這樣外角以圓弧連接，內(nèi)角直接連接，線段端點以半圓封閉。如圖所示。 第2節(jié) 緩沖區(qū)分析 該算法非常重要的一環(huán)是折點凸凹性的自動判斷。此問題可轉(zhuǎn)化為兩個矢量的叉積：把相鄰兩個線段看成兩個矢量，其方向取坐標(biāo)點序方向。若前一個矢量以最小角度掃向第二個矢量時呈逆時針方向，則為凸頂點，反之為凹頂點。具體算法過程如

11、下：由矢量代數(shù)可知，矢量AB，BC可用其端點坐標(biāo)差表示（9-9）： SABCabyxABABaaYYXXAB,yxBCBCbbYYXXBC, ABBCBCAByxyxYYXXYYXXabbabaBCABS第2節(jié) 緩沖區(qū)分析3.緩沖區(qū)分析矢量代數(shù)叉積遵循右手法則，即當(dāng)ABC呈逆時針方向時，S為正，否則為負(fù)。若S0，則ABC呈逆時針，頂點為凸；若S0，則ABC呈順時針，頂點為凹；若S=0，則ABC三點共線。SABCab第2節(jié) 緩沖區(qū)分析第2節(jié) 緩沖區(qū)分析 但當(dāng)計算形狀比較復(fù)雜的對象或多個對象集合的緩沖區(qū)時，就不得不處理邊線自相交的情況。當(dāng)軸線的彎曲空間不容許雙線的邊線無壓蓋地通過時，就會產(chǎn)生若干個

12、自相交多邊形。左圖給出一個緩沖區(qū)邊線自相交的例子。第2節(jié) 緩沖區(qū)分析第2節(jié) 緩沖區(qū)分析 自相交多邊形分為兩種情況：島嶼多邊形和重疊多邊形。島嶼多邊形是緩沖區(qū)邊線的有效組成部分；重疊多邊形不是緩沖區(qū)邊線的有效組成，不參與緩沖區(qū)邊線的最終重構(gòu)。對于島嶼多邊形和重疊多邊形的自動判別方法，首先定義軸線坐標(biāo)點序為其方向，緩沖區(qū)雙線分成左右邊線，左右邊線自相交多邊形的判別情形恰好對稱。對于左邊線，島嶼自相交多邊形呈逆時針方向，重疊自相交多邊形呈順時針方向；對于右邊線，島嶼多邊形呈順時針方向，重疊多邊形呈逆時針方向。 第2節(jié) 緩沖區(qū)分析緩沖區(qū)分析實例圖例：建立的緩沖區(qū)醫(yī)院道路第2節(jié) 緩沖區(qū)分析第3節(jié) 空間疊

13、置分析空間疊置分析(spatial overlay analysis)，又稱疊置分析，是指在統(tǒng)一的空間參照系統(tǒng)條件下，將同一地區(qū)的兩組或兩組以上的要素 (地圖)進(jìn)行疊置，產(chǎn)生新的特征(新的空間圖形或空 間位置上的新屬性的過程)的分析方法。 疊置分析是地理信息系統(tǒng)最常用的提取空間隱含信息的手段之一。 根據(jù)GIS數(shù)據(jù)結(jié)構(gòu)的不同，分為下列矢量疊置和柵格疊置兩類分析方法。 4.疊加分析 疊加分析是地理信息系統(tǒng)最常用的提取空間隱含信息的手段之一。該方法源于傳統(tǒng)的透明材料疊加，即將來自不同的數(shù)據(jù)源的圖紙繪于透明紙上，在透光桌上將其疊放在一起，然后用筆勾出感興趣的部分提取出感興趣的信息。地理信息系統(tǒng)的疊加分

14、析是將有關(guān)主題層組成的數(shù)據(jù)層面，進(jìn)行疊加產(chǎn)生一個新數(shù)據(jù)層面的操作，其結(jié)果綜合了原來兩層或多層要素所具有的屬性。疊加分析不僅包含空間關(guān)系的比較，還包含屬性關(guān)系的比較。地理信息系統(tǒng)疊加分析可以分為以下幾類：視覺信息疊加、點與多邊形疊加、線與多邊形疊加、多邊形疊加、柵格圖層疊加。 第3節(jié) 空間疊置分析4.疊加分析疊加分析 視覺信息疊加是將不同側(cè)面的信息內(nèi)容疊加顯示在結(jié)果圖件或屏幕上，以便研究者判斷其相互空間關(guān)系，獲得更為豐富的空間信息。地理信息系統(tǒng)中視覺信息疊加包括以下幾類：點狀圖，線狀圖和面狀圖之間的疊加顯示。面狀圖區(qū)域邊界之間或一個面狀圖與其他專題區(qū)域邊界之間的疊加。遙感影象與專題地圖的疊加。專

15、題地圖與數(shù)字高程模型（DEM）疊加顯示立體專題圖。 視覺信息疊加不產(chǎn)生新的數(shù)據(jù)層面，只是將多層信息復(fù)合顯示，便于分析。一、視覺信息疊加第3節(jié) 空間疊置分析第3節(jié) 空間疊置分析4.疊加分析疊加分析 點與多邊形疊加，實際上是計算多邊形對點的包含關(guān)系。矢量結(jié)構(gòu)的GIS能夠通過計算每個點相對于多邊形線段的位置，進(jìn)行點是否在一個多邊形中的空間關(guān)系判斷。 此外，還要進(jìn)行屬性信息處理。最簡單的方式是將多邊形屬性信息疊加到其中的點上。當(dāng)然也可以將點的屬性疊加到多邊形上，用于標(biāo)識該多邊形。二、點與多邊形疊加第3節(jié) 空間疊置分析疊置結(jié)果圖層鄉(xiāng)鎮(zhèn)區(qū)劃圖層鄉(xiāng)鎮(zhèn)農(nóng)作物圖層 點與多邊形疊置分析ID名稱1大王鎮(zhèn)2張家村3李

16、家村ID農(nóng)作物產(chǎn)量160022,00031,000ID名稱農(nóng)作物產(chǎn)量1大王鎮(zhèn)6002大王鎮(zhèn)2,0003李家村1,0004.疊加分析疊加分析 線與多邊形的疊加，是比較線上坐標(biāo)與多邊形坐標(biāo)的關(guān)系，判斷線是否落在多邊形內(nèi)。計算過程：計算交點；形成結(jié)點和鏈；建立拓樸；更新屬性。三、線與多邊形疊加 第3節(jié) 空間疊置分析鄉(xiāng)鎮(zhèn)區(qū)劃圖層河流圖層疊置結(jié)果圖層線與多邊形疊置分析ID名稱1大王鎮(zhèn)2張家村3李家村ID河流1裕河2昌河3十里溝ID名稱河流1大王鎮(zhèn)裕河2大王鎮(zhèn)昌河3李家村昌河4.疊加分析疊加分析 多邊形疊加是GIS最常用的功能之一。多邊形疊加將兩個或多個多邊形圖層進(jìn)行疊加產(chǎn)生一個新多邊形圖層的操作，其結(jié)果

17、將原來多邊形要素分割成新要素，新要素綜合了原來兩層或多層的屬性。第3節(jié) 空間疊置分析四、多邊形與多邊形疊加多邊形疊置分析鄉(xiāng)鎮(zhèn)區(qū)劃圖層土地利用圖層疊置結(jié)果圖層ID名稱1高家莊2賈家村3周家堡ID土地利用編號111021113112ID名稱土地利用編號1高家莊1102賈家村1103周家堡1124.疊加分析疊加分析第3節(jié) 空間疊置分析四、多邊形與多邊形疊加 疊加過程可分為幾何求交過程和屬性分配過程兩步。幾何求交過程首先求出所有多邊形邊界線的交點，再根據(jù)這些交點重新進(jìn)行多邊形拓?fù)溥\(yùn)算，對新生成的拓?fù)涠噙呅螆D層的每個對象賦一多邊形唯一標(biāo)識碼，同時生成一個與新多邊形對象一一對應(yīng)的屬性表。由于矢量結(jié)構(gòu)的有限

18、精度原因，幾何對象不可能完全匹配，疊加結(jié)果可能會出現(xiàn)一些碎屑多邊形（Silver Polygon）。通常可以設(shè)定一模糊容限以消除它。第3節(jié) 空間疊置分析四、多邊形與多邊形疊加 疊加生成疊加生成碎屑多邊形碎屑多邊形 T2 時刻多邊形時刻多邊形 多邊形疊加結(jié)果多邊形疊加結(jié)果 T1 時刻多邊形時刻多邊形 第第3 3節(jié)節(jié) 空間疊置分析空間疊置分析四、多邊形與多邊形疊加 根 據(jù) 疊加 結(jié) 果 最 后欲 保 留 空 間特 征 的 不 同要 求 ， 一 般的GIS軟件都提 供 了 三 種類 型 的 多 邊形疊加操作，如圖所示：第3節(jié) 空間疊置分析交交只保留兩個輸入圖層 的公共區(qū)域疊和疊和以輸入圖層為界，保留

19、邊界內(nèi)兩個多邊形的所有多邊形輸入圖層疊加圖層并并保留兩個輸入圖層 的所有多邊形結(jié)果圖層四、多邊形與多邊形疊加 柵格數(shù)據(jù)結(jié)構(gòu)空間信息隱含屬性信息明顯的特點，可以看作是最典型的數(shù)據(jù)層面，通過數(shù)學(xué)關(guān)系建立不同數(shù)據(jù)層面之間的聯(lián)系是GIS提供的典型功能?？臻g模擬尤其需要通過各種各樣的方程將不同數(shù)據(jù)層面進(jìn)行疊加運(yùn)算，這種作用于不同數(shù)據(jù)層面上的基于數(shù)學(xué)運(yùn)算的疊加運(yùn)算，在地理信息系統(tǒng)中稱為地圖代數(shù)。地圖代數(shù)功能有三種不同的類型： 基于常數(shù)對數(shù)據(jù)層面進(jìn)行的代數(shù)運(yùn)算； 基于數(shù)學(xué)變換對數(shù)據(jù)層進(jìn)行的數(shù)學(xué)變換（指數(shù)、對數(shù)、三角變換等）； 多個數(shù)據(jù)層面的代數(shù)運(yùn)算（加、減、乘、除、乘方等）和邏輯運(yùn)算（與、或、非、異或等）。

20、第3節(jié) 空間疊置分析五、柵格圖層的疊加12( ,)nEf x xx設(shè) x1,x2,x3xn，分別表示第1層至第n層上同一坐標(biāo)屬性值，f函數(shù)表示各層上屬性與用戶需求之間的關(guān)系，E為疊置后屬性輸出層的屬性值，則疊加操作的輸出結(jié)果可能是： 各層屬性數(shù)據(jù)的算術(shù)運(yùn)算結(jié)果； 各層屬性數(shù)據(jù)的極值； 邏輯條件組合； 其他模型運(yùn)算結(jié)果。第3節(jié) 空間疊置分析(一)布爾邏輯運(yùn)算 柵格數(shù)據(jù)可以按其屬性數(shù)據(jù)的布爾邏輯運(yùn)算來檢索，即這是一個邏輯選擇的過程。布爾邏輯為AND、OR、XOR、NOT。布爾邏輯運(yùn)算可以組合更多的屬性作為檢索條件，例如加上面積和形狀等條件，以進(jìn)行更復(fù)雜的邏輯選擇運(yùn)算。例如可以用條件：(A AND

21、B) OR C進(jìn)行檢索。其中A為土壤是粘性的，B為PH值7.0的，C為排水不良的。這樣就可把柵格數(shù)據(jù)中土壤結(jié)構(gòu)為粘性的、土壤PH值大于7.0的、或者排水不良的區(qū)域檢索出來。第3節(jié) 空間疊置分析五、柵格圖層的疊加第3節(jié) 空間疊置分析五、柵格圖層的疊加（二）重分類 重分類是將屬性數(shù)據(jù)的類別合并或轉(zhuǎn)換成新類。即對原來數(shù)據(jù)中的多種屬性類型，按照一定的原則進(jìn)行重新分類，以利于分析。重分類時必須保證多個相鄰接的同一類別的圖形單元應(yīng)獲得相同的名稱，并將圖形單元合并，從而形成新的圖形單元 。重分類的過程12345AABBAAB第3節(jié) 空間疊置分析五、柵格圖層的疊加(三)函數(shù)運(yùn)算 多層疊置分析是指將不同圖幅或不

22、同數(shù)據(jù)層的柵格數(shù)據(jù)疊置在一起，在疊置地圖的相應(yīng)位置上產(chǎn)生新的屬性的分析方法。新屬性值的計算可由下式表示： Uf(A,B,C,)其中，A，B，C等表示第一、二、三等各層上的確定的屬性值，f函數(shù)取決于疊置的要求。 多幅圖疊置后的新屬性可由原屬性值的簡單的加、減、乘、除、乘方等計算出，也可以取原屬性值的平均值、最大值、最小值、或原屬性值之間邏輯運(yùn)算的結(jié)果等，甚至可以由更復(fù)雜的方法計算出，如新屬性的值不僅與對應(yīng)的原屬性值相關(guān)，而且與原屬性值所在的區(qū)域的長度、面積、形狀等特性相關(guān)。第3節(jié) 空間疊置分析五、柵格圖層的疊加 例如利用土壤侵蝕通用方程式計算土壤侵蝕量時，就可利用多層面柵格數(shù)據(jù)的函數(shù)運(yùn)算復(fù)合分析

23、法進(jìn)行自動處理。一個地區(qū)土壤侵蝕量的大小是降雨(R)、植被覆度(C)、坡度(S）、坡長（L）、土壤抗蝕性(SR）等因素的函數(shù)?？蓪懗? , , ,)EF R C S L SR 第3節(jié) 空間疊置分析五、柵格圖層的疊加 土壤侵蝕多因子函數(shù)運(yùn)算復(fù)合分析示意圖坡度圖坡長圖土壤抗蝕圖降雨量圖植被覆度侵蝕量圖第3節(jié) 空間疊置分析五、柵格圖層的疊加有一個森林地區(qū)融雪經(jīng)驗?zāi)Ｐ停篗=（0.19T+0.17D） 式中，M是融雪速度（厘米/天），T是空氣溫度，D是露點溫度。根據(jù)此方程，使用該地區(qū)的氣溫和露點溫度分布圖層，就能計算該地區(qū)融雪速率分布圖。計算過程是先分別把溫度分布圖乘以0.19和露點溫度分布圖乘以0.1

24、7，再把得到的結(jié)果相加。 第3節(jié) 空間疊置分析五、柵格圖層的疊加第節(jié) 空間網(wǎng)絡(luò)分析 對地理網(wǎng)絡(luò)（如交通網(wǎng)絡(luò)）、城市基礎(chǔ)設(shè)施網(wǎng)絡(luò)（如各種網(wǎng)線、電力線、電話線、供排水管線等）進(jìn)行地理分析和模型化，是地理信息系統(tǒng)中網(wǎng)絡(luò)分析功能的主要目的。網(wǎng)絡(luò)分析是運(yùn)籌學(xué)模型中的一個基本模型，它的根本目的是研究、籌劃一項網(wǎng)絡(luò)工程如何安排，并使其運(yùn)行效果最好，如一定資源的最佳分配，從一地到另一地的運(yùn)輸費(fèi)用最低等。 第節(jié) 空間網(wǎng)絡(luò)分析一、GIS網(wǎng)絡(luò)分析的概念 概念: GIS的網(wǎng)絡(luò)分析，是通過研究網(wǎng)絡(luò)的狀態(tài)以及模擬和分析資源在網(wǎng)絡(luò)上的流動和分配情況，對網(wǎng)絡(luò)結(jié)構(gòu)及其資源等的優(yōu)化問題進(jìn)行研究的一種空間分析方法。 網(wǎng)絡(luò)分析的基礎(chǔ)

25、是圖論和運(yùn)籌學(xué) 網(wǎng)絡(luò)圖論基礎(chǔ) 圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖，而是一個以抽象的形式來表達(dá)確定的事物，以及事物之間具備或不具備某種特定關(guān)系的數(shù)學(xué)系統(tǒng)。 由點集合V 和點與點之間的連線的集合E所組成的集合對（V，E）稱為圖，用G（V，E）來表示。 V中的元素稱為節(jié)點，E中的元素稱為邊。 節(jié)點集V與邊集合E均為有限的圖稱為有限圖。這里只討論有限圖。 一、GIS網(wǎng)絡(luò)分析的概念 網(wǎng)絡(luò)圖論基礎(chǔ) 如果圖中的邊是有向的，則稱為有向圖。 在無向圖中，首位相接的一串邊的集合稱為路。 在有向圖中，順向的首尾相接的一串有向邊的集合稱為有向路。 起點和終點為同一節(jié)點的路稱為回路（或圈）。 如果一

26、個圖中，任意兩個節(jié)點之間都存在一條路，稱這種圖為連通圖。 若一個連通圖中不存在任何回路，則稱為樹 如果圖中任一邊(i,j)都賦一個數(shù)(i,j)， 稱這種數(shù)為該邊的權(quán)數(shù)。 賦以權(quán)數(shù)的圖成為賦權(quán)圖。 有向圖的各邊賦以權(quán)數(shù)后， 成為有向賦權(quán)圖。第節(jié) 空間網(wǎng)絡(luò)分析 二、網(wǎng)絡(luò)的組成 1. 網(wǎng)絡(luò) 是一系列聯(lián)結(jié)的弧段，形式物質(zhì)，信息流通的通道。 2. 網(wǎng)絡(luò)基本要素 結(jié)點： 網(wǎng)絡(luò)中任意兩條線段的交點。 鏈： 連通路線，連結(jié)兩點的段要素。 轉(zhuǎn)彎： 從一條鏈上經(jīng)結(jié)點轉(zhuǎn)向另一條鏈。 ?？奎c(站點)：網(wǎng)絡(luò)中資源的上、下結(jié)點。 中心： 收發(fā)資源的結(jié)點處的設(shè)施。 障礙： 資源不能通過的結(jié)點。 3.屬性 阻礙：資源在網(wǎng)絡(luò)中

27、運(yùn)行的阻力。 資源需求量：網(wǎng)絡(luò)中與弧段和停靠點相聯(lián)系資源的數(shù)量。 資源容量：網(wǎng)絡(luò)中心為弧段的需求能容納或提供的資源總數(shù)量。 障礙障礙中心中心站點站點站點站點拐角拐角結(jié)點結(jié)點結(jié)點結(jié)點結(jié)點結(jié)點網(wǎng)絡(luò)網(wǎng)絡(luò)網(wǎng)絡(luò)網(wǎng)絡(luò)第節(jié) 空間網(wǎng)絡(luò)分析二、網(wǎng)絡(luò)的組成 4. 網(wǎng)絡(luò)要素的表示 鏈弧 轉(zhuǎn)彎 M條弧相連共有轉(zhuǎn)彎個數(shù)N：N=M2 鏈弧號起結(jié)點終結(jié)點 長度(km)正方向阻強(qiáng)(km/h)反方向阻強(qiáng)(km/h)資源需求量2024145.33555(-1:表示不通) 243555結(jié)點號從弧段至弧段角度時間阻強(qiáng)(s)34L2L1906034L1L11803034L2L3-90-1(不允許拐彎）34L1L300(無阻強(qiáng))停靠點L

28、1L3L234第節(jié) 空間網(wǎng)絡(luò)分析二、網(wǎng)絡(luò)的組成 4. 網(wǎng)絡(luò)要素的表示 停靠點、中心的屬性 ?？奎c：直接在相應(yīng)的結(jié)點上附上需求量 屬性，負(fù)為下卸，正值為裝載。 中心：資源最大容量、服務(wù)范圍和服務(wù)延遲數(shù)。 結(jié)點號需求量453546-20結(jié)點號資源最大容量服務(wù)范圍服務(wù)延遲數(shù)2410002000 第節(jié) 空間網(wǎng)絡(luò)分析 三、網(wǎng)絡(luò)分析 1.最短路徑問題 最短路徑的含義是指在網(wǎng)絡(luò)中，找出從起點出發(fā)到終點的累計行程最短的路徑。 1）“純距離”意義上的最短路徑 2）“經(jīng)濟(jì)距離”意義上的最短路徑 3）“時間”意義上的最短路徑單源點間最短路徑，網(wǎng)絡(luò)中某一點到其它點的最短路徑.所有點對之間的最短路徑，在整個運(yùn)算過程中，

29、求得所有點對之間的最短距離.第節(jié) 空間網(wǎng)絡(luò)分析 三、網(wǎng)絡(luò)分析 1.最短路徑問題 最短路徑的算法Dijkstar算法 1959年由E.W.Dijkstar提出的標(biāo)號法被認(rèn)為是目前公認(rèn)的最好的求解算法 該算法的優(yōu)點是： 可以求出求出起點到終點的最短路徑及其長度，而且可以求出起點到其它 任何一個頂點的最短路徑及其長度。 不但適用于求解有向圖上的最短路徑問題，而且同樣也適用于求解無向圖上的 最短路徑問題。 基本思想：首先從起點Vs開始，給每個頂點標(biāo)一個數(shù)(成為標(biāo)號)， T 標(biāo)號表示從起點Vs到該點的最短路權(quán)的上界，稱為臨時標(biāo)號； P 標(biāo)號表示從Vs到該點的最短路權(quán)，稱為固定標(biāo)號。 已經(jīng)得到 P 標(biāo)號的

30、頂點不再改變，凡是沒有標(biāo)上 P 標(biāo)號的頂點，標(biāo)上T標(biāo)號。 算法的每一步就是把某一頂點的 T 標(biāo)號改為變?yōu)?P 標(biāo)號。那么，最多經(jīng)過k -1 步，就可以求得從起點Vs ，到終點Vk的最短路徑。第節(jié) 空間網(wǎng)絡(luò)分析 基本思想 按最短路徑長度遞增的順序，逐個產(chǎn)生各最短路徑。E.W.Dijkstra狄克斯特拉算法狄克斯特拉算法(Dijkstra,1959) (Dijkstra,1959) 狄克斯特拉算法狄克斯特拉算法(Dijkstra,1959) (Dijkstra,1959) 距離矩陣的計算 為了求出最短路徑，需先計算兩點間的距離， 并形成距離矩陣。若兩點間沒有路，則距離為。 最短路徑搜索的依據(jù) 最短

31、路徑搜索的基本依據(jù)是，若從點S 到點 E 有一條最短路徑， 則該路徑上的任何點到S 的距離都是最短的。 為了進(jìn)行最短路徑搜索，令d(Vi, Vj)表示點Vi到Vj的距離， P(Vi)表示Vi到起始點S的最短距離。 最短路徑搜索的步驟 (1) 對起始點S作標(biāo)記，且對所有頂點令P(Vs) = 0, T(Vi) 。 (2) 對所有未作標(biāo)記的點按以下公式計算距離， T(Vj) min T(Vj), d(Vi, Vj) P(Vi) 其中Vi是己確定作標(biāo)記的點。取具有最小值的T(Vj)，并對Vj作標(biāo)記，令P(Vj)T(Vj) 。 若最小值的T(Vj)為，則說明S到所有未標(biāo)記的點都沒有路，算法終止；否則繼續(xù)

32、。 (3) 如果Vj等于E，則已找到S到E的最短路徑，算法終止；否則轉(zhuǎn)(2)。 需搜索A到C的最短路徑 對A作P標(biāo)記，P(A)=0, 其它結(jié)點作T標(biāo)號，T(V)= +, V為B、C、D、E。 因為A已經(jīng)得到P標(biāo)號，而與A關(guān)聯(lián)的點有B、E、D， 且它們都是T標(biāo)號，所以要修改它們的T標(biāo)號 T(B) = minT(B),P(A)+d(A,B) = min+,0+4 = 4 T(E) = minT(E),P(A)+ d(A,E) = min+,0+2 = 2 T(D) = minT(D),P(A)+ d(A,D) = min+,0+1 = 1 在所有的T 標(biāo)號中，T(D) = 1最小，于是令P(D)

33、= 1 因為D已經(jīng)得到P標(biāo)號，而與D關(guān)聯(lián)的點有E、C， 且它們都是T標(biāo)號，所以要修改它們的T標(biāo)號 T(E) = minT(E),P(D)+d(D,E) = min2,1+2 = 2 T(C) = minT(C),P(D)+ d(D,C) = min+,1+9 = 10 在所有的T 標(biāo)號中，T(E) = 2最小，于是令P(E) = 2 因為E已經(jīng)得到P標(biāo)號，而與E關(guān)聯(lián)的點有B、C， 且它們都是T標(biāo)號，所以要修改它們的T標(biāo)號 T(B) = minT(B),P(E)+d(E,B) = min4,2+1 = 3 T(C) = minT(C),P(E)+ d(E,C) = min10,2+6 = 8 在

34、所有的T 標(biāo)號中，T(B) = 3最小，于是令P(B) = 3 因為B已經(jīng)得到P標(biāo)號，而與B關(guān)聯(lián)的點只有C，且為T標(biāo)號，所以要修改它們的T標(biāo)號 T(C) = minT(C),P(B)+d(B,C) = min8,3+7 = 8 在所有的T 標(biāo)號中，只有T(C) = 8最小，于是令P(C) = 8 根據(jù)順序記錄的標(biāo)記點，以及最小值的取值情況，可得到最短路徑為AEC， 最短距離為8。 Dijkstar算法應(yīng)用舉例 在下圖所示的賦權(quán)圖中，每一個頂點Vi ( i=1,2,)代表一個城鎮(zhèn)；每一條邊代表相應(yīng)兩個城鎮(zhèn)之間的交通線，其長度用邊旁的數(shù)字表示。試求城鎮(zhèn) V1到 V6 之間的最短路徑。 第節(jié) 空間網(wǎng)

35、絡(luò)分析142536171281416212139起始點起始點Disti：起始點到每個終點vi的最短路徑長度 初始值： Disti=Costi0,i viVV：網(wǎng)絡(luò)節(jié)點集合, V=1,2,3,4,5,6 S：已確定最短路徑的節(jié)點集合，S=1V-S：尚未確定最短路徑的節(jié)點集合0902101614132012081701 2 3 4 5 6123456142536171281416212139起始點起始點Costi,jDijkstarDijkstar算法應(yīng)用舉例算法應(yīng)用舉例Costi,j=142536171281416212139(17, 1)(8, 1)(, )(, )(, )42起始點09021

36、01614132012081701 2 3 4 5 6123456Costi,j=S=1Disti=Costi0,iV=1,2,3,4,5,6DijkstarDijkstar算法應(yīng)用舉例算法應(yīng)用舉例142536171281416212139(17,1)(8,1)(, )(, )(, )j=4S=1,4V-S=2,3,5,6第一步：選擇Vj，使得Distj=Min Disti|ViV-S， S=SViDijkstarDijkstar算法應(yīng)用舉例算法應(yīng)用舉例T(2) = minT(2),P(1)+d(1,2) = min+,0+17 = 17T(4) = minT(4),P(1)+ d(1,4)

37、= min+,0+8 = 8 在所有的T 標(biāo)號中，T(4) = 8最小，于是令P(4) = 8142536171281416212139(17,1)(8,1)(24,4)(29,4)(, )j=4S=1,4V=2,3,5,6第二步：修改從Vj出發(fā)到集合V-S中任意一頂點Vk的最短路徑長度。如果:Distj+Costj,kDistk, 則 Distk=Distj+Costj,kDijkstarDijkstar算法應(yīng)用舉例算法應(yīng)用舉例142536171281416212139(17,1)(8,1)(24,4)(29,4)(, )S=1,4,2V=3,5,6j=2重復(fù)第一步：選擇VjDijkstar

38、Dijkstar算法應(yīng)用舉例算法應(yīng)用舉例142536171281416212139(17,1)(8,1)(24,4)(26,3)(37,3)S=1,4,2,3V=5,6j=3DijkstarDijkstar算法應(yīng)用舉例算法應(yīng)用舉例142536171281416212139(17,1)(8,1)(24,4)(26,3)(35,5)S=1,4,2,3,5V=6j=5DijkstarDijkstar算法應(yīng)用舉例算法應(yīng)用舉例S=1,4,2,3,5,6V=142536171281416212139(17,1)(8,1)(24,4)(26,3)(35,5)j=6DijkstarDijkstar算法應(yīng)用舉例

39、算法應(yīng)用舉例2()O n起點到其它所有點的最短路徑，時間復(fù)雜度為：3()O n任意兩點之間的最短距離，時間復(fù)雜度為：DijkstarDijkstar算法算法( (時間復(fù)雜度時間復(fù)雜度) ) 三、網(wǎng)絡(luò)分析 2.連通分析最小生成樹 含義 連通圖：如果一個圖中，任意兩個節(jié)點之間都存在一條路。 樹：若一個連通圖中不存在任何回路，則稱為樹。 最小生成樹：生成樹是圖的極小連通子圖。 生成樹T 的權(quán)數(shù)：生成樹中各邊的權(quán)數(shù)之和。 應(yīng)用 類似在n個城市間建立通信線路這樣的連通分析問題。 圖的頂點表示城市，邊表示兩城市間的線路，邊上所賦的權(quán)值表示代價126543161118656第節(jié) 空間網(wǎng)絡(luò)分析 三、網(wǎng)絡(luò)分析

40、2.連通分析最小生成樹 構(gòu)造最小生成樹的依據(jù)有兩點： 1）在網(wǎng)中選擇n1條邊連接網(wǎng)的n個頂點； 2）盡可能選取權(quán)值為最小的邊。 12654316193321111418656賦權(quán)圖12654316111865612654316111856最小生成樹之一最小生成樹之二第節(jié) 空間網(wǎng)絡(luò)分析 三、網(wǎng)絡(luò)分析 2.連通分析最小生成樹 算法（Kruskal，克羅斯克爾算法，也叫“避圈”法） 1）先把圖G中的各邊按權(quán)數(shù)從小到大重新排列， 并取權(quán)數(shù)最小的一條邊為T中的邊。 2）在剩下的邊中，按順序取下一條邊。若該邊 與T中已有的邊構(gòu)成回路，則舍去該邊，否則 選進(jìn)T 中。 3）重復(fù)2），直到有m-1條邊被選進(jìn)T中

41、，這m-1 條邊就是G的圖。 12654316193321111418656賦權(quán)圖第節(jié) 空間網(wǎng)絡(luò)分析 三、網(wǎng)絡(luò)分析 3.資源分配定位與分配問題 含義 在一些候選點中選擇給定數(shù)量的供應(yīng)點以使預(yù)定的目標(biāo)方程達(dá)到最佳結(jié)果。-最佳分配中心，最優(yōu)配置。 所謂目標(biāo)方程，是用數(shù)學(xué)方式表達(dá)滿足所需求點到供應(yīng)點的加權(quán)距離最小的條件方程，也稱P中心定位問題 主要包括： 定位問題：指已知需求源的分布，確定在哪里布設(shè)供應(yīng)點最合適的問題 分配問題：確定這些需求源分別受哪個供應(yīng)點服務(wù)的問題。 第節(jié) 空間網(wǎng)絡(luò)分析 三、網(wǎng)絡(luò)分析 3.資源分配定位與分配問題 算法 P中心的定位分配問題的Teitz-Bart算法 1）算法思想

42、是要在m個候選點中選擇P個供應(yīng)點為n個需求點服務(wù)，使得為這幾個需求點服務(wù)的總距離(或時間或費(fèi)用)為最少。 假設(shè)i記為需求點i的需求量， dij 記為從候選點j到需求點i的距離，則P中心問題可敘為： 并滿足： i = 1,2,n 保證每個需求點 i 都被服務(wù) pmn 其中，aij是分配的指數(shù)。如果需求點i受供應(yīng)點j的服務(wù)，則其值為1，否則為0 上述兩個約束條件是為了保證每個需求點僅受一個供應(yīng)點服務(wù)，并且只有p個供應(yīng)點第節(jié) 空間網(wǎng)絡(luò)分析 3.資源分配定位與分配問題 算法 P中心的定位分配問題的Teitz-Bart算法 2）算法步驟 A、選定P個候選點作為起始供應(yīng)點，并將所有需求點分配到最近的供應(yīng)點，計算其目標(biāo)方程，即總的加權(quán)距離。 B、作全局性調(diào)整 檢驗所有選擇的供應(yīng)點，選定一個供應(yīng)點準(zhǔn)備刪除，它的刪除僅引起最小的 目標(biāo)方程的增值 從未選入的候選點中，尋找一個候選點來代替第一步中選定的供應(yīng)點，這樣可以 最大限度地減少目標(biāo)方程的值 如果步驟中選定的點所減少的目標(biāo)方程的值大于第一步中選定的點所增加的目標(biāo)方程的值，就用步驟中的點代替步驟中選擇的點，并更新目標(biāo)方程的值，再回到步驟重復(fù)檢驗。