第5章空間幾何關(guān)系分析

1、第第5章章 空間幾何關(guān)系分析空間幾何關(guān)系分析 5.1 鄰近度分析鄰近度分析5.2 疊加分析疊加分析5.3 網(wǎng)絡(luò)分析網(wǎng)絡(luò)分析5.1 鄰近度分析 鄰近度（Proximity）是定性描述空間目標距離關(guān)系的重要物理量之一，表示地理空間中兩個目標地物距離相近的程度。 泰森多邊形分析泰森多邊形分析 5.1.15.1.2緩沖區(qū)分析緩沖區(qū)分析 5.1.1 緩沖區(qū)分析緩沖區(qū)分析 緩沖區(qū)緩沖區(qū) 是指為了識別某一地理實體或空間物體對其周圍地物的影響度而在其周圍建立的具有一定寬度的帶狀區(qū)域。緩沖區(qū)分析緩沖區(qū)分析 則是對一組或一類地物按緩沖的距離條件，建立緩沖區(qū)多邊形，然后將這一圖層與需要進行緩沖區(qū)分析的圖層進行疊加分

2、析，得到所需結(jié)果的一種空間分析方法。 緩沖區(qū)分析適用于點、線或面對象，如點狀的居民點、線狀的河流和面狀的作物區(qū)等?；驹砘驹?.1.1 緩沖區(qū)分析緩沖區(qū)分析道路中心線道路中心線基本原理基本原理5.1.1 緩沖區(qū)分析緩沖區(qū)分析 從數(shù)學(xué)的角度看，緩沖區(qū)分析的基本思想是給定一個空間對象或集合，確定其鄰域，鄰域的大小由鄰域半徑R決定，因此對象Oi的緩沖區(qū)定義為：Bi = x | d (x, Oi) R，即半徑為R的對象Oi的緩沖區(qū)，Bi為距Oi的距離小于等于R的全部點的集合，d一般指最小歐氏距離，但也可以為其他定義的距離，如網(wǎng)絡(luò)距離，即空間物體間的路徑距離。對于對象集合 O = Oi | i=1

3、, 2, , n，其半徑為R的緩沖區(qū)是各個對象緩沖區(qū)的并集，即 ：niiBB1基本原理基本原理5.1.1 緩沖區(qū)分析緩沖區(qū)分析（a） 不同寬度緩沖區(qū)干流支流 鄰域半徑R即緩沖距離（寬度），是緩沖區(qū)分析的主要數(shù)量指標，可以是常數(shù)或變量。 空間對象還可以生成多個緩沖帶?；驹砘驹恚╞）環(huán)狀緩沖區(qū)5.1.1 緩沖區(qū)分析緩沖區(qū)分析具有不同特性的緩沖區(qū)（a）靜態(tài)緩沖區(qū)a = b （b）動態(tài)緩沖區(qū)a b abaaba 根據(jù)研究對象影響力的特點，緩沖區(qū)可以分為均質(zhì)與非均質(zhì)兩種。 基本原理基本原理5.1.1 緩沖區(qū)分析緩沖區(qū)分析 矢量數(shù)據(jù)緩沖區(qū)的建立方法 緩沖區(qū)建立方法緩沖區(qū)建立方法（a）單點形成的緩沖

4、區(qū) （b）點群形成的緩沖區(qū) （c）分級點形成的緩沖區(qū)點形成的緩沖區(qū)形式 點要素的緩沖區(qū)5.1.1 緩沖區(qū)分析緩沖區(qū)分析 矢量數(shù)據(jù)緩沖區(qū)的建立方法 線要素的緩沖區(qū)線形成的緩沖區(qū)形式（a）單線形成的緩沖區(qū) （b）多線形成的緩沖區(qū) （c）分級線形成的緩沖區(qū)緩沖區(qū)建立方法緩沖區(qū)建立方法5.1.1 緩沖區(qū)分析緩沖區(qū)分析 矢量數(shù)據(jù)緩沖區(qū)的建立方法 面要素的緩沖區(qū)面形成的緩沖區(qū)形式（a）單一面形成的緩沖區(qū) （b）多個面形成的緩沖區(qū) （c）分級面形成的緩沖區(qū)緩沖區(qū)建立方法緩沖區(qū)建立方法5.1.1 緩沖區(qū)分析緩沖區(qū)分析 柵格數(shù)據(jù)緩沖區(qū)的建立方法 緩沖區(qū)建立方法緩沖區(qū)建立方法柵格數(shù)據(jù)的緩沖區(qū)分析通常稱為推移或擴散

5、（Spread），推移或擴散實際上是模擬主體對鄰近對象的作用過程，物體在主體的作用下沿著一定的阻力表面移動或擴散，距離主體越遠所受到的作用力越弱。 5.1.1 緩沖區(qū)分析緩沖區(qū)分析緩沖區(qū)建立方法緩沖區(qū)建立方法5.1.1 緩沖區(qū)分析緩沖區(qū)分析 動態(tài)緩沖區(qū)緩沖區(qū)建立方法緩沖區(qū)建立方法現(xiàn)實世界中很多空間對象或過程對于周圍的影響并不是隨著距離的變化而固定不變的，需要建立動態(tài)緩沖區(qū)，根據(jù)空間物體對周圍空間影響度的變化性質(zhì)，可以采用不同的分析模型。 當緩沖區(qū)內(nèi)各處隨著距離變化，其影響度變化速度相等時，采用線性模型； 當距離空間物體近的地方比距離空間物體遠的地方影響度變化快時，采用二次模型； 當距離空間物體

6、近的地方比距離空間物體遠的地方影響度變化更快時，采用指數(shù)模型。5.1.1 緩沖區(qū)分析緩沖區(qū)分析 緩沖區(qū)實現(xiàn)有兩種基本算法：矢量方法和柵格方法。緩沖區(qū)實現(xiàn)的基本算法緩沖區(qū)實現(xiàn)的基本算法矢量方法使用較廣，產(chǎn)生時間較長，相對比較成熟，具體的幾何算法是中心線擴張法，又稱加寬線法或圖形加粗法，通過以中心軸線為核心做平行曲線，生成緩沖區(qū)邊線，再對生成邊線求交、合并，最終生成緩沖區(qū)邊界。柵格方法以數(shù)學(xué)形態(tài)學(xué)擴張算法為代表，采用由實體柵格和八方向位移L得到的n方向柵格像元與原圖作布爾運算來完成，由于柵格數(shù)據(jù)量很大，特別是上述算法運算量級很大，當L較大時實施有一定困難，且距離精度也尚待提高。5.1.1 緩沖區(qū)分

7、析緩沖區(qū)分析 角分線法 緩沖區(qū)實現(xiàn)的基本算法緩沖區(qū)實現(xiàn)的基本算法RdB角分線法 角分線法簡單易行，但算法存在不足： 難以最大限度地保證緩沖區(qū)左右邊線的等寬性；校正過程復(fù)雜；算法模型欠結(jié)構(gòu)化。5.1.1 緩沖區(qū)分析緩沖區(qū)分析緩沖區(qū)實現(xiàn)的基本算法緩沖區(qū)實現(xiàn)的基本算法 凸角圓弧法 凸角圓弧法對于凸部的圓弧處理使其能最大限度地保證左右平行曲線的等寬性，避免了角分線法所帶來的異常情況。 凸角圓弧法原理5.1.1 緩沖區(qū)分析緩沖區(qū)分析 凸角圓弧法的算法實施步驟為 緩沖區(qū)實現(xiàn)的基本算法緩沖區(qū)實現(xiàn)的基本算法 直線性判斷直線性判斷為簡化計算過程，凸角圓弧法的第一步是進行相鄰三點的直線性判斷。當相鄰三點處于近似共

