【正文】 以數(shù)學形態(tài)學擴張算法為代表，采用由實體柵格和八方向位移 L得到的 n方向柵格像元與原圖作布爾運算來完成，由于柵格數(shù)據量很大，特別是上述算法運算量級很大，當 L較大時實施有一定困難，且距離精度也尚待提高。 網絡分析 是通過研究網絡的狀態(tài)以及模擬和分析資源在網絡上的流動和分配情況，對網絡結構及其資源等的優(yōu)化問題進行研究的一種空間分析方法。網絡分析的理論基礎是圖論和運籌學。 在地理信息系統(tǒng)中，網絡分析功能依據圖論和運籌學原理，在計算機系統(tǒng)軟硬件的支持下，將與網絡有關的實際問題抽象化、模型化、可操作化，根據網絡元素的拓撲關系（線性實體之間、線性實體與結點之間、結點與結點之間的連結、連通關系），通過考察網絡元素的空間、屬性數(shù)據，對網絡的性能特征進行多方面的分析計算，從而為制定系統(tǒng)的優(yōu)化途徑和方案提供科學決策的依據，最終達到使系統(tǒng)運行最優(yōu)的目標。 網絡 模型 在城市之間建立通訊網絡，使其中任意兩個城市之間都有直接或間接的通訊聯(lián)系，假設已知每兩個城市之間通訊線路的成本，要求找出一個成本最低的通訊網絡。 3 1 城市 1 城市 2 6 7 9 城市 3 城市 4 城市 5 7 6 5 4 8 （ a） 通訊網絡問題中的數(shù)據 （ b） 一個最小成本通訊網絡 用圖形描述通訊網絡問題 3 1 城市 1 城市 2 6 城市 3 城市 4 城市 5 4 （ 1）圖 圖論中的“圖”是指由點集合 V和 V中點與點之間的連線的集合 E構成的二元組（ V, E）。 V 中的元素稱為結點， E 中的元素稱為邊。 圖論中所研究的圖是由實際問題抽象出來的邏輯關系圖，圖中點和線的位置與曲直無關緊要，點的多少和每條線是連接哪些點才是關鍵。 圖的結構 A B C D e3 e4 e5 e1 e2 e6 e7 ? 兩個端點重合的邊稱為環(huán)。 ? 如果有兩條邊的端點是同一對頂點，則稱這兩條邊為重邊 ? 既沒有環(huán)也沒有重邊的圖，稱為簡單圖。 ? 如果圖中的邊是有向的，則稱為有向圖，其中的邊叫做弧 ? 在無向圖中，首尾相接的一串邊的集合叫做路。 ? 在有向圖中，順向的首尾相接的一串邊的集合叫做有向路 ? 如果一個圖中，任意兩個結點之間都存在一個路，則稱之為連通圖。 ? 起點和終點為同一個結點的路稱為回路（或圈）。 ? 如果一個連通圖中不存在任何回路，則稱為樹。 ? 任意一個連通圖，去掉一些邊后形成的樹叫做連通圖的生成樹。 ? 給定一個圖，圖中的每一條邊賦以一個實數(shù)，稱這種數(shù)為邊的權數(shù)，稱這種圖為賦權圖。 ? 賦以權數(shù)的有向圖稱為賦權有向圖，也可稱之為網絡。 ? 根據需要賦權有向圖中的一條邊，必要時可以賦以多個權值，另外也可以給結點賦權，稱為點權網絡，相對于點權網絡，給邊賦權的網絡稱為邊權網絡。 ? 在機器實現(xiàn)中，鄰接矩陣表示法、關聯(lián)矩陣表示法、鄰接表表示法是用來描述圖與網絡常用的方法。 V2 V0 V1 100 V3 V5 V4 60 20 30 10 10 50 5 帶權的有向圖 鄰接矩陣 用來表示圖中任意兩點間的鄰接關系及其權值。如果兩點間有一條弧，則鄰接矩陣中對應的元素為 1；否則為 0（也可用 ∞ 表示兩點間無任何連接關系），鄰接矩陣為對稱矩陣。對于加權圖的鄰接矩陣表示，一條弧所對應的元素不再是 1，而是相應的權值。 2 4 （ a） 有向圖 1 5 3 （ b） 鄰接矩陣 0 1 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 0 0 1 1 0 有向圖及其鄰接矩陣 （ 2）鄰接矩陣與 關聯(lián)矩陣 關聯(lián)矩陣 中，每行對應圖的一個節(jié)點，每列對應圖的一條弧。如果一個節(jié)點是一條弧的起點，則關聯(lián)矩陣中對應的元素為 1；如果一個節(jié)點是一條弧的終點，則關聯(lián)矩陣中對應的元素為 – 1；如果一個節(jié)點與一條弧不關聯(lián)，則關聯(lián)矩陣中對應的元素為 0。 2 4 （ a） 有向圖 1 5 3 有向圖及其關聯(lián)矩陣 1 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 1 1 0 0 1 0 1 0 0 0 1 1 （ b）關聯(lián)矩陣 圖的鄰接表 是圖中所有節(jié)點鄰接表的集合。 2 4 （ a） 有向圖 1 5 3 有向圖及其鄰接表 0 4 2 1 2 3 4 5 8 6 0 4 2 6 3 0 3 0 9 3 0 3 5 0 7 4 （ b）鄰接表 網絡數(shù)據結構的基本組成部分和屬性 鏈（ Link） 網絡中流動的管線如街道、河流、水管，其狀態(tài)屬性包括阻力和需求。 結點（ Node） 網絡中鏈的結點，如港口、車站等，其狀態(tài)屬性包括阻力和需求等。 障礙（ Barrier），禁止網絡上流動的點。 拐點（ Turn），出現(xiàn)在網絡中的分割點上，其狀態(tài)有屬性和阻力，如拐彎的時間和限制（如在 8點到 18點不允許左拐）。 中心（ Center），是接受或分配資源的位置，如水庫、商業(yè)中心，電站等，其狀態(tài)包括資源容量（如總量），阻力限額（中心到鏈的最大距離或時間）。 站點（ Stop），在路徑選擇中資源增減的結點，如庫房、車站等，其狀態(tài)屬性有資源需求，如產品數(shù)量。 結點中的特殊類型 ? 路徑分析 路徑分析是 GIS中最基本的功能，其核心是對最佳路徑的求解。從網絡模型的角度看，最佳路徑的求解是在指定網絡的兩個結點之間找一條阻礙強度最小的路徑。另一種路徑分析功能是求解最佳游歷方案，又分為弧段最佳游歷方案求解和結點最佳游歷方案求解兩種。 ? 連通分析 現(xiàn)實中常需要知道從某一結點或邊出發(fā)能夠到達的全部結點或邊，這一類問題稱為連通分量求解；另一類連通分析問題是求解最少費用連通方案，即在耗費最小的情況下使全部結點相互連通。 網絡分析功能 ? 動態(tài)分段 動態(tài)分段技術是 GIS網絡分析中一種基于網絡線的動態(tài)分析、顯示和繪圖技術。通過建立一種比“弧段－結點”數(shù)據模型高級的“動態(tài)段－動態(tài)結點”模型，來實現(xiàn)根據不同的屬性按照某種度量標準對線性要素進行相對位置的劃分。 ? 地址匹配 地址匹配實質是對地理位置的查詢，涉及到地址的編碼。地址匹配與其他網絡分析功能結合起來，可以滿足實際工作中復雜的分析要求。 （ 3）最短路徑分析 最佳路徑分析也稱最優(yōu)路徑分析，以最短路徑分析為主。這里“最佳”包含很多含義，不僅指一般地理意義上的距離最短，還可以是成本最少、耗費時間最短、資源流量（容量）最大、線路利用率最高等標準。很多網絡相關問題，如最可靠路徑問題、最大容量路徑問題、易達性評價問題和各種路徑分配問題均可納入最佳路徑問題的范疇之中。無論判斷標準和實際問題中的約束條件如何變化，其核心實現(xiàn)方法都是最短路徑算法。 最短路徑問題從算法研究的角度考慮最短路徑問題通?？蓺w納為兩大類：一類是所有點對之間的最短路徑，另一類是單源點間的最短路徑問題。 不但求出起點到終點的最短路徑及其長度，而且求出了起點到圖中其他各個頂點的最短路徑及長度。 Dijkstra算法 a b c d 1 2 5 6 10 f e 1 1 4 3 S’ S 令 S={a, b, f}，則 S’={c, d, e}， 求 d(a, S’)？ （ 4）中心 選址問題 中心點選址問題中，最佳選址位置的判定標準，是使其所在的頂點與圖中其它頂點之間的 最大距離 達到最小，或者使其所在的頂點到圖中其它頂點之間的距離之和 達到最小。 這個選址問題實際上就是求網絡圖的中心點問題。這類選址問題適宜于醫(yī)院、消防站等服務設施的布局問題。 v6 v8 v1 v7 v5 v4 v2 v3 8 9 3 6 3 2 5 3 7 5 7 中心選址問題的實例 例如 ， 某縣要在其所轄的 8個鄉(xiāng)鎮(zhèn)之一修建一個消防站 ， 為8個鄉(xiāng)鎮(zhèn)服務 ， 要求消防站至最遠鄉(xiāng)鎮(zhèn)的距離達到最小 。 假設該 8個鄉(xiāng)鎮(zhèn)之間的交通網絡被抽象為無向賦權連通圖 ， 權值為鄉(xiāng)鎮(zhèn)之間的距離 。 下面求解消防站應設在哪個鄉(xiāng)鎮(zhèn) ，即哪個頂點 ？ 首先，用 Dijkstra算法計算出 每一個頂點 vi至其它各頂點vj的最短路徑長度 dij(i, j=1,2,… ,6)， 寫出距離矩陣： 60 61 91 61 52 56 54 73 其次 ， 求 距離 矩陣中每行的最大值 ， 即各個頂點的最大服務距離 ， 得 e(v1)=14, e(v2)=15, e(v3)=20, e(v4)=12, e(v5)=15, e(v6)=17, e(v7)=12, e(v8)=20 最后計算最大服務距離的最小值 。 顯然 ，e(v4) = e(v7) = min{ e(vi)}。 所以 ， 消防站應建在 v4或 v7點所在的鄉(xiāng)鎮(zhèn) 。 60 61 91 61 52 56 54 73 要求消防站至 所有 鄉(xiāng)鎮(zhèn)的距離達到最?。? 消防站應建在 v5點所在的鄉(xiāng)鎮(zhèn) 大部分 GIS軟件以分層的方式組織地理景觀，將地理景觀按主題分層提取，同一地區(qū)的整個數(shù)據層集表達了該地區(qū)地理景觀的內容。每個主題層可以用矢量結構的點線面圖層文件表達，也可以用柵格結構的圖層文件進行表達。 疊置分析是 GIS最常用的提取空間隱含信息的手段之一。該方法來源于傳統(tǒng)的透明材料疊置。既將來自不同數(shù)據源的圖紙繪于透明紙上，在透光桌上將其疊放在一起，然后用筆勾出感興趣的部分。 疊置分析是將兩層或多層地圖要素進行疊置產生一個新要素層的操作，其結果將原來要素分割成新的要素，新要素綜合了原來兩層或多層要素所具有的屬性。也就是說，疊置分析不僅生成了新的空間關系，還將輸入數(shù)據層的屬性聯(lián)系起來產生了新的屬性關系。疊置分析是對新要素的屬性按一定的數(shù)學模型進行計算分析，進而產生用戶需要的結果或回答用戶提出的問題。 點與多邊形的疊置分析，實質是計算包含關系（包含分析），判斷各個點的歸屬（落在哪個多邊形內）。疊置的結果是為每點產生一個新的屬性。例如，井位與規(guī)劃區(qū)疊置，可找到包含每個井的區(qū)域。 （ 1）點與多邊形疊置 在完成點與多邊形幾何關系計算后，還要進行屬性信息處理。最簡單的方式是將多邊形屬性信息疊置到其中的點上（或反之）。如有多點分布在同一多邊形，則要采取一些特殊的規(guī)則。 點與多邊形的疊置通常不產生新的數(shù)據層，只是把屬性信息疊置到原圖層中，然后通過屬性查詢間接獲得點與多邊形疊置的需要信息。 point name poly 1 農行取款機 A 2 建行取款機 B 3 農行取款機 C 4 商行取款機 C A B C 自動取款機位置圖 居民區(qū)分布圖 疊置圖層 2 1 3 4 poly name point A 進德小區(qū) 1 B 陽光小區(qū) 2 C 花園小區(qū) 3,4 （ 2）線與多邊形疊置 ?線與多邊形的疊置，是 比較線上坐標與多邊形坐標的關系 ，判斷線是否落在多邊形內。 ?疊置后每條線被它穿過的多邊形打斷成新弧段，要將原線和多邊形的屬性信息一起賦給新弧段。 Line ID Old ID Poly 1 1 C 2 2 C 3 2 B 4 3 C 5 3 A 6 3 B 1 2 4 A B C 1 2 3 3 5 6 政區(qū)圖 河流圖 新弧段圖層 1 2 3 居民區(qū) 疊置 區(qū) 居民區(qū) ID 污染分級 A1 A 1 A2 A 2 A3 A 3 B1 B 1 B3 B 3 居民區(qū) ID A B 污染分級 1 2 3 疊置圖 污染分級圖 （ 3）多邊形的疊置 A B 1 2 3 B1 B3 A1 A2 A3 ?原來多邊形要素分割成新要素，新要素綜合了原來兩層或多層的屬性。 ① 并操作（ Union） ② 交操作（ Intersect） ③ 擦除操作（ Erase） ④ 裁剪操作（ Clip） 多邊形的疊置 70 ① 并操作 (A∪ B) 保留兩個圖層的所有圖形要素和屬性數(shù)據。 A∪ B A B 71 ② 交操作 (A∩B) 保留兩個圖層共同的部分，其余部分將被消除。 A∩B A B ③ 擦除操作 (AA∩B) 輸出層保留以