第八章空間基本原理和方法

第8章空間分析基本原理與方法梁欣

8.3空間分析方法柵格數(shù)據(jù)分析矢量數(shù)據(jù)分析網(wǎng)絡(luò)分析基于地形的分析8.3.1柵格數(shù)據(jù)分析的基本模式聚類分析聚合分析信息的復(fù)合分析柵格數(shù)據(jù)的追蹤分析柵格數(shù)據(jù)的窗口分析一、聚類分析聚類分析是將屬性數(shù)據(jù)的類別合并或轉(zhuǎn)換成新類。即對原來數(shù)據(jù)中的多種屬性類型，按照一定的原則進(jìn)行重新分類，以利于分析。在多數(shù)情況下，聚類分析都是將復(fù)雜的類型合并成簡單的類型?？蓪⒏鞣N土壤類型聚類分析為水面和陸地兩種類型。聚類分析時必須保證多個相鄰接的同一類別的圖形單元應(yīng)獲得一個相同的名稱，并且這些圖形單元之間的邊應(yīng)該去掉，從而形成新的圖形單元。合并相同屬性的多邊形二、聚合分析將較小的多邊形合并到相鄰的多邊形中，具有數(shù)據(jù)綜合的作用三、柵格數(shù)據(jù)信息的復(fù)合分析①類型疊置即通過疊置獲取新的類型。如土壤圖與植被圖疊置，以分析土壤與植被的關(guān)系。②數(shù)量統(tǒng)計即計算某一區(qū)域內(nèi)的類型和面積。如行政區(qū)劃圖和土壤類型圖疊圖，可計算出某一行政區(qū)劃中的土壤類型數(shù)，以及各種類型土壤的面積。③動態(tài)分析即通過對同一地區(qū)、相同屬性、不同時間的柵格數(shù)據(jù)的疊置，分析由時間引起的變化。④益本分析即通過對屬性和空間的分析，計算成本、價值等。⑤幾何提取即通過與所需提取的范圍的疊置運(yùn)算，快速地進(jìn)行范圍內(nèi)信息的提取。柵格圖層疊加——森林地區(qū)融雪模型M=（0.19T+0.17D）M融雪速度（厘米/天）T

空氣溫度D

露點溫度根據(jù)此方程，使用該地區(qū)的氣溫和露點溫度分布圖層，就能計算該地區(qū)融雪速率分布圖。計算過程是先分別把溫度分布圖乘以0.19和露點溫度分布圖乘以0.17，再把得到的結(jié)果相加。疊置運(yùn)算得到不同的結(jié)果從幾何運(yùn)算上看，兩個多邊形通過不同的疊置運(yùn)算可以得到不同的結(jié)果：交并差分割多層?xùn)鸥駭?shù)據(jù)的疊置分析是指將二個以上圖幅或不同數(shù)據(jù)層的柵格數(shù)據(jù)疊置在一起，在疊置地圖的相應(yīng)位置上產(chǎn)生新的屬性的分析方法。新屬性值的計算可由下式表示：U＝f(A,B,C,……)其中，A，B，C等表示第一、二、三等各層上的確定的屬性值，f函數(shù)取決于疊置的要求。

多幅圖疊置后的新屬性可由原屬性值的簡單的加、減、乘、除、乘方等計算出，也可以取原屬性值的平均值、最大值、最小值、或原屬性值之間邏輯運(yùn)算的結(jié)果等，甚至可以由更復(fù)雜的方法計算出，如新屬性的值不僅與對應(yīng)的原屬性值相關(guān)，而且與原屬性值所在的區(qū)域的長度、面積、形狀等特性相關(guān)。多層?xùn)鸥癔B置示意圖柵格疊置的具體運(yùn)算在進(jìn)行柵格疊置的具體運(yùn)算時，可以直接在未壓縮的柵格矩陣上進(jìn)行，也可在壓縮編碼(如游程編碼、四叉樹編碼)后的柵格數(shù)據(jù)上進(jìn)行。它們之間的差別主要在于算法的復(fù)雜性、算法的速度、所占用的計算機(jī)內(nèi)存等。邏輯操作布爾邏輯運(yùn)算柵格數(shù)據(jù)可以按其屬性數(shù)據(jù)的布爾邏輯運(yùn)算來檢索，即這是一個邏輯選擇的過程。布爾邏輯為AND、OR、XOR、NOT。布爾邏輯運(yùn)算可以組合更多的屬性作為檢索條件，例如加上面積和形狀等條件，以進(jìn)行更復(fù)雜的邏輯選擇運(yùn)算。布爾邏輯運(yùn)算AND、OR、XOR、NOT例如可以用條件：(AANDB)ORC進(jìn)行檢索。其中A為土壤是粘性的，B為PH值＞7.0的，C為排水不良的。這樣就可把柵格數(shù)據(jù)中土壤結(jié)構(gòu)為粘性的、土壤PH值大于7.0的、或者排水不良的區(qū)域檢索出來。