8、線狀態(tài)時，用直線代替。常用的直線性判斷方法是點到直線距離法，即直接利用解析幾何中的距離公式 其中，Ax+By+C = 0為過首末點的直線方程，x、y為相鄰三點中相對中間點的坐標，d為該中間點到直線Ax+By+C = 0的距離，當d小于某一給定值時，相鄰三點可視為直線，簡化計算過程。)(/22BACByAxd5.1.1 緩沖區(qū)分析緩沖區(qū)分析緩沖區(qū)實現(xiàn)的基本算法緩沖區(qū)實現(xiàn)的基本算法 凸角圓弧法的算法實施步驟為 折點凸凹性的判斷折點凸凹性的判斷凸角圓弧法的關(guān)鍵在于對凸凹部分的不同處理，因此折線頂點處的凸凹特性的判斷是非常重要的步驟，它能確定何處需要用圓弧連接而何處需要用直線求交。這個問題可轉(zhuǎn)化為兩個

9、矢量的叉積：把相鄰兩個線段看成兩個矢量，其方向取為坐標點序方向。若前一個矢量以最小的角度掃向第二個矢量時呈逆時針，則為凸頂點，反之，為凹頂點。 凸頂點圓弧的嵌入凸頂點圓弧的嵌入設(shè)圓弧的始邊與終邊分別為 、 ，其坐標形式分別為： ， ，為弦弧逼近誤差（如圖所示）。其中， ， ， ， 。 AB),(yxaaA),(yxbbB 21XXax21YYay23XXbx23YYbyABA213uv凸頂點圓弧的嵌入5.1.1 緩沖區(qū)分析緩沖區(qū)分析 凸角圓弧法的算法實施步驟為 緩沖區(qū)實現(xiàn)的基本算法緩沖區(qū)實現(xiàn)的基本算法 邊線關(guān)系的判別和處理邊線關(guān)系的判別和處理當軸線的彎曲空間不能容許左右平行曲線無壓蓋地通過時，

10、就產(chǎn)生邊線自相交問題，形成若干個自相交多邊形，如圖所示。自相交多邊形分為兩種情況：島嶼多邊形與重疊區(qū)多邊形。 邊線多邊形的形成5.1.1 緩沖區(qū)分析緩沖區(qū)分析緩沖區(qū)實現(xiàn)的基本算法緩沖區(qū)實現(xiàn)的基本算法島嶼多邊形&重疊區(qū)多邊形及其自動識別：矢量數(shù)據(jù)格式表示的曲線具有方向性，取曲線坐標串的方向為曲線前進的方向。當中心軸線被取定方向后，其兩側(cè)的平行曲線也就自然地獲得了左右屬性，稱左邊線和右邊線。對于左邊線，島嶼多邊形呈逆時針方向；對于右邊線，島嶼多邊形呈順時針方向。對于重疊區(qū)多邊形左邊線呈順時針方向；右邊線呈逆時針方向 島嶼多邊形與重疊區(qū)多邊形（a）左邊線的島嶼多邊形與重疊區(qū)多邊形 （b）右邊

11、線的島嶼多邊形與重疊區(qū)多邊形5.1.1 緩沖區(qū)分析緩沖區(qū)分析緩沖區(qū)實現(xiàn)的基本算法緩沖區(qū)實現(xiàn)的基本算法 凸角圓弧法的算法實施步驟為 緩沖區(qū)邊界的最終形成緩沖區(qū)邊界的最終形成將重疊區(qū)進行合并繪制出最外圍邊線，同時繪出島嶼輪廓，就形成了最終的緩沖區(qū)邊界。要注意的是，利用緩沖區(qū)進行檢索的時候，按最外圍邊線所形成的圓頭或方頭緩沖區(qū)檢索之后，要扣除按所有島嶼進行檢索的結(jié)果。5.1.1 緩沖區(qū)分析緩沖區(qū)分析對于矢對于矢量數(shù)據(jù)量數(shù)據(jù)對于柵對于柵格數(shù)據(jù)格數(shù)據(jù)緩沖區(qū)多邊形的重疊合并數(shù)學(xué)運算法矢量柵格轉(zhuǎn)換法矢量柵格混合法對緩沖區(qū)內(nèi)的柵格賦上一個與其影響度惟一對應(yīng)的值，如果發(fā)生重疊的區(qū)域具有相同的影響度，則取任一值；

12、如果發(fā)生重疊的區(qū)域具有不同影響度等級，則影響度小的服從于影響度大的。緩沖區(qū)實現(xiàn)的基本算法緩沖區(qū)實現(xiàn)的基本算法5.1.1 緩沖區(qū)分析緩沖區(qū)分析緩沖區(qū)作為一個獨立的數(shù)據(jù)層可以參與疊加分析，常應(yīng)用到道路、河流、居民點、工廠（污染源）等生產(chǎn)生活設(shè)施的空間分析，為不同工作需要（如道路修整、河道改建、居民區(qū)拆遷、污染范圍確定等）提供科學(xué)依據(jù)。結(jié)合不同的專業(yè)模型，緩沖區(qū)分析能夠在景觀生態(tài)、規(guī)劃、軍事應(yīng)用等領(lǐng)域發(fā)揮更大的作用。例如，利用緩沖區(qū)分析和相鄰緩沖區(qū)的景觀結(jié)構(gòu)總體變異系數(shù)方法對自然保護區(qū)進行自然景觀和人為影響景觀的分割研究。在虛擬軍事演練系統(tǒng)中，緩沖區(qū)分析方法是對雷達群的合成探測范圍和干擾效果進行研究

13、的一種非常有效的手段。 緩沖區(qū)分析應(yīng)用緩沖區(qū)分析應(yīng)用為了能根據(jù)離散分布的氣象站降雨量數(shù)據(jù)來計算某地平均的降雨量，荷蘭氣候?qū)W家A.H.Thiessen提出了一種新的計算方法，即將所有相鄰氣象站連成三角形，作三角形各邊的垂直平分線，每個氣象站周圍的若干垂直平分線便圍成一個多邊形，用這個多邊形內(nèi)所包含的惟一一個氣象站的降雨強度來表示這個多邊形區(qū)域內(nèi)的降雨強度，該多邊形稱為泰森多邊形（Thiessen Polygons或Thiessen Tesselations，又稱Voronoi或Dirichlet多邊形）。5.1.2 泰森多邊形分析泰森多邊形及其特性泰森多邊形及其特性 ABCD泰森多邊形u其幾何定

