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