布爾邏輯運(yùn)算舉例在地下管網(wǎng)信息系統(tǒng)中，設(shè)A為埋深小于3米的煤氣管；B為長度小于300米的煤氣管。AANDB埋深小于3米且長度小于300米的所有煤氣管；AORNOTB埋深小于3米及長度大于或等于300米的所有煤氣管；AXORB埋深小于3米而長度大于或等于300米的煤氣管道和長度小于300米而埋深大于或等于3米的煤氣管道四、柵格數(shù)據(jù)的追蹤分析對原圖二值化細(xì)化矢量化圖像邊緣跟蹤圖像內(nèi)線要素的跟蹤五、柵格數(shù)據(jù)的窗口分析對柵格數(shù)據(jù)可計算區(qū)域的周長、面積、重心等，以及線的長度、點的坐標(biāo)等在柵數(shù)數(shù)據(jù)上量算面積有其獨(dú)特的方便之處，只要對柵格進(jìn)行計數(shù)，再乘以柵格的單位面積即可特征參數(shù)計算例圖在柵格數(shù)據(jù)中計算距離時，距離有四方向距離、八方向距離、歐幾里德距離等多種意義。四方向距離是通過水平或垂直的相鄰像元來定義路徑的；八方向距離是根據(jù)每個像元的八個相鄰像元來定義的。對圖的線，用四方向距離計算的距離為6，用八方向計算的距離為六、基于柵格數(shù)據(jù)的緩沖區(qū)分析

緩沖區(qū)分析在GIS中用得較多，但對矢量數(shù)據(jù)的緩沖區(qū)操作比較復(fù)雜，而在柵格數(shù)據(jù)中可看作是對空間實體向外進(jìn)行一定距離的擴(kuò)展，因而算法比較簡單。算法比較簡單，核心問題是距離變換。柵格數(shù)據(jù)8.3.2矢量數(shù)據(jù)分析的基本方法拓?fù)浏B加緩沖區(qū)分析數(shù)字地形分析空間集合分析一、包含分析判斷某個地理實體是否位于另一個地理實體之內(nèi)。包含分析需要判斷備查對象與包含多邊形之間的關(guān)系，包括：包含穿越部分包含二、矢量數(shù)據(jù)的緩沖區(qū)分析1、緩沖區(qū)概念及其作用GIS緩沖區(qū)是指在點、線、面實體的周圍，自動建立的一定寬度的多邊形。例如：某地區(qū)有危險品倉庫，要分析一旦倉庫爆炸所涉及的范圍，這就需要進(jìn)行點緩沖區(qū)分析；如果要分析因道路拓寬而需拆除的建筑物和需搬遷的居民，則需進(jìn)行線緩沖區(qū)分析；而在對野生動物棲息地的評價中，動物的活動區(qū)域往往是在距它們生存所需的水源或棲息地一定距離的范圍內(nèi)，為此可用面緩沖區(qū)進(jìn)行分析。緩沖區(qū)分析的意義緩沖區(qū)分析是GIS的基本空間操作功能之一，也是解決鄰近度問題的空間分析工具之一。鄰近度(Proximity)

描述了地理空間中兩個地物距離相近的程度，其確定是空間分析的一個重要手段。污染物擴(kuò)散、道路拓寬拆遷

交通網(wǎng)的影響區(qū)分析點、線、面的緩沖區(qū)緩沖區(qū)的寬度在建立緩沖區(qū)時，緩沖區(qū)的寬度并不一定是相同的，可以根據(jù)要素的不同屬性特征，規(guī)定不同的緩沖區(qū)寬度，以形成可變寬度的緩沖區(qū)。例如，沿河流繪出的環(huán)境敏感區(qū)的寬度應(yīng)根據(jù)河流的類型而定。這樣就可根據(jù)河流屬性表，確定不同類型的河流所對應(yīng)的緩沖區(qū)寬度，以產(chǎn)生所需的緩沖區(qū)。2、緩沖區(qū)的建立

點的緩沖區(qū)建立時，只需要給定半徑繪圓即可。面的緩沖區(qū)只朝一個方向（里外之一），而線的緩沖區(qū)需在線的左右配置。建立線緩沖區(qū)在建立線緩沖區(qū)時，通常首先要對線進(jìn)行化簡，以加快緩沖區(qū)建立的速度。這種對線的化簡稱為線的重采樣。具體的算法設(shè)計可采用線的矢量數(shù)據(jù)壓縮算法。建立線緩沖區(qū)就是生成緩沖區(qū)多邊形。只需在線的兩邊按一定的距離（緩沖距）繪平行線，并在線的端點處繪半圓，就可連成緩沖區(qū)多邊形。對一條線所建的緩沖區(qū)有可能重疊，這時需把重疊的部分去除?；舅悸肥?，對緩沖區(qū)邊界求交，并判斷每個交點是出點還是入點，以決定交點之間的線段保留或刪除。這樣就可得到島狀的緩沖區(qū)。緩沖區(qū)的計算凸角圓弧法：方法最大限度的保證了平行曲線的等寬性。緩沖區(qū)邊界相交的情況