14、義為：設(shè)平面上的一個離散點集P = P1, P2, , Pn ，其中任意兩個點都不共位，即Pi Pj（i j, i1, 2, , n, j1, 2, , n），且任意四點不共圓，則任意離散點Pi 的泰森多邊形的定義為在泰森多邊形 Ti 中，任意一個內(nèi)點到該泰森多邊形的發(fā)生點 Pi 的距離都小于該點到其他任何發(fā)生點 Pj 的距離。這些發(fā)生點 Pi（i1, 2, , n）也稱為泰森多邊形的控制點或質(zhì)心（Centroid）。 5.1.2 泰森多邊形分析泰森多邊形及其特性泰森多邊形及其特性 為歐氏距離：dPPPPPPxdPxdxTjijijii,| ),(),(u 泰森多邊形因其生成過程的特殊性，具有

15、以下一些特性：5.1.2 泰森多邊形分析泰森多邊形及其特性泰森多邊形及其特性 1 1每個泰森多邊形內(nèi)僅含有一個控制點數(shù)據(jù)；3位于泰森多邊形邊上的點到其兩邊控制點的距離相等；2泰森多邊形內(nèi)的點到相應(yīng)控制點的距離最近；4在判斷一個控制點與其他哪些控制點相鄰時，可直接根據(jù)泰森多邊形得出結(jié)論，即若泰森多邊形是n邊形，則與n個離散點相鄰。 Delaunay三角網(wǎng)是由與相鄰泰森多邊形共享一條邊的相關(guān)點連接而成的三角網(wǎng)，它與泰森多邊形是對偶關(guān)系。5.1.2 泰森多邊形分析Delaunay三角網(wǎng)的構(gòu)建三角網(wǎng)的構(gòu)建 泰森多邊形及其對偶Delaunay三角網(wǎng)5.1.2 泰森多邊形分析uDelaunay三角網(wǎng)具有以

16、下特征：Delaunay三角網(wǎng)是惟一的；三角網(wǎng)的外邊界構(gòu)成了給定點集的凸多邊形“外殼”；沒有任何點在三角形的外接圓內(nèi)部，反之，如果一個三角網(wǎng)滿足此條件，那么它就是Delaunay三角網(wǎng)（如圖）。如果將三角網(wǎng)中的每個三角形的最小角進行升序排列，則Delaunay三角網(wǎng)的排列得到的數(shù)值最大，從這個意義上講，Delaunay三角網(wǎng)是“最接近于規(guī)則化” 的三角網(wǎng)。 Delaunay三角網(wǎng)的構(gòu)建三角網(wǎng)的構(gòu)建 Delaunay三角網(wǎng)構(gòu)建1234567821345678構(gòu)建三角網(wǎng)凸包插值算法凸包插值算法是Tsai在1993年提出的在n維歐拉空間中構(gòu)造Delaunay三角網(wǎng)的一種通用算法，包括三個主要步驟：5

17、.1.2 泰森多邊形分析Delaunay三角網(wǎng)的構(gòu)建三角網(wǎng)的構(gòu)建 凸包的生成123456789圖 1 凸包生成凸包三角剖分圖 2 環(huán)切邊界法構(gòu)成若干Delaunay三角形123456789離散點內(nèi)插圖 3 離散點內(nèi)插入三角剖分形成新的三角剖分123456789泰森多邊形建立過程：建立Delaunay三角網(wǎng)，對離散點和形成的三角形進行編號，并記錄每個三角形是由哪三個離散點構(gòu)成的；找出與每個離散點相鄰的所有三角形的編號，并記錄下來； 將與每個離散點相鄰的所有三角形按順時針或逆時針方向進行排序；計算出每個三角形的外接圓圓心，并記錄下來；連接相鄰三角形的外接圓圓心，即可得到泰森多邊形。對于三角網(wǎng)邊緣的

18、泰森多邊形，可作垂直平分線與圖廓相交，與圖廓一起構(gòu)成泰森多邊形。5.1.2 泰森多邊形分析泰森多邊形的建立泰森多邊形的建立 泰森多邊形的柵格算法實現(xiàn)過程 一種柵格算法是先將圖形柵格化為數(shù)字圖像，然后對該數(shù)字圖像進行歐氏距離變換，得到灰度圖像，而泰森多邊形的邊一定處于該灰度圖像的脊線上；再通過相應(yīng)的圖像運算，提取灰度圖像的這些脊線，就得到最終的泰森多邊形。另外還可采用以發(fā)生點為中心點，同時向周圍相鄰八方向做柵格擴張運算（一種距離變換），兩個相鄰發(fā)生點擴張運算的交線即為泰森多邊形的鄰接邊，三個相鄰發(fā)生點擴張運算的交點即為泰森多邊形的頂點。泰森多邊形的建立泰森多邊形的建立用柵格方法得到的泰森多邊形5

19、.1.2 泰森多邊形分析5.2 疊加分析 疊加分析概述疊加分析概述5.2.1空間要素圖形疊加空間要素圖形疊加5.2.2空間要素屬性疊加空間要素屬性疊加5.2.35.2.1 疊加分析概述疊加分析是指將同一地區(qū)、同一比例尺、同一數(shù)學(xué)基礎(chǔ)，不同信息表達的兩組或多組專題要素的圖形或數(shù)據(jù)文件進行疊加，根據(jù)各類要素與多邊形邊界的交點或多邊形屬性建立具有多重屬性組合的新圖層，并對那些在結(jié)構(gòu)和屬性上既相互重疊，又相互聯(lián)系的多種現(xiàn)象要素進行綜合分析和評價；或者對反映不同時期同一地理現(xiàn)象的多邊形圖形進行多時相系列分析，從而深入揭示各種現(xiàn)象要素的內(nèi)在聯(lián)系及其發(fā)展規(guī)律的一種空間分析方法。 a2結(jié)果圖層abc1234a

20、1c2c4b3c1c3b2+=輸入圖層疊加圖層疊加分析的基本概念5.2.1 疊加分析概述 地理空間數(shù)據(jù)的處理與分析目的是獲得空間潛在信息，疊加分析是非常有效的提取隱含信息的工具之一。例如，將全國水文監(jiān)測站分布圖與政區(qū)圖疊加，得到一個新的圖層，既保留了水文監(jiān)測站的點狀圖形及屬性，同時附加了行政分區(qū)的屬性信息，據(jù)此可以查詢水文站點屬于哪個省區(qū)，或者查詢某省區(qū)內(nèi)共有多少個水文站點；又如將某區(qū)域的土地利用類型圖與土壤pH值狀態(tài)圖、地下水埋深圖、植被覆蓋圖等專題地圖疊加，生成新的圖層后按照濕地的定義形成屬性判別標準，從而判斷該區(qū)域是否為濕地。將一個點層作為輸入圖層疊加到一個多邊形圖層上，即通過計算點與多

21、邊形線段的相對位置，來判斷這個點是否在多邊形內(nèi)，從而確定是否進行屬性信息的疊加。5.2.2 空間要素圖形疊加 點與多邊形的疊加點與多邊形的疊加點與多邊形疊加分析將一個線圖層作為輸入圖層疊加到一個多邊形圖層上，要進行線段與多邊形的空間關(guān)系判別，主要是比較線上坐標與多邊形的坐標，判斷線段是否落在多邊形內(nèi)。5.2.2 空間要素圖形疊加 線與多邊形的疊加線與多邊形的疊加線與多邊形疊加分析5.2.2 空間要素圖形疊加 多邊形與多邊形的疊合是指將兩個不同圖層的多邊形要素相疊合，產(chǎn)生輸出層的新多邊形要素，用以解決地理變量的多準則分析、區(qū)域多重屬性的模擬分析、地理特征的動態(tài)變化分析，以及圖幅要素更新、相鄰圖幅

22、拼接、區(qū)域信息提取等。多邊形與多邊形的疊加多邊形與多邊形的疊加層1屬性：地貌層2屬性：土壤結(jié)果層屬性：地貌、土壤5.2.2 空間要素圖形疊加 多邊形與多邊形的疊加多邊形與多邊形的疊加根據(jù)疊加結(jié)果要保留不同的空間特征，常用的GIS軟件通常提供了三種類型的多邊形疊加分析操作，即并、疊和、交。輸入圖層疊加圖層結(jié)果圖層+=+=+=多邊形的不同疊加方式并疊和交 矢量數(shù)據(jù)屬性疊加處理更多地使用邏輯疊加運算，即布爾邏輯運算中的包含、交、并、差等。5.2.3 空間要素屬性疊加 矢量數(shù)據(jù)疊加分析矢量數(shù)據(jù)疊加分析12345A123456A線與多邊形的疊加屬性邏輯運算LineID 1 2 3 4 5 6 Old I

23、D 1 2 3 4 5 1Poly A A A 0 0 0LineID 1 2 3 Old ID 1 2 3 Poly A A A LineID 4 5 6 Old ID 4 5 1Poly 0 0 0（a）邏輯并 （b）邏輯交 （c）邏輯差 柵格數(shù)據(jù)中對于同一區(qū)域、同一比例尺、同一數(shù)學(xué)基礎(chǔ)的不同信息表達的要素來說，其柵格編號不會發(fā)生變化，即對于任意柵格單元用作標識的行列號I0、J0是不變的，進行疊加的時候只是增加了屬性表的長度，下表表示進行多重疊加后的柵格多邊形的數(shù)據(jù)結(jié)構(gòu)：柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析柵格編號屬性1屬性2屬性nI0J0R1R2Rn5.2.3 空間要素屬性疊加 柵格數(shù)據(jù)來源

24、復(fù)雜，疊加分析操作的前提是要將其轉(zhuǎn)換為統(tǒng)一的柵格數(shù)據(jù)格式，如BMP、GRID等，且各個疊加層必須具有統(tǒng)一的地理空間，即具有統(tǒng)一的空間參考（包括地圖投影、橢球體、基準面等），統(tǒng)一的比例尺以及具有統(tǒng)一的分辨率（即像元大小）。 柵格數(shù)據(jù)的疊加分析操作主要通過柵格之間的各種運算來實現(xiàn)?？梢詫螌訑?shù)據(jù)進行各種數(shù)學(xué)運算如加、減、乘、除、指數(shù)、對數(shù)等，也可通過數(shù)學(xué)關(guān)系式建立多個數(shù)據(jù)層之間的關(guān)系模型。 5.2.3 空間要素屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析基于不同的運算方式和疊加形式：5.2.3 空間要素屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析基于像元與像元之間一一對應(yīng)的運算，每一個像元都是基于它自

