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