當(dāng)緩沖區(qū)形狀比較復(fù)雜或多個對象集合的緩沖區(qū)時，就會產(chǎn)生邊線自相交的情況。處理方法是將斜線區(qū)域當(dāng)成緩沖區(qū)，橫線部分為新增加的島嶼。輸入數(shù)據(jù)、建緩沖區(qū)、重疊處理3、緩沖區(qū)查詢不破壞原有空間對象關(guān)系，僅用緩沖區(qū)給定查詢范圍，并檢索得到落入（全部或局部）緩沖區(qū)對象的過程特點是不產(chǎn)生新的多邊形，僅對緩沖區(qū)內(nèi)的對象數(shù)量和屬性進(jìn)行分析公交線路影響帶內(nèi)的人口和職業(yè)商業(yè)網(wǎng)點的影響區(qū)內(nèi)的人口和收入4、緩沖區(qū)分析（1）緩沖區(qū)和原有圖層疊加得到新的圖層，對新圖層加入屬性特點是產(chǎn)生新的空間實體鼠標(biāo)右鍵選中某個（或幾個）幾何對象，在彈出的快捷菜單中進(jìn)行選擇。緩沖區(qū)分析（2）在對話框中進(jìn)行參數(shù)的設(shè)置生成的緩沖區(qū)添加到地圖窗口顯示結(jié)果緩沖區(qū)分析示意圖三、多邊形的疊置分析疊置分析是地理信息系統(tǒng)最常用的提取空間隱含信息的手段之一，它將有關(guān)主題層組成的數(shù)據(jù)層面，進(jìn)行疊加產(chǎn)生一個新數(shù)據(jù)層面的操作，其結(jié)果綜合了原來兩層或多層要素所具有的屬性。根據(jù)GIS數(shù)據(jù)結(jié)構(gòu)的不同，分為矢量和柵格兩種疊置分析方法。基于矢量數(shù)據(jù)的疊置分析疊置分析是將同一地區(qū)的兩組或兩組以上的要素進(jìn)行疊置，產(chǎn)生新的特征的分析方法。疊置的直觀概念就是將兩幅或多幅地圖重迭在一起，產(chǎn)生新多邊形和新多邊形范圍內(nèi)的屬性。矢量數(shù)據(jù)圖示1、矢量數(shù)據(jù)疊置的內(nèi)容點與多邊形的疊置點與多邊形的疊置是確定一幅圖(或數(shù)據(jù)層)上的點落在另一幅圖(或數(shù)據(jù)層)的哪個多邊形中，這樣就可給相應(yīng)的點增加新的屬性內(nèi)容。例如，一幅圖表示水井的位置，另一幅圖表示城市行政區(qū)。兩幅圖疊置后可得出每個城市功能區(qū)(如居住區(qū))有多少水井，也可知道每口水井是位于城市的什么行政區(qū)。點與多邊形疊置的算法就是判斷點是否在多邊形內(nèi)，可用垂線法或轉(zhuǎn)角法實現(xiàn)。線與多邊形的疊置

線與多邊形的疊置是把一幅圖(或一個數(shù)據(jù)層)中的多邊形的特征加到另一幅圖(或另一個數(shù)據(jù)層)的線上。例如，道路圖與境界圖疊置，可得到每個政區(qū)中各種等級道路的里程。線與多邊形疊置的算法就是線的多邊形裁剪。多邊形與多邊形的疊置多邊形與多邊形的疊置是指不同圖幅或不同圖層多邊形要素之間的疊置，通常分為合成疊置和統(tǒng)計疊置。合成疊置是指通過疊置形成新的多邊形，使新多邊形具有多重屬性，即需進(jìn)行不同多邊形的屬性合并。統(tǒng)計疊置是指確定一個多邊形中含有其它多邊形的屬性類型的面積等，即把其它圖上的多邊形的屬性信息提取到本多邊形中來。AB123451B2B1A2A4A3A5B3B4B降雨量土壤類型適宜農(nóng)作物矢量圖層疊加分析農(nóng)作物適宜性分析宗地的穩(wěn)定性分析疊置分析統(tǒng)計示意圖疊置圖某縣土地報表多邊形的不同疊加方式多邊形與多邊形疊置算法

多邊形與多邊形疊置算法的核心是多邊形對多邊形的裁剪。多邊形裁剪比較復(fù)雜，因為多邊形裁剪后仍然是多邊形，而且可能是多個多邊形。多邊形裁剪的基本思想是一條邊一條邊地裁剪。多邊形A對多邊形B裁剪。多邊形疊置的位置誤差

進(jìn)行多邊形疊置的往往是不同類型的地圖，甚至是不同比例尺的地圖，因此會產(chǎn)生無意義多邊形。處理無意義的多邊形，常用如下三種方法：1°在屏幕上顯示多邊形疊加的情況，人機(jī)交互地把小多邊形合并到大多邊形中。2°確定無意義多邊形的面積臨界值，把小于臨界值的多邊形合并到相鄰的大多邊形中。3°先擬合出一條新的邊界線，然后進(jìn)行疊置操作。無論采用哪種方法來處理無意義多邊形，都會產(chǎn)生誤差。多邊形疊加產(chǎn)生碎屑多邊形SuperMap的五種疊加分析裁剪分析Clip運(yùn)算是用一個Clip數(shù)據(jù)集（左下）從一個被剪取數(shù)據(jù)集（左上）中抽取部分特征（點、線、面）集合的運(yùn)算合并分析合并運(yùn)算是將兩個數(shù)據(jù)集求并集后輸出為一個數(shù)據(jù)集，在這里只限于兩個面數(shù)據(jù)集之間進(jìn)行合并擦除運(yùn)算是用來擦除掉被擦除數(shù)據(jù)集中與Erase數(shù)據(jù)集中多邊形相重疊部分（點、線、面）的操作擦除分析求交分析求交運(yùn)算是求兩個數(shù)據(jù)集的交集的操作。兩個數(shù)據(jù)集中相交的部分將被輸出到結(jié)果數(shù)據(jù)集中，其余部分將被刪除同一分析是對兩個數(shù)據(jù)集進(jìn)行相交運(yùn)算。保留第一數(shù)據(jù)集（左上）的所有部分，去除第二數(shù)據(jù)集（左下）中與第一個數(shù)據(jù)集沒有重疊的部分求青海省的湖泊分布情況根據(jù)全國湖泊分布圖、青海省行政區(qū)域圖計算出青海省境內(nèi)的湖泊分布圖使用裁剪或者求交分析第一數(shù)據(jù)集為“Lake”第二數(shù)據(jù)集為“青?！鼻笄嗪Ｊ∫约笆?nèi)的湖泊分布情況根據(jù)全國湖泊分布圖、青海省行政區(qū)域圖計算出青海省以及省內(nèi)的湖泊分布圖使用同一分析第一數(shù)據(jù)集為“青?！钡诙?shù)據(jù)集為“Lake”8.3.3網(wǎng)絡(luò)分析應(yīng)用