25、身的運算，不考慮其他的與之相鄰的像元；局部變換將具有相同屬性值的像元作為整體進行分析運算；分帶變換基于研究區(qū)內(nèi)所有像元的運算，輸出柵格的每一個像元值是基于全區(qū)的柵格運算，這里像元是具有或沒有屬性值的網(wǎng)格（柵格）。全局變換以某一像元為中心，將周圍像元的值作為算子，進行簡單求和、求平均值、最大值、最小值等；鄰域變換柵格疊加變換類型：局部變換每一個像元經(jīng)過局部變換后的輸出值與這個像元本身有關(guān)系，而不考慮圍繞該像元的其他像元值。 3 輸入柵格 輸出柵格 輸入柵格 乘數(shù)柵格 輸出柵格（a）單層局部變換 （b）多層局部變換局部變換2 0 1 12 3 0 23 2 31 1 26 0 3 36 9 0 6

26、9 6 93 3 62 0 1 12 3 0 23 2 31 1 21 1 2 21 2 2 22 2 3 32 3 3 42 0 2 22 6 0 46 6 92 3 85.2.3 空間要素屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析鄰域變換如果要計算某一像元的值，就將該像元看作一個中心點，一定范圍內(nèi)圍繞它的格網(wǎng)可以看作它的輻射范圍，這個中心點的值取決于采用何種計算方法將周圍格網(wǎng)的值賦給中心點，其中的輻射范圍可自定義。鄰域變換2 0 1 12 3 0 23 0 2 31 1 0 2鄰域求和7 8 7 410 13 12 910 12 13 95 7 8 7輸入柵格 輸出柵格5.2.3 空間要素

27、屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析分帶變換將同一區(qū)域內(nèi)具有相同像元值的格網(wǎng)看作一個整體進行分析運算，稱為分帶變換。 分帶變換2 0 112 3 02 0 21 1 02輸入柵格 分帶柵格 輸出柵格1 2 345 6 781 2 345 5 558 7 558 6 78 7 85 5 785.2.3 空間要素屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析全局變換全局變換是基于區(qū)域內(nèi)全部柵格的運算，一般指在同一網(wǎng)格內(nèi)進行像元與像元之間距離的量測。歐幾里德距離歐幾里德距離運算 111 22.0 1.0 0.0 0.01.4 1.0 1.0 0.01.0 0.0 1.0 1.01.4 1.0 1.

28、4 2.0輸入柵格 輸出柵格5.2.3 空間要素屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析 在距離量測中像元間距離考慮全部的源數(shù)據(jù)，且要求像元間距離最短，但沒有考慮其他因素如運費等。成本距離量測運算比空間距離量測運算要復(fù)雜得多，需要另一個格網(wǎng)來定義經(jīng)過每個像元的成本或阻抗。交通費用計算5.0 3.0 0.0 0.03.5 2.5 2.8 0.01.5 0.0 2.5 2.02.1 3.0 2.8 4.0輸入柵格 成本柵格 輸出柵格 111a 2b c2 2 444 4 332 1 412 5 335.2.3 空間要素屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析柵格邏輯疊加?xùn)鸥駭?shù)據(jù)中的像元值有時無

29、法用數(shù)值型字符來表示，不同專題要素用統(tǒng)一的量化系統(tǒng)表示也比較困難，故使用邏輯疊加更容易實現(xiàn)各個柵格層之間的運算。圖層之間的布爾邏輯運算包括：與（AND）、或（OR）、非（NOT）、異或（OR）等。A B A AND B A OR B A NOT B A OR B 0 0 0 0 0 01 0 0 1 1 10 1 0 1 0 11 1 1 1 0 0布爾邏輯運算示例5.2.3 空間要素屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析假設(shè)某市政府要在轄區(qū)范圍內(nèi)選擇理想地點建立一個垃圾場，有關(guān)垃圾場的選址條件如下所述：區(qū)域地表物質(zhì)應(yīng)具有低滲透率，以阻止可溶性物質(zhì)快速滲入地下水中；區(qū)域與現(xiàn)有市政區(qū)域范圍保

30、持一定距離；區(qū)域不屬于環(huán)境敏感區(qū)；區(qū)域應(yīng)屬于農(nóng)業(yè)區(qū)，而非市政區(qū)或工業(yè)區(qū)；區(qū)域的地表平均坡度平穩(wěn)，并小于某個極限值；區(qū)域不發(fā)生洪水。5.2.3 空間要素屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析二值邏輯疊加模型：根據(jù)垃圾場選址條件組織有關(guān)圖件資料，包括表土滲透性圖、城區(qū)范圍圖、生態(tài)敏感度分布圖、城鄉(xiāng)區(qū)劃圖、地表坡度圖和洪泛區(qū)分布圖等。建立垃圾場選址的模型。該模型將以上圖層結(jié)合起來進行布爾邏輯運算，結(jié)果生成二值圖，其中值為1的地點表示滿足上述垃圾場選址的全部條件，值為0則表示不滿足選址條件。5.2.3 空間要素屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊加分析具體模型如下：將各個圖層二值化（TRUE，F(xiàn)A