對地理網(wǎng)絡(luò)（如交通網(wǎng)絡(luò)）、城市基礎(chǔ)設(shè)施網(wǎng)絡(luò)（如各種網(wǎng)線、電力線、電話線、供排水管線等）進(jìn)行地理分析和模型化，是GIS中網(wǎng)絡(luò)分析功能的主要目的。電力網(wǎng)和交通網(wǎng)電力設(shè)施管理交通網(wǎng)絡(luò)分析污染分析和路徑分析路徑分析污染源分析與追蹤SuperMap網(wǎng)絡(luò)分析過程構(gòu)建網(wǎng)絡(luò)數(shù)據(jù)集動態(tài)拓?fù)浞植酵負(fù)涮幚碜詣泳S護(hù)拓?fù)潢P(guān)系各種網(wǎng)絡(luò)分析交通分析服務(wù)區(qū)分析構(gòu)建網(wǎng)絡(luò)數(shù)據(jù)集通過線數(shù)據(jù)集自動拓?fù)渫瓿蓸?gòu)建網(wǎng)絡(luò)數(shù)據(jù)集拓?fù)溴e誤處理選項中“弧段求交”項必選各種網(wǎng)絡(luò)分析連通性分析鄰接點分析通達(dá)點分析通達(dá)邊分析關(guān)鍵點分析關(guān)鍵邊分析兩點是否連通分析最佳路徑、旅行商分析服務(wù)區(qū)分析最近設(shè)施查找鄰接點分析通達(dá)點分析通達(dá)邊分析關(guān)鍵點分析關(guān)鍵邊分析兩點間是否連通最佳路徑、旅行商分析（1）功能選取最佳路徑分析旅行商問題站點選取方式節(jié)點選取自由選取導(dǎo)入外部站點查看結(jié)果保存為數(shù)據(jù)集最佳路徑、旅行商分析（2）對訪問站點的順序的處理有所不同最佳路徑分析：必須按照指定的順序訪問網(wǎng)絡(luò)中的所有節(jié)點。旅行商分析：在保證在一次行程中訪問所有站點的前提下，訪問站點的次序是由自己決定的。因此旅行商分析的結(jié)果即包括所選擇的路徑，也包括它所確定的最優(yōu)的訪問次序。服務(wù)區(qū)分析根據(jù)指定的服務(wù)中心點及服務(wù)范圍分析服務(wù)中心點能夠提供的服務(wù)范圍。

最近設(shè)施查找查找與已知點（事件點）距離最近的設(shè)施點

1網(wǎng)絡(luò)圖論基礎(chǔ)

分析和解決網(wǎng)絡(luò)模型的有力工具是圖論,在此介紹了網(wǎng)絡(luò)分析中幾個概念：圖、有向圖、回路、連通圖、樹及其性質(zhì)，賦權(quán)圖。圖論中的“圖”并不是通常意義下的幾何圖形或物體的形狀圖，而是一個以抽象的形式來表達(dá)確定的事物，以及事物之間具備或不具備某種特定關(guān)系的數(shù)學(xué)系統(tǒng)。由點集合V和點與點之間的連線的集合E所組成的集合對（V，E）稱為圖，用G（V，E）來表示。V中的元素稱為節(jié)點，E中的元素稱為邊。節(jié)點集V與邊集合E均為有限的圖稱為有限圖。在下圖中，節(jié)點集合V={A,B,C,D}，邊集合為E={e1,e2,e3,e4,e5,e6,e7,e8}；連接兩個節(jié)點間的邊可能不止一條，如e1,e2都連接A和B，稱為回路或圈；連接同一節(jié)點的邊稱為自圈，如e8；在此不討論具有自圈和回路的圖。如果圖中的邊是有向的，則稱為有向圖，如圖所示。在無向圖中，首位相接的一串邊的集合稱為路。在有向圖中，順向的首尾相接的一串有向邊的集合稱為有向路。通常用順次的節(jié)點或邊來表示路或有向路。如圖中，{e1,e2,e4}為一條路，該路也可用{v1,v2,v3,v5}來表示。

有向圖起點和終點為同一節(jié)點的路稱為回路（或圈）。如果一個圖中，任意兩個節(jié)點之間都存在一條路，稱這種圖為連通圖。若一個連通圖中不存在任何回路，則稱為樹樹樹的性質(zhì)1）樹中任意兩節(jié)點之間至多只有一條邊。2）樹中邊數(shù)比節(jié)點數(shù)少1。3）樹中任意去掉一條邊，就變成不連通圖。4）樹中任意添一條邊，就會構(gòu)成一個回路。

任意一個連通圖，或者是樹，或者去掉一些邊后形成樹，這種樹稱為這個連通圖的生成樹。一般來說，一個連通圖的生成樹可能不止一個賦權(quán)圖如果圖中任一邊（i，j）都賦一個數(shù)ω（i，j），稱這種數(shù)為該邊的權(quán)數(shù)。賦以權(quán)數(shù)的圖成為賦權(quán)圖。有向圖的各邊賦以權(quán)數(shù)后，成為有向賦權(quán)圖。賦權(quán)圖在實際問題中非常有用。根據(jù)不同的實際情況，權(quán)數(shù)的含義可以各不相同。例如，可用權(quán)數(shù)代表兩地之間的實際距離或行車時間，也可用權(quán)數(shù)代表某工序所需的加工時間等。常用權(quán)重及其應(yīng)用權(quán)重描述應(yīng)用邊的長度最短路徑分析程序。很多程序都需要邊長管道的直徑計算網(wǎng)絡(luò)中的壓力的分析程序阻抗（電阻）在一個供電網(wǎng)絡(luò)中計算電壓落差穿過某一條邊的時間最短路徑分析街道中車道的數(shù)量計算一條街道中的交通容量道路的分類最短路徑分析中描述網(wǎng)絡(luò)的分級英里/小時應(yīng)用到一個允許動態(tài)計算權(quán)重的最短路徑算法中冒險的物資運(yùn)輸路線作為一個過濾器使用—尋找一條冒險的物資運(yùn)輸路線使用某條道路的費(fèi)用選擇實際費(fèi)用最小的最短路徑二、路徑分析最短路徑分析

在最短路徑選擇中，兩點之間的距離可以定義為實際的距離，也可定義為兩點間的時間、運(yùn)費(fèi)、流量等，即定義為使用這條邊所需付出的代價。因此，可以對不同的專題內(nèi)容進(jìn)行最短路徑分析。狄克斯特拉（Dijkstra）在1959年提出的最短路徑搜索的算法，被公認(rèn)為是最好的算法之一。狄克斯特拉（Dijkstra）算法基本思想：把圖的頂點分為S、T兩類,若起始點u到某頂點x的最短通路己求出,則將x歸入S，其余歸入T，開始時S中只有u，隨著程序運(yùn)行，T的元素逐個轉(zhuǎn)入S，直到目標(biāo)頂點v轉(zhuǎn)入后結(jié)束。距離矩陣的計算

GIS中的網(wǎng)絡(luò)可以看作是圖，可以是有向圖，也可以是無向圖。無向圖也可當(dāng)作有向圖處理（雙向阻力相等）。

為了求出最短路徑，需先計算兩點間的距離，形成距離矩陣。若兩點間沒有路，則距離為∞。圖為網(wǎng)絡(luò)圖及其距離矩陣。表示雙向阻力最短路徑搜索的依據(jù)網(wǎng)絡(luò)圖中的最短路徑應(yīng)該是一條簡單路徑，即是一條不與自身相交的路徑。最短路徑搜索的基本依據(jù)是，若從點S到點T有一條最短路徑，則該路徑上的任何點到S的距離都是最短的。為了進(jìn)行最短路徑搜索，令d(X,Y)表示點X到Y(jié)的距離，D(X)表示X到起始點S的最短距離。在搜索算法中，還需假定兩點之間的距離不為負(fù)。最短路徑搜索的步驟1、對起始點S作標(biāo)記，且對所有頂點令D(X)＝∞，Y＝S。2、對所有未作標(biāo)記的點按以下公式計算距離，D(X)＝min｛D(X),d(Y,X)＋D(Y)｝其中Y是己確定作標(biāo)記的點。取具有最小值的D(X)，并對X作標(biāo)記，令Y＝X若最小值的D(X)為∞，則說明S到所有未標(biāo)記的點都沒有路，算法終止；否則繼續(xù)。3、如果Y等于T，則已找到S到T的最短路徑，算法終止；否則轉(zhuǎn)2。最短路徑搜索例子A-C1、對A作標(biāo)記，按公式計算所有標(biāo)記點的距離。結(jié)果為D(B)＝4，D(C)＝∞，D(D)＝1[最小值]，D(E)＝2。2、對D作標(biāo)記，按公式算D(B)、D(C)、D(E)。D(B)＝min｛D(B),d(D,B)＋D(D)｝＝min｛4,∞＋1｝＝4D(C)＝min｛D(C),d(D,C)＋D(D)｝

＝min｛∞,9＋1｝＝10D(E)＝min｛D(E),d(D,E)＋D(D)｝＝min｛2,2＋1｝＝23、對E作標(biāo)記，計算D(B)，D(C)。D(B)＝min｛D(B),d(E,B)＋D(E)｝＝min｛4,1＋2｝＝3D(C)＝min｛D(C),d(E,C)＋D(E)｝＝min｛10,6＋2｝＝8最小值為D(B)＝3。4、對B作標(biāo)記，計算D(C)D(C)＝min｛D(C),d(B,C)＋D(B)｝＝min｛8,7＋3｝＝85、根據(jù)順序記錄的標(biāo)記點，以及最小值的取值情況，可得到最短路徑為A→E→C，最短距離為8最短路徑分析算例二_求點0到點5的最短距離D(X)＝min｛D(X),d(Y,X)＋D(Y)｝D(0)=0Y=0,X=1D(1)=∞Y=0,X=2D(2)＝min｛10,10＋0｝=10Y=0,X=3D(3)=∞Y=0,X=4D(4)＝min｛30,30＋0｝=30Y=0,X=5D(5)＝min｛100,100＋0｝=100D(X)＝min｛D(X),d(Y,X)＋D(Y)｝D(2)=10Y=2,X=1D(1)=∞Y=2,X=3D(3)＝min｛∞,50＋10｝=60Y=2,X=4D(4)＝min｛30,∞+10｝=

30Y=2,X=5D(5)＝min｛100,∞+10｝=

100D(X)＝min｛D(X),d(Y,X)＋D(Y)｝D(4)=30Y=4,X=1D(1)=min｛∞,∞

＋30｝=∞Y=4,X=3D(3)＝min｛60,20＋30｝=50Y=4,X=5D(5)＝min｛100,60＋30｝=90D(X)＝min｛D(X),d(Y,X)＋D(Y)｝D(3)=50Y=3,X=1D(1)=∞Y=3,X=5D(5)＝min｛90,10＋50｝=60用Dijkstra計算的結(jié)果