31、LSE）或（0，1）。本例中各層數(shù)據(jù)的布爾邏輯條件如下：Ca = 地表滲透性級別為低級；Cb = 距離城區(qū)邊界的距離1km；Cc = 生態(tài)敏感性為不敏感級別；Cd = 土地利用類型為農(nóng)業(yè)用地；Ce = 地表坡度 2；Cf = 不屬于洪泛區(qū)范圍。對于各輸入數(shù)據(jù)層的布爾邏輯條件變量進行邏輯與運算，在區(qū)域某位置點上如果所有數(shù)據(jù)層的條件變量都是所要求的值，則結(jié)果變量OUTPUT為“1”，其他情況下為“0”。OUTPUTCa AND Cb AND Cc AND Cd AND Ce AND Cf生成二值圖。滿足條件的位置就是二值圖中值為“1”的地點。5.2.3 空間要素屬性疊加 柵格數(shù)據(jù)疊加分析柵格數(shù)據(jù)疊

32、加分析5.3 網(wǎng)絡(luò)分析5.3.5流分析流分析5.3.6動態(tài)動態(tài)分段分段技技術(shù)術(shù)5.3.4資資源分配源分配5.3.7地址匹配地址匹配5.3.1網(wǎng)絡(luò)網(wǎng)絡(luò)分析分析概概述述5.3.3連連通分析通分析5.3.2最佳路最佳路徑徑分析分析5.3.1 網(wǎng)絡(luò)分析概述 網(wǎng)絡(luò)分析網(wǎng)絡(luò)分析 是通過研究網(wǎng)絡(luò)的狀態(tài)以及模擬和分析資源在網(wǎng)絡(luò)上的流動和分配情況，對網(wǎng)絡(luò)結(jié)構(gòu)及其資源等的優(yōu)化問題進行研究的一種空間分析方法。網(wǎng)絡(luò)分析的理論基礎(chǔ)是圖論和運籌學(xué)。在地理信息系統(tǒng)中，網(wǎng)絡(luò)分析功能依據(jù)圖論和運籌學(xué)原理，在計算機系統(tǒng)軟硬件的支持下，將與網(wǎng)絡(luò)有關(guān)的實際問題抽象化、模型化、可操作化，根據(jù)網(wǎng)絡(luò)元素的拓撲關(guān)系（線性實體之間、線性實體與

33、結(jié)點之間、結(jié)點與結(jié)點之間的連結(jié)、連通關(guān)系），通過考察網(wǎng)絡(luò)元素的空間、屬性數(shù)據(jù)，對網(wǎng)絡(luò)的性能特征進行多方面的分析計算，從而為制定系統(tǒng)的優(yōu)化途徑和方案提供科學(xué)決策的依據(jù)，最終達到使系統(tǒng)運行最優(yōu)的目標。 5.3.1 網(wǎng)絡(luò)分析概述 在城市之間建立通訊網(wǎng)絡(luò)，使其中任意兩個城市之間都有直接或間接的通訊聯(lián)系，假設(shè)已知每兩個城市之間通訊線路的成本，要求找出一個成本最低的通訊網(wǎng)絡(luò)。圖論中的基本概念圖論中的基本概念31城市1城市2679城市3城市4城市576548（a）通訊網(wǎng)絡(luò)問題中的數(shù)據(jù)（b）一個最小成本通訊網(wǎng)絡(luò)用圖形描述通訊網(wǎng)絡(luò)問題31城市1城市26城市3城市4城市545.3.1 網(wǎng)絡(luò)分析概述 圖論中的“圖”

34、是指由點集合V和V中點與點之間的連線的集合E構(gòu)成的二元組（V, E）。V 中的元素稱為結(jié)點，E 中的元素稱為邊。 圖論中所研究的圖是由實際問題抽象出來的邏輯關(guān)系圖，圖中點和線的位置與曲直無關(guān)緊要，點的多少和每條線是連接哪些點才是關(guān)鍵。圖論中的基本概念圖論中的基本概念圖的結(jié)構(gòu)ABCDe3e4e5e1e2e6e75.3.1 網(wǎng)絡(luò)分析概述圖論中的基本概念圖論中的基本概念有向圖V1V2V3V4e1e2e3e4e5e6樹V1V2V3V4V5V6V7V8V10V9兩個端點重合的邊稱為環(huán)。如果有兩條邊的端點是同一對頂點，則稱這兩條邊為重邊。既沒有環(huán)也沒有重邊的圖，稱為簡單圖。如果圖中的邊是有向的，則稱為有向

35、圖，其中的邊叫做弧。在無向圖中，首尾相接的一串邊的集合叫做路。在有向圖中，順向的首尾相接的一串邊的集合叫做有向路。如果一個圖中，任意兩個結(jié)點之間都存在一個路，則稱之為連通圖。起點和終點為同一個結(jié)點的路稱為回路（或圈）。如果一個連通圖中不存在任何回路，則稱為樹。任意一個連通圖，去掉一些邊后形成的樹叫做連通圖的生成樹。 5.3.1 網(wǎng)絡(luò)分析概述給定一個圖，圖中的每一條邊賦以一個實數(shù)，稱這種數(shù)為邊的權(quán)數(shù)，稱這種圖為賦權(quán)圖。賦以權(quán)數(shù)的有向圖稱為賦權(quán)有向圖，也可稱之為網(wǎng)絡(luò)。根據(jù)需要賦權(quán)有向圖中的一條邊，必要時可以賦以多個權(quán)值，另外也可以給結(jié)點賦權(quán)，稱為點權(quán)網(wǎng)絡(luò)，相對于點權(quán)網(wǎng)絡(luò)，給邊賦權(quán)的網(wǎng)絡(luò)稱為邊權(quán)網(wǎng)絡(luò)

36、。在機器實現(xiàn)中，鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、鄰接表表示法是用來描述圖與網(wǎng)絡(luò)常用的方法。圖論中的基本概念圖論中的基本概念V2V0V1100V3V5V46020301010505帶權(quán)的有向圖5.3.1 網(wǎng)絡(luò)分析概述鄰接矩陣鄰接矩陣 用來表示圖中任意兩點間的鄰接關(guān)系及其權(quán)值。如果兩點間有一條弧，則鄰接矩陣中對應(yīng)的元素為 1；否則為 0（也可用表示兩點間無任何連接關(guān)系），鄰接矩陣為對稱矩陣。對于加權(quán)圖的鄰接矩陣表示，一條弧所對應(yīng)的元素不再是1，而是相應(yīng)的權(quán)值。 圖論中的基本概念圖論中的基本概念24（a）有向圖153（b）鄰接矩陣0 1 1 0 00 0 0 1 00 1 0 0 00 0 1 0

37、10 0 1 1 0有向圖及其鄰接矩陣5.3.1 網(wǎng)絡(luò)分析概述關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣 中，每行對應(yīng)圖的一個節(jié)點，每列對應(yīng)圖的一條弧。如果一個節(jié)點是一條弧的起點，則關(guān)聯(lián)矩陣中對應(yīng)的元素為1；如果一個節(jié)點是一條弧的終點，則關(guān)聯(lián)矩陣中對應(yīng)的元素為1；如果一個節(jié)點與一條弧不關(guān)聯(lián)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為0。圖論中的基本概念圖論中的基本概念24（a）有向圖153有向圖及其關(guān)聯(lián)矩陣1-100010-100010-100-110000-1100001-100-101000-11（b）關(guān)聯(lián)矩陣5.3.1 網(wǎng)絡(luò)分析概述 圖的鄰接表鄰接表 是圖中所有節(jié)點鄰接表的集合。圖論中的基本概念圖論中的基本概念24（a）有向圖15