終點從v0到其它各個節(jié)點的最短路徑v1∞∞∞∞∞無v210（v0,v2）v3∞60(v0,v2,v3)50(v0,v4,v3)v430（v0,v4）30(v0,v4)v5100（v0,v5）100（v0,v5）90（v0,v4,v5）60（v0,v4,v3,v5）vjv2v4v3v5三、最小生成樹設(shè)T為圖G的一個生成樹，若把T中各邊的權(quán)數(shù)相加，則這個和數(shù)稱為生成樹T的權(quán)數(shù)。在G的所有生成樹中，權(quán)數(shù)最小的生成樹稱為G的最小生成樹。在實際應(yīng)用中，常有類似在n個城市間建立通信線路這樣的問題。這可用圖來表示，圖的頂點表示城市，邊表示兩城市間的線路，邊上所賦的權(quán)值表示代價。對n個頂點的圖可以建立許多生成樹，每一棵樹可以是一個通信網(wǎng)。若要使通信網(wǎng)的造價最低，就需要構(gòu)造圖的最小生成樹。生成樹是圖的極小連通子圖。一個連通的賦權(quán)圖G可能有很多的生成樹。構(gòu)造最小生成樹的依據(jù)1、在網(wǎng)中選擇n－1條邊連接網(wǎng)的n個頂點；2、形成的新樹T，其構(gòu)成邊的權(quán)為最??；3、舍去構(gòu)成回路的邊。最小生成樹的算法Kruskal（克羅斯克爾）算法（1956）避圈法：在圖中任取一個圈，從圈中去掉最大邊，將這個圈破掉。重復(fù)該過程，直到圖中沒有圈為止。剩余邊組成的圖即為最小生成樹。Prim（普賴姆）算法最小邊加入法：樹從任意頂點開始形成并逐漸生長直至該樹跨越了V中的所有頂點。在每一步，連接T中某結(jié)點到V-T中某結(jié)點的最短邊被加入到樹中，其特點是集合T中的邊總是只形成單棵樹。不需要對邊權(quán)排序，即可以直接在網(wǎng)路圖上操作，也可以在邊權(quán)矩陣上操作，適合計算機(jī)運(yùn)算避圈法構(gòu)造最小生成樹的步驟(1)先把圖G中的各邊按權(quán)數(shù)從小到大重新排列，并取權(quán)數(shù)最小的一條邊為T中的邊。(2)在剩下的邊中，按順序取下一條邊。若該邊與T中已有的邊構(gòu)成回路，則舍去該邊，否則選進(jìn)T中。(3)重復(fù)（2），直到有m-1條邊被選進(jìn)T中，這m-1條邊就是G的最小生成樹。避圈法生成最小生成樹算例為了使權(quán)數(shù)的總和為最小，應(yīng)該先對邊的權(quán)進(jìn)行排序，然后按權(quán)的大小依次選邊；選最短邊(2，3)；留該邊后，在圖中取權(quán)數(shù)第二小的邊，此時，可選(2，4)或(3，4)，設(shè)取(2，4)；去掉(2，4)邊，下一條權(quán)數(shù)最小的邊為(3，4)，但使用邊(3，4)后會出現(xiàn)回路，故不可取，應(yīng)去掉邊(3，4)；下一條權(quán)數(shù)最小的邊為(2，6)；依上述方法重復(fù)，可形成圖最小生成樹。如果前面不取(2，4)，而取(3，4)，則形成最小生成樹。Prim（普賴姆）算法1、根據(jù)網(wǎng)路寫出邊權(quán)矩陣，兩點間若沒有邊，則用表示；2、從v1開始標(biāo)記，在第一行打，劃去第一列；3、從所有打的行中找出尚未劃掉的最小元素，對該元素畫圈，劃掉該元素所在列，與該列數(shù)對應(yīng)的行打；4、若所有列都劃掉，則已找到最小生成樹(所有畫圈元素所對應(yīng)的邊)；否則，返回第3步。該算法中，打行對應(yīng)的節(jié)點在V1中，未劃去的列在V2中

Prim（普賴姆）法算例Prim算法是多項式算法Prim算法可以求最大生成樹網(wǎng)路的邊權(quán)可以有多種解釋，如效率四、最小費(fèi)用最大流在地理網(wǎng)絡(luò)中進(jìn)行著物質(zhì)和能量的流動，形成各種各樣的流。在網(wǎng)絡(luò)中的每段路徑都有“容量”和“費(fèi)用”兩個限制。最小費(fèi)用最大流就是尋找出：流量從A到B，如何選擇路徑、分配經(jīng)過路徑的流量，可以達(dá)到所用的費(fèi)用最小的要求。例如：n輛卡車要運(yùn)送物品，從A地到B地。由于每條路段都有不同的路費(fèi)要繳納，每條路能容納的車的數(shù)量有限制，如何分配卡車的出發(fā)路徑可以達(dá)到費(fèi)用最低，物品又能全部送到。地理網(wǎng)絡(luò)中流的性質(zhì)設(shè)有一個水管網(wǎng)絡(luò)，只有一個進(jìn)水口和一個出水口。每個管道用其截面積作為權(quán)數(shù)，用于反映單位時間內(nèi)可能通過的最大流量(稱為容量)。有穩(wěn)定水流注入進(jìn)水口，經(jīng)過網(wǎng)絡(luò)從出水口流出。這樣的一個穩(wěn)定的流動稱為“流”，具有如下性質(zhì)：1）流是有向的。2）管道的流量不可能超過最大流量。3）每個內(nèi)部節(jié)點處流入和流出節(jié)點的流量相等。4）進(jìn)水口的流量等于出水口的流量網(wǎng)絡(luò)流的基本問題設(shè)一個有向賦權(quán)圖G（V，E），V={s,a,b,c,…,s’}，其中有兩個特殊的節(jié)點s和s’。s稱為發(fā)點，s’稱為收點。圖中各邊的方向和權(quán)數(shù)表示允許的流向和最大可能的流量（容量）。問在這個網(wǎng)絡(luò)圖中從發(fā)點流出到收點匯集，最大可通過的實際流量為多少？流向的分布情況為怎樣?在實際應(yīng)用中，不僅要考慮使網(wǎng)絡(luò)上的流量最大，而且要使運(yùn)送流的費(fèi)用或代價最小。這就是最小費(fèi)用最大流量問題。最大流問題的求解