38、3有向圖及其鄰接表04212345860426303093035074（b）鄰接表5.3.1 網(wǎng)絡(luò)分析概述 網(wǎng)絡(luò)數(shù)據(jù)模型是現(xiàn)實世界網(wǎng)絡(luò)系統(tǒng)（如交通網(wǎng)、通訊網(wǎng)、自來水管網(wǎng)、煤氣管網(wǎng)等 ）的抽象表示。按照幾何形態(tài)，空間實體被抽象為點、線、面目標，構(gòu)成網(wǎng)絡(luò)的最基本元素是線性實體以及這些實體的連接交匯點。前者稱為網(wǎng)線或鏈（Link），后者稱為結(jié)點（Node）。 鏈（Link） 鏈是構(gòu)成網(wǎng)絡(luò)的骨架，是現(xiàn)實世界中各種線路的抽象和資源傳輸或通信聯(lián)絡(luò)的通道，可以代表公路、鐵路、街道、航線、水管、煤氣管、輸電線、河流等。鏈包括圖形信息和屬性信息，鏈的屬性信息包括阻礙強度和資源需求量，鏈的阻礙強度是指在通過一條鏈

39、時所需要花費的時間或者費用等，如資源流動的時間、速度。鏈是有方向的，當資源沿著網(wǎng)絡(luò)中的不同方向流動時所受到的阻礙強度可能相同，也可能不同。網(wǎng)絡(luò)數(shù)據(jù)模型網(wǎng)絡(luò)數(shù)據(jù)模型5.3.1 網(wǎng)絡(luò)分析概述 結(jié)點（Node）結(jié)點是網(wǎng)線的端點，又是網(wǎng)線的匯合點，可以表示交叉路口、中轉(zhuǎn)站、河流匯合點等，其狀態(tài)屬性除了包括阻礙強度和資源需求量等，還有下面幾種特殊的類型。 障礙（Barrier）：禁止資源在網(wǎng)絡(luò)中的鏈上流動的點。 拐點（Turn）：出現(xiàn)在網(wǎng)絡(luò)鏈中的分割結(jié)點上，狀態(tài)屬性有阻礙強度，如拐彎的時間和限制（例如在8：00到18：00不允許左拐等）。在地理網(wǎng)絡(luò)中，拐點對資源的流動有很大影響，資源沿著某一條鏈流動到有

40、關(guān)結(jié)點后，既可以原路返回，也可以流向與該結(jié)點相連的任意一條鏈，如果阻礙強度值為負數(shù)，則表示資源禁止流向特定的弧段。網(wǎng)絡(luò)數(shù)據(jù)模型網(wǎng)絡(luò)數(shù)據(jù)模型5.3.1 網(wǎng)絡(luò)分析概述 結(jié)點（Node） 中心（Center）：網(wǎng)絡(luò)中具有一定的容量，能夠接受或分配資源的結(jié)點所在的位置。如水庫商業(yè)中心、電站、學(xué)校等，其狀態(tài)屬性包括資源容量（如總量）阻礙強度（如中心到鏈的最大距離或時間限制）。資源容量決定了為中心服務(wù)的弧段的數(shù)量，中心的阻礙強度是指沿某一路徑到達中心所經(jīng)歷的弧段總阻礙強度的最大值。 站點（Stop）：在路徑選擇中資源增減的結(jié)點，如庫房車站等，其狀態(tài)屬性有兩種，一種是站的阻礙強度，它代表與站有關(guān)的費用、時間

41、等，如在某個庫房裝卸貨物所用時間等；一種是站的資源需求量，如產(chǎn)品數(shù)量、學(xué)生數(shù)、乘客數(shù)等。站的需求量為正值時，表示在該站上增加資源；若為負值，則表示在該站上減少資源。網(wǎng)絡(luò)數(shù)據(jù)模型網(wǎng)絡(luò)數(shù)據(jù)模型5.3.1 網(wǎng)絡(luò)分析概述 網(wǎng)絡(luò)分析功能路徑分析路徑分析路徑分析是GIS中最基本的功能，其核心是對最佳路徑的求解。從網(wǎng)絡(luò)模型的角度看，最佳路徑的求解是在指定網(wǎng)絡(luò)的兩個結(jié)點之間找一條阻礙強度最小的路徑。另一種路徑分析功能是求解最佳游歷方案，又分為弧段最佳游歷方案求解和結(jié)點最佳游歷方案求解兩種。連通分析連通分析現(xiàn)實中常需要知道從某一結(jié)點或邊出發(fā)能夠到達的全部結(jié)點或邊，這一類問題稱為連通分量求解；另一類連通分析問題是

42、求解最少費用連通方案，即在耗費最小的情況下使全部結(jié)點相互連通。網(wǎng)絡(luò)分析功能網(wǎng)絡(luò)分析功能5.3.1 網(wǎng)絡(luò)分析概述 網(wǎng)絡(luò)分析功能資源分配資源分配資源分配也稱定位與分配問題，包括目標選址和將需求按最近（這里遠近是按加權(quán)距離來確定的）原則尋找供應(yīng)中心（資源發(fā)散或匯集地）兩個問題。流分析流分析 流是資源在結(jié)點間的傳輸。流分析問題主要是按照某種優(yōu)化標準（時間最少、費用最低、路程最短或運送量最大等）設(shè)計的運送方案，網(wǎng)絡(luò)流理論是其基礎(chǔ)理論。網(wǎng)絡(luò)分析功能網(wǎng)絡(luò)分析功能5.3.1 網(wǎng)絡(luò)分析概述 網(wǎng)絡(luò)分析功能動態(tài)分段動態(tài)分段動態(tài)分段技術(shù)是GIS網(wǎng)絡(luò)分析中一種基于網(wǎng)絡(luò)線的動態(tài)分析、顯示和繪圖技術(shù)。通過建立一種比“弧段結(jié)

43、點”數(shù)據(jù)模型高級的“動態(tài)段動態(tài)結(jié)點”模型，來實現(xiàn)根據(jù)不同的屬性按照某種度量標準對線性要素進行相對位置的劃分。 地址匹配地址匹配地址匹配實質(zhì)是對地理位置的查詢，涉及到地址的編碼。地址匹配與其他網(wǎng)絡(luò)分析功能結(jié)合起來，可以滿足實際工作中復(fù)雜的分析要求。網(wǎng)絡(luò)分析功能網(wǎng)絡(luò)分析功能5.3.2 最佳路徑分析 最佳路徑分析也稱最優(yōu)路徑分析，以最短路徑分析為主。這里“最佳”包含很多含義，不僅指一般地理意義上的距離最短，還可以是成本最少、耗費時間最短、資源流量（容量）最大、線路利用率最高等標準。很多網(wǎng)絡(luò)相關(guān)問題，如最可靠路徑問題、最大容量路徑問題、易達性評價問題和各種路徑分配問題均可納入最佳路徑問題的范疇之中。無

44、論判斷標準和實際問題中的約束條件如何變化，其核心實現(xiàn)方法都是最短路徑算法。 最短路徑問題從算法研究的角度考慮最短路徑問題通?？蓺w納為兩大類：一類是所有點對之間的最短路徑，另一類是單源點間的最短路徑問題。5.3.2 最佳路徑分析 Dijkstra算法基本思想其基本思路是：假設(shè)每個點都有一對標號（dj, pj），其中dj是從起源點 s 到點 j 的最短路徑的長度（從頂點到其本身的最短路徑是零路（沒有弧的路），其長度等于零）；pj 則是從s到 j 的最短路徑中 j 點的前一點。 初始化。起源點設(shè)置為ds = 0，ps為空，并標記起源點s，記k = s，其他所有點設(shè)為未標記點。 檢驗從所有已標記的點

45、k 到其直接連接的未標記的點j的距離，并設(shè)置dj = mindj, dk+lkj，其中，lkj為從點k到j(luò)的直接連接距離。 選取下一個點。從所有未標記的結(jié)點中，選取dj 中最小的一個i，di = mindj, 所有未標記的點 j ，點i就被選為最短路徑中的一點，并設(shè)為已標記的點。 找到點i的前一點。從已標記的點中找到直接連接到點i的點j*，作為前一點，記為i = j* 標記點i。如果所有點已標記，則算法完全推出，否則記k = i，重復(fù)步驟。 最短路徑算法最短路徑算法5.3.2 最佳路徑分析左圖為某一帶權(quán)有向圖，若對其施行Dijkstra算法，則所得從V0到其余各頂點的最短路徑以及運算過程中距離

46、的變化情況如右表所示。 V2V0V1100V3V5V46020301010505帶權(quán)的有向圖終點從源點V0到各終點的距離值和最短路徑的求解過程i = 1i = 2i = 3i = 4i = 5V1V210（V0, V2）V360（V0, V2, V 3）50（V0, V4, V3）V430（V 0, V 4）30（V0, V 4）V5100（V0, V5）100（V0, V5）90（V0, V4, V5）60（V0, V4, V3, V5）VjV2V4V3V5SV0, V2V0, V2, V3V0, V2, V3, V4V0, V2, V3, V4, V5最短路徑算法最短路徑算法5.3.2 最

47、佳路徑分析 弗洛伊德算法其基本思想是：假設(shè)求從頂點 Vi 到 Vj 的最短路徑。若從Vi 到 Vj 有弧，則從Vi 到 Vj 存在一條長度為 dij 的路徑，該路徑不一定是最短路徑，需要進行 n 次試探。首先判別?。╒i, V1）和?。╒1, Vj）是否存在。如果存在，則比較（Vi, Vj）和（Vi, V1, Vj）的路徑長度，較短者為從Vi 到 Vj 的中間頂點的序號不大于1的最短路徑。假如在路徑上再增加一個頂點V2，若路徑（Vi, , V2）和路徑（V2 , , Vj）分別是當前找到的中間頂點的序號不大于1的最短路徑，那么后來的路徑（Vi, , V2 , , Vj）就有可能是從Vi 到 V

48、j 的中間頂點的序號不大于 2 的最短路徑。將它和已經(jīng)得到的從Vi 到 Vj 的中間頂點的序號不大于 1 的最短路徑相比較，從中選出中間頂點的序號不大于 2 的最短路徑之后，再增加一個頂點 V3，繼續(xù)進行試探。依次類推，在經(jīng)過 n 次比較之后，最后求得的必是從Vi 到 Vj 的最短路徑。 最短路徑算法最短路徑算法5.3.2 最佳路徑分析 矩陣算法 該算法是利用矩陣來求出圖的最短距離矩陣。算法步驟可表示為：最短路徑算法最短路徑算法 D = AA2A3 An-2 = (di,j)nn。 求出A, A2, A3 , , An-2 ； 已知圖的鄰接矩陣A；5.3.2 最佳路徑分析最佳路徑分析在汽車導(dǎo)航

49、系統(tǒng)和各種應(yīng)急系統(tǒng)（如110報警、119火警以及醫(yī)療救護系統(tǒng)等）中應(yīng)用非常廣泛，系統(tǒng)應(yīng)用需求決定了最佳路徑分析應(yīng)是高效率的，比如一般要求計算出到出事地點的最佳路徑的時間必須是在13s內(nèi)，且在行車過程中需要實時計算出車輛前方的行駛路線。但前面介紹的三種算法在時間復(fù)雜度上都不盡如人意，很難滿足不斷發(fā)展的各種系統(tǒng)的要求，從而促使人們考慮從各個角度解決其實現(xiàn)的效率問題。針對不同的網(wǎng)絡(luò)特征、應(yīng)用需求及具體的軟硬件環(huán)境，各種最短路徑算法不斷涌現(xiàn)，在空間復(fù)雜度、時間復(fù)雜度、易實現(xiàn)性及應(yīng)用范圍等方面各具特色。 最短路徑算法的優(yōu)化最短路徑算法的優(yōu)化5.3.2 最佳路徑分析 以路徑分析應(yīng)用最廣泛的交通道路網(wǎng)絡(luò)為例

50、，提供一個解決實際問題的基本模式。 假定某地區(qū)交通管理部門接到舉報在該區(qū)域內(nèi)某一地點發(fā)生交通事故，需要有關(guān)人員立刻趕到現(xiàn)場，選擇一條路途最短的行進路線到達指定地點。在解決問題之前要了解交通網(wǎng)絡(luò)數(shù)據(jù)的基本特征。首先，對于一定區(qū)域范圍內(nèi)龐大的交通網(wǎng)絡(luò)要考慮它的存儲結(jié)構(gòu)，既要有利于網(wǎng)絡(luò)分析算法的實現(xiàn)，又能夠在節(jié)約存儲空間的前提下根據(jù)需要擴充數(shù)據(jù)，對交通網(wǎng)絡(luò)進行綜合分析。然后是網(wǎng)絡(luò)搜索，主要依據(jù)求解單源點間最短路徑的戴克斯徒拉算法思想，同樣也可以對其進行優(yōu)化改進以提高效率。根據(jù)實際應(yīng)用的需要，首先將網(wǎng)絡(luò)邊的權(quán)值設(shè)為兩結(jié)點間的距離，并定義沿著起點到終點的方向為空間有效方向，相反的方向為無效方向；然后賦給

51、網(wǎng)絡(luò)邊、結(jié)點相應(yīng)的字段值，并定義站點、拐點、橋梁等特殊地物的屬性，最后通過具體的程序設(shè)計來實現(xiàn)搜索過程。路徑分析的實現(xiàn)路徑分析的實現(xiàn)5.3.3 連通分析 在地理網(wǎng)絡(luò)中從某一點出發(fā)能夠到達的全部結(jié)點或邊有哪些，如何選擇對于用戶來說成本最小的線路，即連通分析所要解決的問題。連通分析的求解過程實質(zhì)上是對應(yīng)的圖的生成樹的求解過程，其中研究最多的是最小生成樹問題?；靖拍罨靖拍頥1V2V4V3無向圖（連通圖）5.3.3 連通分析 連通性是圖論的一個重要概念。在無向圖G = (V, E)中，如果從頂點Vs到頂點Vt有路徑，則稱Vs和Vt是連通的。如果對于圖G中的任意兩個頂點Vi,VjV，Vi和Vj都是連

52、通的，則稱G為連通圖。無向圖及其連通分量（a）無向圖GV9V2V1V8V3V5V6V7V4V9V8V2V1V3V5V6V7V4（b）G的三個連通分量基本概念基本概念5.3.3 連通分析 一個連通圖的生成樹是含有該連通圖的全部頂點的一個極小連通子圖，包含三個條件： 它是連通的； 它包含原有連通圖的全部結(jié)點； 它不含任何回路。 依據(jù)連通圖的生成樹的定義可知，若連通圖G的頂點個數(shù)為n，則G的生成樹的邊數(shù)為n-1；樹無回路，但不相鄰頂點連成一邊，就會得到一個回路；樹是連通的，但去掉任意一條邊，就會變?yōu)椴贿B通的。 基本概念基本概念5.3.3 連通分析 從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一頂點僅被