設(shè)有一個網(wǎng)絡(luò)圖G(V，E)，，V={s,a,b,c,…,s’}，E中的每條邊(i,j)對應(yīng)一個容量c(i,j)與輸送單位流量所需費(fèi)用a(i,j)。如有一個運(yùn)輸方案（可行流），流量為f(i,j)，則最小費(fèi)用最大流問題就是這樣一個求極值問題：

其中F為G的最大流的集合，即在最大流中尋找一個費(fèi)用最小的最大流。確定最小費(fèi)最大流的過程確定最小費(fèi)最大流的過程實際上是一個多次迭代的過程?；舅枷胧牵簭牧懔鳛槌跏伎尚辛鏖_始，在每次迭代過程中對每條邊賦予與c(i,j)（容量）、a(i,j)（單位流量運(yùn)輸費(fèi)用）、f(i,j)（現(xiàn)有流的流量）有關(guān)的權(quán)數(shù)ω(i,j)，形成一個有向賦權(quán)圖。再用求最短距離路徑的方法確定由發(fā)點s至收點s’的費(fèi)用最小的非飽和路，沿著該路增加流量，得到相應(yīng)的新流。經(jīng)過多次迭代，直至達(dá)到最大流為止。五、定位與分配模型定位與分配模型是根據(jù)需求點的空間分布，選擇給定數(shù)量的供應(yīng)點以使預(yù)定的目標(biāo)方程達(dá)到最佳結(jié)果。---最佳分配中心，最優(yōu)配置。包括：定位問題是指已知需求源的分布，確定在哪里布設(shè)供應(yīng)點最合適的問題；分配問題是確定這些需求源分別受哪個供應(yīng)點服務(wù)的問題。1、含義：不同的目標(biāo)方程就可以求得不同的結(jié)果。在運(yùn)籌學(xué)的理論中，定位與分配模型?？捎镁€性規(guī)劃求得全局性的最佳結(jié)果。由于其計算量以及內(nèi)存需求巨大，所以在實際應(yīng)用中常用一些啟發(fā)式算法(heuristicalgorithms)來逼近或求得最佳結(jié)果。

如P—中心的定位分配問題：在m個候選點中選擇P個供應(yīng)點為n個需求點服務(wù)，使得為這幾個需求點服務(wù)的總距離(或時間或費(fèi)用)為最少2、算法3、應(yīng)用：實際應(yīng)用中，選擇供應(yīng)點時，并不只是要使總的加權(quán)距離為最小，有時需要使總的服務(wù)范圍為最大，有時又限定服務(wù)的最大距離不能超過一定的值，因此僅僅是P中心模型不足以解決更多的實際問題，需要進(jìn)行修改、擴(kuò)充。SuperMap網(wǎng)絡(luò)分析過程構(gòu)建網(wǎng)絡(luò)數(shù)據(jù)集動態(tài)拓?fù)浞植酵負(fù)涮幚碜詣泳S護(hù)拓?fù)潢P(guān)系各種網(wǎng)絡(luò)分析交通分析服務(wù)區(qū)分析構(gòu)建網(wǎng)絡(luò)數(shù)據(jù)集通過線數(shù)據(jù)集自動拓?fù)渫瓿蓸?gòu)建網(wǎng)絡(luò)數(shù)據(jù)集拓?fù)溴e誤處理選項中“弧段求交”項必選各種網(wǎng)絡(luò)分析連通性分析鄰接點分析通達(dá)點分析通達(dá)邊分析關(guān)鍵點分析關(guān)鍵邊分析兩點是否連通分析最佳路徑、旅行商分析服務(wù)區(qū)分析最近設(shè)施查找鄰接點分析通達(dá)點分析通達(dá)邊分析關(guān)鍵點分析關(guān)鍵邊分析兩點間是否連通最佳路徑、旅行商分析（1）功能選取最佳路徑分析旅行商問題站點選取方式節(jié)點選取自由選取導(dǎo)入外部站點查看結(jié)果保存為數(shù)據(jù)集旅行商問題（TravelingSalemanProblem，TSP）又譯為旅行推銷員問題、貨郎擔(dān)問題，簡稱為TSP問題，是最基本的路線問題，該問題是在尋求單一旅行者由起點出發(fā)，通過所有給定的需求點之后，最后再回到原點的最小路徑成本。最佳路徑、旅行商分析（2）對訪問站點的順序的處理有所不同最佳路徑分析：必須按照指定的順序訪問網(wǎng)絡(luò)中的所有節(jié)點。旅行商分析：在保證在一次行程中訪問所有站點的前提下，訪問站點的次序是由自己決定的。因此旅行商分析的結(jié)果即包括所選擇的路徑，也包括它所確定的最優(yōu)的訪問次序。服務(wù)區(qū)分析根據(jù)指定的服務(wù)中心點及服務(wù)范圍分析服務(wù)中心點能夠提供的服務(wù)范圍。