53、訪問一次，這一過程叫做圖的遍歷。遍歷圖的基本方法有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索?；舅枷胧牵簭膱D中的某個頂點出發(fā)，然后訪問任意一個該點的鄰接點，并以該點的鄰接點為新的出發(fā)點繼續(xù)訪問下一層級的鄰接點，從而使整個搜索過程向縱深方向發(fā)展，直到圖中的所有頂點都被訪問過為止。從圖中的某個頂點出發(fā)，訪問該頂點之后依次訪問它的所有鄰接點，然后分別從這些鄰接點出發(fā)按深度優(yōu)先搜索遍歷圖的其他頂點，直至所有頂點都被訪問到為止。基本概念基本概念5.3.3 連通分析 圖（a）是一個具有8個結(jié)點的網(wǎng)絡(luò)圖，對其分別進行深度優(yōu)先搜索和廣度優(yōu)先搜索，其搜索過程如圖（b）和（c）。（a）網(wǎng)絡(luò)圖V1V2V3V4V5V8V6V

54、7基本概念基本概念V1V2V3V4V5V8V6V71234567（b）廣度優(yōu)先搜索過程V1V2V3V4V5V8V6V71524673（c）深度優(yōu)先搜索過程5.3.3 連通分析 克羅斯克爾（Kruskal）算法是1956年提出的，俗稱“避圈法”。設(shè)圖G是由m個結(jié)點構(gòu)成的連通賦權(quán)圖，則構(gòu)造最小生成樹的步驟如下：最小生成樹算法最小生成樹算法1先把圖G中的各邊按權(quán)數(shù)從小到大重新排列，并取權(quán)數(shù)最小的一條邊為生成樹T中的邊；2在剩下的邊中，按順序取下一條邊，若該邊與生成樹中已有的邊構(gòu)成回路，則舍去該邊，否則選擇進入生成樹中；3重復(fù)步驟2，直到有m-1條邊被選進T中，這m-1條邊就是圖G的最小生成樹。5.3

55、.3 連通分析 構(gòu)造最小生成樹的另一個著名算法Prim算法的基本思想是：假設(shè)N = (V, E)是連通網(wǎng)，生成的最小生成樹為T = (V, TE)，求T的步驟如下： 最小生成樹算法最小生成樹算法1初始化：U =u0，TE =；2在所有 uU，vV-U 的邊（u, v）E中，找一條權(quán)最小的邊（u0, v0），TE+（u0, v0）TE，v0+UU；3如果U = V，則算法結(jié)束，否則重復(fù)步驟2；4最后得到最小生成樹T = ，其中TE為最小生成樹的邊集。5.3.3 連通分析 圖1中帶權(quán)圖最小生成樹求算過程如圖2所示。1243566536264551圖 1 帶權(quán)圖1243562124356241243

56、56241124356245112435632451圖 2 求帶權(quán)圖最小生成樹的過程（a） （b） （c） （d） （e）最小生成樹算法最小生成樹算法5.3.4 資源分配 在多數(shù)的應(yīng)用中，需要解決在網(wǎng)絡(luò)中選定幾個供應(yīng)中心，并將網(wǎng)絡(luò)的各邊和點分配給某一中心，使各中心所覆蓋范圍內(nèi)每一點到中心的總的加權(quán)距離最小，實際上包括定位與分配兩個問題。 定位是指已知需求源的分布，確定在哪里布設(shè)供應(yīng)點最合適的問題； 分配指的是已知供應(yīng)點，確定其為哪些需求源提供服務(wù)的問題。 5.3.4 資源分配 選址功能涉及在某一指定區(qū)域內(nèi)選擇服務(wù)性設(shè)施的位置，如確定市郊商店區(qū)消防站工廠飛機場倉庫等的最佳位置。 選址問題的數(shù)學(xué)模

57、型取決于可供選擇的范圍，以及所選位置的質(zhì)量判斷標準這兩個條件。在一個地理網(wǎng)絡(luò)中，能夠從網(wǎng)絡(luò)的結(jié)點和邊上找到一些特定的點使它們滿足某種優(yōu)化條件，這些點可用于較簡單的定位問題。 選址問題（定位問題）選址問題（定位問題） 5.3.4 資源分配 給定一個地理網(wǎng)絡(luò)D =（V, E），其中V表示地理網(wǎng)絡(luò)結(jié)點的集合，E表示地理網(wǎng)絡(luò)邊的集合。令 d(p, q)表示從頂點 p 到頂點 q 之間的距離；令R表示矩陣，矩陣的第 p、q 個元素是 d(p, q)，矩陣R的元素稱為頂點頂點距離（Vertex-vertex Distance，VVD）； 表示從網(wǎng)絡(luò)邊（vi, vj）上的f_點到結(jié)點 q 之間的距離，這個長

58、度稱為點頂點距離（Point-vertex Distance，PVD）；表示從頂點到網(wǎng)絡(luò)邊（vi, vj）的最大距離，此長度稱為頂點弧距離（Vertex-arc Distance）。 選址問題（定位問題）選址問題（定位問題） 5.3.4 資源分配從頂點p到任一頂點的最大距離從頂點p到所有頂點的總距離從頂點p到所有弧的最大距離從頂點p到所有弧的總距離 從網(wǎng)絡(luò)邊（vi, vj）上的f_點到任一結(jié)點的最大距離 從網(wǎng)絡(luò)邊（vi, vj）上的f_點到所有各結(jié)點的總距離),(max)(qpdpMVVqqqpdpSVV),()(),( ,(max)(),(jipdpMVAji),(),( ,()(jijip

59、dpSVAqjifdjifMPVq),_(max),_(qqjifdjifSPV),_(),_(選址問題（定位問題）選址問題（定位問題） 5.3.4 資源分配 基于以上變量的定義，給出有關(guān)中心點和中位點的概念。使最大距離達到最小的位置稱為網(wǎng)絡(luò)的中心點，使最大距離總和達到最小的位置稱為網(wǎng)絡(luò)的中位點。一個地理網(wǎng)絡(luò)的中心點主要有中心、一般中心、絕對中心和一般絕對中心等；一個地理網(wǎng)絡(luò)的中位點主要有中位點、一般中位點、絕對中位點和一般絕對中位點等。 選址問題（定位問題）選址問題（定位問題） 5.3.4 資源分配地理網(wǎng)絡(luò)的中心點是網(wǎng)絡(luò)中距最遠結(jié)點最近的一個結(jié)點vx，即地理網(wǎng)絡(luò)的一般中心是距最遠點最近的一個

60、結(jié)點vx，即地理網(wǎng)絡(luò)的絕對中心是距最遠結(jié)點最近的任意一點vx，即地理網(wǎng)絡(luò)的一般絕對中心是距最遠點最近的任意一點vx，即)(miniMVVxMVVi）（)(min)(iMVAxMVAi),_(min),_(srfMPVjifMPV),_(min),_(srfMPAjifMPA選址問題（定位問題）選址問題（定位問題） 5.3.4 資源分配地理網(wǎng)絡(luò)的中位點是從該點到其他各結(jié)點有最小總距離的一個結(jié)點vx，即地理網(wǎng)絡(luò)的一般中位點是從該點到其他各結(jié)點有最小總距離的一個結(jié)點vx，即地理網(wǎng)絡(luò)的絕對中位點是從該點到所有各結(jié)點有最小總距離的任意一點，即地理網(wǎng)絡(luò)的一般絕對中位點是從該點到所有各條網(wǎng)絡(luò)邊有最小的總距離的任意一