最近設(shè)施查找查找與已知點（事件點）距離最近的設(shè)施點

8.3.4基于地形的空間分析數(shù)字高程模型（DigitalElevationModels,DEM)主要用于描述地面起伏狀況，可以用于各種地形信息提取，如坡度、坡向地表面積、地表粗糙度、高程及變異、谷脊特征、日照強(qiáng)度等，并進(jìn)行可視化等應(yīng)用分析。DEM在土木工程設(shè)計、軍事指揮等眾多領(lǐng)域被廣泛使用。DEM的主要表示模型GIS可以用三種通用的方法來模擬一個地形表面：柵格（規(guī)則格網(wǎng)）、不規(guī)則三角網(wǎng)及等高線。

TIN示意圖三維Grid示意圖一、基于DEM的信息提取1、坡度的計算地表單元的坡度就是其切平面的法線方向與Z軸的夾角。即切平面與水平面的夾角。若需求格網(wǎng)點上的坡度時，可取3×3的格網(wǎng)單元進(jìn)行計算。也可求出該格網(wǎng)點八個方向上的坡度，再取其平均值。坡度G的計算公式為：坡度的計算結(jié)果——坡度圖在計算出各地表單元的坡度后，可對不同的坡度設(shè)定不同的灰度級，或繪出等值線，即可得到坡度圖。2、坡向的計算坡向是地表單元的法向量在OXY平面上的投影與X軸之間的夾角。在計算出每個地表單元的坡向后，可制作坡向圖，通常把坡向分為東、南、西、北、東北、西北、東南、西南8類，再加上平地，共9類，用不同的色彩顯示，即可得到坡向圖。坡向通常要換算成正北方向起算的角度。其計算公式為：GridDEM上制作坡度、坡向圖

通常用3*3的格網(wǎng)窗口在DEM數(shù)據(jù)矩陣中連續(xù)移動計算完成。坡向的計算結(jié)果——坡向圖8.3.4.2基于DEM的可視化一、剖面分析研究地形剖面，常常可以以線代面，研究區(qū)域的地貌形態(tài)。如果在地形剖面上疊加上其它變量，例如坡度、土壤、植被、土地利用現(xiàn)狀等，可以提供土地利用規(guī)劃、工程選線和選址等的決策依據(jù)。已知兩點的坐標(biāo)A(x1，y1)，B(x2，y2)，則可求出兩點連線與格網(wǎng)或三角網(wǎng)的交點，以及各交點之間的距離。然后按選定的垂直比例尺和水平比例尺，按距離和高程繪出剖面圖。在格網(wǎng)或三角網(wǎng)交點的高程通?？刹捎煤唵蔚木€性內(nèi)插算出,且剖面圖不一定必須沿直線繪制，也可沿一條曲線繪制，但其繪制方法仍然是相同的。剖面分析圖形和計算2、通視分析

通視分析是指以某一點為觀察點，研究某一區(qū)域通視情況的地形分析。通視分析的核心是通視圖的繪制。1）方法：A.繪制通視圖的基本思路是：以O(shè)為觀察點，對格網(wǎng)DEM或三角網(wǎng)DEM上的每個點判斷通視與否，通視賦值為1，不通視賦值為0。由此可形成屬性值為0和1的格網(wǎng)或三角網(wǎng)。對此以0.5為值追蹤等值線，即得到以O(shè)為觀察點的通視圖。因此，判斷格網(wǎng)或三角網(wǎng)上的某一點是否通視成為關(guān)鍵。B.以觀察點O為軸，以一定的方位角間隔算出0°～360°的所有方位線上的通視情況。對于每條方位線，通視的地方繪線，不通視的地方斷開，或相反。這樣可得出射線狀的通視圖。

2）關(guān)鍵算法均是判斷格網(wǎng)或三角網(wǎng)上的某一點是否通視（即兩點是否可見）（1）判斷兩點之間的可視性的算法比較常見的一種算法基本思路如下：①確定過觀察點和目標(biāo)點所在的線段與XY平面垂直的平面S；②求出地形模型中與S相交的所有邊；③判斷相交的邊是否位于觀察點和目標(biāo)點所在的線段之上，如果有一條邊在其上，則觀察點和目標(biāo)點不可視。另一種算法是所謂的“射線追蹤法”。這種算法的基本思想是對于給定的觀察點V和某個觀察方向，從觀察點V開始沿著觀察方向計算地形模型中與射線相交的第一個面元，如果這個面元存在，則不再計算。顯然這種方法既可用于判斷兩點相互間是否可視，又可以用于限定區(qū)域的水平可視計算。通視分析計算若tgα＞max(tgβi,i＝A、B、C)，則OP通視，否則不通視。通視區(qū)域的分析通視分析的應(yīng)用通視分析從幾何上可分為點、線、面三類。點的通視是指視點與目標(biāo)點間；線的通視是指已知視點，計算視點的視野；區(qū)域的通視是指已知視點，分析其可視的地形表面區(qū)域集合。通視應(yīng)用可以分為五類：1）已知一個或一組觀察點，找出某一地形的可見區(qū)域。2）欲觀察到某一區(qū)域的全部地形表面，計算最少觀察點數(shù)量。3）在觀察點數(shù)量一定的前提下，計算能獲得的最大觀察區(qū)域。4）以最小代價建造觀察塔，要求全部區(qū)域可見。5）在給定建造代價的前提下，求最大可見區(qū)。觀察哨所的設(shè)定其位置應(yīng)該設(shè)在能監(jiān)視某一感興趣的區(qū)域，視線不能被地形