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

關(guān)于空間幾何關(guān)系分析第1頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1鄰近度分析鄰近度（Proximity）是定性描述空間目標(biāo)距離關(guān)系的重要物理量之一，表示地理空間中兩個(gè)目標(biāo)地物距離相近的程度。泰森多邊形分析

5.1.15.1.2緩沖區(qū)分析

第2頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析

緩沖區(qū)是指為了識別某一地理實(shí)體或空間物體對其周圍地物的影響度而在其周圍建立的具有一定寬度的帶狀區(qū)域。緩沖區(qū)分析則是對一組或一類地物按緩沖的距離條件，建立緩沖區(qū)多邊形，然后將這一圖層與需要進(jìn)行緩沖區(qū)分析的圖層進(jìn)行疊加分析，得到所需結(jié)果的一種空間分析方法。緩沖區(qū)分析適用于點(diǎn)、線或面對象，如點(diǎn)狀的居民點(diǎn)、線狀的河流和面狀的作物區(qū)等?；驹淼?頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析道路中心線按道路中心線100米生成緩沖區(qū)基本原理第4頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析從數(shù)學(xué)的角度看，緩沖區(qū)分析的基本思想是給定一個(gè)空間對象或集合，確定其鄰域，鄰域的大小由鄰域半徑R決定，因此對象Oi的緩沖區(qū)定義為：Bi

={x|d(x,Oi)≤R}，即半徑為R的對象Oi的緩沖區(qū)，Bi為距Oi的距離小于等于R的全部點(diǎn)的集合，d一般指最小歐氏距離，但也可以為其他定義的距離，如網(wǎng)絡(luò)距離，即空間物體間的路徑距離。對于對象集合O={Oi

|i=1,2,…,n}，其半徑為R的緩沖區(qū)是各個(gè)對象緩沖區(qū)的并集，即：基本原理第5頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析（a）不同寬度緩沖區(qū)干流支流鄰域半徑R即緩沖距離（寬度），是緩沖區(qū)分析的主要數(shù)量指標(biāo)，可以是常數(shù)或變量?？臻g對象還可以生成多個(gè)緩沖帶?；驹恚╞）環(huán)狀緩沖區(qū)第6頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析具有不同特性的緩沖區(qū)（a）靜態(tài)緩沖區(qū)a=b

（b）動(dòng)態(tài)緩沖區(qū)a

≠b

abaaba根據(jù)研究對象影響力的特點(diǎn)，緩沖區(qū)可以分為均質(zhì)與非均質(zhì)兩種?；驹淼?頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析矢量數(shù)據(jù)緩沖區(qū)的建立方法緩沖區(qū)建立方法（a）單點(diǎn)形成的緩沖區(qū)（b）點(diǎn)群形成的緩沖區(qū)（c）分級點(diǎn)形成的緩沖區(qū)點(diǎn)形成的緩沖區(qū)形式①點(diǎn)要素的緩沖區(qū)第8頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析矢量數(shù)據(jù)緩沖區(qū)的建立方法②線要素的緩沖區(qū)線形成的緩沖區(qū)形式（a）單線形成的緩沖區(qū)（b）多線形成的緩沖區(qū)（c）分級線形成的緩沖區(qū)緩沖區(qū)建立方法第9頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析矢量數(shù)據(jù)緩沖區(qū)的建立方法③面要素的緩沖區(qū)面形成的緩沖區(qū)形式（a）單一面形成的緩沖區(qū)（b）多個(gè)面形成的緩沖區(qū)（c）分級面形成的緩沖區(qū)緩沖區(qū)建立方法第10頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析柵格數(shù)據(jù)緩沖區(qū)的建立方法緩沖區(qū)建立方法柵格數(shù)據(jù)的緩沖區(qū)分析通常稱為推移或擴(kuò)散（Spread），推移或擴(kuò)散實(shí)際上是模擬主體對鄰近對象的作用過程，物體在主體的作用下沿著一定的阻力表面移動(dòng)或擴(kuò)散，距離主體越遠(yuǎn)所受到的作用力越弱。第11頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析緩沖區(qū)建立方法第12頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析動(dòng)態(tài)緩沖區(qū)緩沖區(qū)建立方法現(xiàn)實(shí)世界中很多空間對象或過程對于周圍的影響并不是隨著距離的變化而固定不變的，需要建立動(dòng)態(tài)緩沖區(qū)，根據(jù)空間物體對周圍空間影響度的變化性質(zhì)，可以采用不同的分析模型。①當(dāng)緩沖區(qū)內(nèi)各處隨著距離變化，其影響度變化速度相等時(shí)，采用線性模型；②當(dāng)距離空間物體近的地方比距離空間物體遠(yuǎn)的地方影響度變化快時(shí)，采用二次模型；③當(dāng)距離空間物體近的地方比距離空間物體遠(yuǎn)的地方影響度變化更快時(shí)，采用指數(shù)模型。第13頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析緩沖區(qū)實(shí)現(xiàn)有兩種基本算法：矢量方法和柵格方法。緩沖區(qū)實(shí)現(xiàn)的基本算法矢量方法使用較廣，產(chǎn)生時(shí)間較長，相對比較成熟，具體的幾何算法是中心線擴(kuò)張法，又稱加寬線法或圖形加粗法，通過以中心軸線為核心做平行曲線，生成緩沖區(qū)邊線，再對生成邊線求交、合并，最終生成緩沖區(qū)邊界。柵格方法以數(shù)學(xué)形態(tài)學(xué)擴(kuò)張算法為代表，采用由實(shí)體柵格和八方向位移L得到的n方向柵格像元與原圖作布爾運(yùn)算來完成，由于柵格數(shù)據(jù)量很大，特別是上述算法運(yùn)算量級很大，當(dāng)L較大時(shí)實(shí)施有一定困難，且距離精度也尚待提高。第14頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析角分線法緩沖區(qū)實(shí)現(xiàn)的基本算法RdB角分線法基本思想是：首先在中心軸線兩端點(diǎn)處作軸線的垂線，按緩沖區(qū)半徑R截去超出部分，獲得左右邊線的起訖點(diǎn)；然后在中心軸線的其他各轉(zhuǎn)折點(diǎn)處，用以偏移量為R的左右平行線的交點(diǎn)來確定該轉(zhuǎn)折點(diǎn)處左右平行邊線的對應(yīng)頂點(diǎn)；最終由端點(diǎn)、轉(zhuǎn)折點(diǎn)和左右平行線形成的多邊形就構(gòu)成了所需要的緩沖區(qū)多邊形

第15頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五角分線法簡單易行，但算法存在不足：難以最大限度地保證緩沖區(qū)左右邊線的等寬性；校正過程復(fù)雜；算法模型欠結(jié)構(gòu)化。RdB角分線法第16頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析緩沖區(qū)實(shí)現(xiàn)的基本算法凸角圓弧法凸角圓弧法的算法思想是：在中心軸線兩端點(diǎn)處作軸線的垂線，按緩沖區(qū)半徑R截去超出部分，獲得左右邊線的起訖點(diǎn)；在中心軸線的其他各轉(zhuǎn)折點(diǎn)處，首先判斷該點(diǎn)的凸凹性，在凸側(cè)用圓弧彌合，在凹側(cè)用與該轉(zhuǎn)折點(diǎn)前后相繼的軸線的偏移量為R的左右平行線的交點(diǎn)來確定對應(yīng)頂點(diǎn)凸角圓弧法對于凸部的圓弧處理使其能最大限度地保證左右平行曲線的等寬性，避免了角分線法所帶來的異常情況。凸角圓弧法原理第17頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析凸角圓弧法的算法實(shí)施步驟為緩沖區(qū)實(shí)現(xiàn)的基本算法①直線性判斷為簡化計(jì)算過程，凸角圓弧法的第一步是進(jìn)行相鄰三點(diǎn)的直線性判斷。當(dāng)相鄰三點(diǎn)處于近似共線狀態(tài)時(shí)，用直線代替。常用的直線性判斷方法是點(diǎn)到直線距離法，即直接利用解析幾何中的距離公式

其中，Ax+By+C=0為過首末點(diǎn)的直線方程，x、y為相鄰三點(diǎn)中相對中間點(diǎn)的坐標(biāo)，d為該中間點(diǎn)到直線Ax+By+C=0的距離，當(dāng)d小于某一給定值時(shí)，相鄰三點(diǎn)可視為直線，簡化計(jì)算過程。第18頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析緩沖區(qū)實(shí)現(xiàn)的基本算法凸角圓弧法的算法實(shí)施步驟為

②折點(diǎn)凸凹性的判斷凸角圓弧法的關(guān)鍵在于對凸凹部分的不同處理，因此折線頂點(diǎn)處的凸凹特性的判斷是非常重要的步驟，它能確定何處需要用圓弧連接而何處需要用直線求交。這個(gè)問題可轉(zhuǎn)化為兩個(gè)矢量的叉積：把相鄰兩個(gè)線段看成兩個(gè)矢量，其方向取為坐標(biāo)點(diǎn)序方向。若前一個(gè)矢量以最小的角度掃向第二個(gè)矢量時(shí)呈逆時(shí)針，則為凹頂點(diǎn)，反之，為凸頂點(diǎn)。③凸頂點(diǎn)圓弧的嵌入設(shè)圓弧的始邊與終邊分別為、，其坐標(biāo)形式分別為：，，δ為弦弧逼近誤差（如圖所示）。其中，，，，。A213uv凸頂點(diǎn)圓弧的嵌入第19頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析凸角圓弧法的算法實(shí)施步驟為緩沖區(qū)實(shí)現(xiàn)的基本算法④邊線關(guān)系的判別和處理當(dāng)軸線的彎曲空間不能容許左右平行曲線無壓蓋地通過時(shí)，就產(chǎn)生邊線自相交問題，形成若干個(gè)自相交多邊形，如圖所示。自相交多邊形分為兩種情況：島嶼多邊形與重疊區(qū)多邊形。邊線多邊形的形成第20頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析緩沖區(qū)實(shí)現(xiàn)的基本算法島嶼多邊形&重疊區(qū)多邊形及其自動(dòng)識別：矢量數(shù)據(jù)格式表示的曲線具有方向性，取曲線坐標(biāo)串的方向?yàn)榍€前進(jìn)的方向。當(dāng)中心軸線被取定方向后，其兩側(cè)的平行曲線也就自然地獲得了左右屬性，稱左邊線和右邊線。對于左邊線，島嶼多邊形呈逆時(shí)針方向；對于右邊線，島嶼多邊形呈順時(shí)針方向。對于重疊區(qū)多邊形左邊線呈順時(shí)針方向；右邊線呈逆時(shí)針方向島嶼多邊形與重疊區(qū)多邊形（a）左邊線的島嶼多邊形與重疊區(qū)多邊形（b）右邊線的島嶼多邊形與重疊區(qū)多邊形第21頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析緩沖區(qū)實(shí)現(xiàn)的基本算法凸角圓弧法的算法實(shí)施步驟為⑤緩沖區(qū)邊界的最終形成將重疊區(qū)進(jìn)行合并繪制出最外圍邊線，同時(shí)繪出島嶼輪廓，就形成了最終的緩沖區(qū)邊界。要注意的是，利用緩沖區(qū)進(jìn)行檢索的時(shí)候，按最外圍邊線所形成的圓頭或方頭緩沖區(qū)檢索之后，要扣除按所有島嶼進(jìn)行檢索的結(jié)果。第22頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析對于矢量數(shù)據(jù)對于柵格數(shù)據(jù)①②③緩沖區(qū)多邊形的重疊合并數(shù)學(xué)運(yùn)算法矢量—柵格轉(zhuǎn)換法矢量—柵格混合法對緩沖區(qū)內(nèi)的柵格賦上一個(gè)與其影響度惟一對應(yīng)的值，如果發(fā)生重疊的區(qū)域具有相同的影響度，則取任一值；如果發(fā)生重疊的區(qū)域具有不同影響度等級，則影響度小的服從于影響度大的。緩沖區(qū)實(shí)現(xiàn)的基本算法第23頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.1緩沖區(qū)分析緩沖區(qū)作為一個(gè)獨(dú)立的數(shù)據(jù)層可以參與疊加分析，常應(yīng)用到道路、河流、居民點(diǎn)、工廠（污染源）等生產(chǎn)生活設(shè)施的空間分析，為不同工作需要（如道路修整、河道改建、居民區(qū)拆遷、污染范圍確定等）提供科學(xué)依據(jù)。結(jié)合不同的專業(yè)模型，緩沖區(qū)分析能夠在景觀生態(tài)、規(guī)劃、軍事應(yīng)用等領(lǐng)域發(fā)揮更大的作用。例如，利用緩沖區(qū)分析和相鄰緩沖區(qū)的景觀結(jié)構(gòu)總體變異系數(shù)方法對自然保護(hù)區(qū)進(jìn)行自然景觀和人為影響景觀的分割研究。在虛擬軍事演練系統(tǒng)中，緩沖區(qū)分析方法是對雷達(dá)群的合成探測范圍和干擾效果進(jìn)行研究的一種非常有效的手段。緩沖區(qū)分析應(yīng)用第24頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五為了能根據(jù)離散分布的氣象站降雨量數(shù)據(jù)來計(jì)算某地平均的降雨量，荷蘭氣候?qū)W家A.H.Thiessen提出了一種新的計(jì)算方法，即將所有相鄰氣象站連成三角形，作三角形各邊的垂直平分線，每個(gè)氣象站周圍的若干垂直平分線便圍成一個(gè)多邊形，用這個(gè)多邊形內(nèi)所包含的惟一一個(gè)氣象站的降雨強(qiáng)度來表示這個(gè)多邊形區(qū)域內(nèi)的降雨強(qiáng)度，該多邊形稱為泰森多邊形（ThiessenPolygons或ThiessenTesselations，又稱Voronoi或Dirichlet多邊形）。5.1.2泰森多邊形分析泰森多邊形及其特性

ABCD泰森多邊形第25頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五其幾何定義為：設(shè)平面上的一個(gè)離散點(diǎn)集P={P1,P2,…,Pn

}，其中任意兩個(gè)點(diǎn)都不共位，即Pi

≠Pj（i≠j,i∈[1,2,…,n],j∈[1,2,…,n]），且任意四點(diǎn)不共圓，則任意離散點(diǎn)Pi

的泰森多邊形的定義為在泰森多邊形Ti中，任意一個(gè)內(nèi)點(diǎn)到該泰森多邊形的發(fā)生點(diǎn)Pi的距離都小于該點(diǎn)到其他任何發(fā)生點(diǎn)Pj的距離。這些發(fā)生點(diǎn)Pi（i∈[1,2,…,n]）也稱為泰森多邊形的控制點(diǎn)或質(zhì)心（Centroid）。5.1.2泰森多邊形分析泰森多邊形及其特性

第26頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五泰森多邊形因其生成過程的特殊性，具有以下一些特性：5.1.2泰森多邊形分析泰森多邊形及其特性

1每個(gè)泰森多邊形內(nèi)僅含有一個(gè)控制點(diǎn)數(shù)據(jù)；3位于泰森多邊形邊上的點(diǎn)到其兩邊控制點(diǎn)的距離相等；2泰森多邊形內(nèi)的點(diǎn)到相應(yīng)控制點(diǎn)的距離最近；4在判斷一個(gè)控制點(diǎn)與其他哪些控制點(diǎn)相鄰時(shí)，可直接根據(jù)泰森多邊形得出結(jié)論，即若泰森多邊形是n邊形，則與n個(gè)離散點(diǎn)相鄰。第27頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五Delaunay三角網(wǎng)是由與相鄰泰森多邊形共享一條邊的相關(guān)點(diǎn)連接而成的三角網(wǎng)，它與泰森多邊形是對偶關(guān)系。5.1.2泰森多邊形分析Delaunay三角網(wǎng)的構(gòu)建

泰森多邊形及其對偶Delaunay三角網(wǎng)第28頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.1.2泰森多邊形分析Delaunay三角網(wǎng)具有以下特征：Delaunay三角網(wǎng)是惟一的；三角網(wǎng)的外邊界構(gòu)成了給定點(diǎn)集的凸多邊形“外殼”；沒有任何點(diǎn)在三角形的外接圓內(nèi)部，反之，如果一個(gè)三角網(wǎng)滿足此條件，那么它就是Delaunay三角網(wǎng)（如圖）。如果將三角網(wǎng)中的每個(gè)三角形的最小角進(jìn)行升序排列，則Delaunay三角網(wǎng)的排列得到的數(shù)值最大，從這個(gè)意義上講，Delaunay三角網(wǎng)是“最接近于規(guī)則化”的三角網(wǎng)。

Delaunay三角網(wǎng)的構(gòu)建

Delaunay三角網(wǎng)構(gòu)建1234567821345678構(gòu)建三角網(wǎng)第29頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五凸包插值算法凸包插值算法是Tsai在1993年提出的在n維歐拉空間中構(gòu)造Delaunay三角網(wǎng)的一種通用算法，包括三個(gè)主要步驟：5.1.2泰森多邊形分析Delaunay三角網(wǎng)的構(gòu)建

①凸包的生成123456789圖1

凸包生成②凸包三角剖分圖2

環(huán)切邊界法構(gòu)成若干Delaunay三角形123456789③離散點(diǎn)內(nèi)插圖3離散點(diǎn)內(nèi)插入三角剖分形成新的三角剖分123456789第30頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五泰森多邊形建立過程：建立Delaunay三角網(wǎng)，對離散點(diǎn)和形成的三角形進(jìn)行編號，并記錄每個(gè)三角形是由哪三個(gè)離散點(diǎn)構(gòu)成的；找出與每個(gè)離散點(diǎn)相鄰的所有三角形的編號，并記錄下來；將與每個(gè)離散點(diǎn)相鄰的所有三角形按順時(shí)針或逆時(shí)針方向進(jìn)行排序；計(jì)算出每個(gè)三角形的外接圓圓心，并記錄下來；連接相鄰三角形的外接圓圓心，即可得到泰森多邊形。對于三角網(wǎng)邊緣的泰森多邊形，可作垂直平分線與圖廓相交，與圖廓一起構(gòu)成泰森多邊形。5.1.2泰森多邊形分析泰森多邊形的建立第31頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五泰森多邊形的柵格算法實(shí)現(xiàn)過程一種柵格算法是先將圖形柵格化為數(shù)字圖像，然后對該數(shù)字圖像進(jìn)行歐氏距離變換，得到灰度圖像，而泰森多邊形的邊一定處于該灰度圖像的脊線上；再通過相應(yīng)的圖像運(yùn)算，提取灰度圖像的這些脊線，就得到最終的泰森多邊形。另外還可采用以發(fā)生點(diǎn)為中心點(diǎn)，同時(shí)向周圍相鄰八方向做柵格擴(kuò)張運(yùn)算（一種距離變換），兩個(gè)相鄰發(fā)生點(diǎn)擴(kuò)張運(yùn)算的交線即為泰森多邊形的鄰接邊，三個(gè)相鄰發(fā)生點(diǎn)擴(kuò)張運(yùn)算的交點(diǎn)即為泰森多邊形的頂點(diǎn)。泰森多邊形的建立用柵格方法得到的泰森多邊形5.1.2泰森多邊形分析第32頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.2疊加分析疊加分析概述5.2.1空間要素圖形疊加5.2.2空間要素屬性疊加5.2.3第33頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.2.1疊加分析概述疊加分析是指將同一地區(qū)、同一比例尺、同一數(shù)學(xué)基礎(chǔ)，不同信息表達(dá)的兩組或多組專題要素的圖形或數(shù)據(jù)文件進(jìn)行疊加，根據(jù)各類要素與多邊形邊界的交點(diǎn)或多邊形屬性建立具有多重屬性組合的新圖層，并對那些在結(jié)構(gòu)和屬性上既相互重疊，又相互聯(lián)系的多種現(xiàn)象要素進(jìn)行綜合分析和評價(jià)；或者對反映不同時(shí)期同一地理現(xiàn)象的多邊形圖形進(jìn)行多時(shí)相系列分析，從而深入揭示各種現(xiàn)象要素的內(nèi)在聯(lián)系及其發(fā)展規(guī)律的一種空間分析方法。a2結(jié)果圖層abc1234a1c2c4b3c1c3b3+=輸入圖層疊加圖層疊加分析的基本概念第34頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.2.1疊加分析概述地理空間數(shù)據(jù)的處理與分析目的是獲得空間潛在信息，疊加分析是非常有效的提取隱含信息的工具之一。例如，將全國水文監(jiān)測站分布圖與政區(qū)圖疊加，得到一個(gè)新的圖層，既保留了水文監(jiān)測站的點(diǎn)狀圖形及屬性，同時(shí)附加了行政分區(qū)的屬性信息，據(jù)此可以查詢水文站點(diǎn)屬于哪個(gè)省區(qū)，或者查詢某省區(qū)內(nèi)共有多少個(gè)水文站點(diǎn)；又如將某區(qū)域的土地利用類型圖與土壤pH值狀態(tài)圖、地下水埋深圖、植被覆蓋圖等專題地圖疊加，生成新的圖層后按照濕地的定義形成屬性判別標(biāo)準(zhǔn)，從而判斷該區(qū)域是否為濕地。第35頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五將一個(gè)點(diǎn)層作為輸入圖層疊加到一個(gè)多邊形圖層上，即通過計(jì)算點(diǎn)與多邊形線段的相對位置，來判斷這個(gè)點(diǎn)是否在多邊形內(nèi)，從而確定是否進(jìn)行屬性信息的疊加。5.2.2空間要素圖形疊加點(diǎn)與多邊形的疊加點(diǎn)與多邊形疊加分析第36頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五將一個(gè)線圖層作為輸入圖層疊加到一個(gè)多邊形圖層上，要進(jìn)行線段與多邊形的空間關(guān)系判別，主要是比較線上坐標(biāo)與多邊形的坐標(biāo)，判斷線段是否落在多邊形內(nèi)。5.2.2空間要素圖形疊加線與多邊形的疊加線與多邊形疊加分析第37頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.2.2空間要素圖形疊加多邊形與多邊形的疊合是指將兩個(gè)不同圖層的多邊形要素相疊合，產(chǎn)生輸出層的新多邊形要素，用以解決地理變量的多準(zhǔn)則分析、區(qū)域多重屬性的模擬分析、地理特征的動(dòng)態(tài)變化分析，以及圖幅要素更新、相鄰圖幅拼接、區(qū)域信息提取等。多邊形與多邊形的疊加層1屬性：地貌層2屬性：土壤結(jié)果層屬性：地貌、土壤第38頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.2.2空間要素圖形疊加多邊形與多邊形的疊加根據(jù)疊加結(jié)果要保留不同的空間特征，常用的GIS軟件通常提供了三種類型的多邊形疊加分析操作，即并、疊和、交。輸入圖層疊加圖層結(jié)果圖層+=+=+=多邊形的不同疊加方式并疊和交第39頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五矢量數(shù)據(jù)屬性疊加處理更多地使用邏輯疊加運(yùn)算，即布爾邏輯運(yùn)算中的包含、交、并、差等。5.2.3空間要素屬性疊加矢量數(shù)據(jù)疊加分析12345A123456

A線與多邊形的疊加屬性邏輯運(yùn)算LineID123456OldID123451PolyAAA000LineID123OldID123PolyAAALineID456OldID451Poly000（a）邏輯并（b）邏輯交（c）邏輯差第40頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五柵格數(shù)據(jù)中對于同一區(qū)域、同一比例尺、同一數(shù)學(xué)基礎(chǔ)的不同信息表達(dá)的要素來說，其柵格編號不會發(fā)生變化，即對于任意柵格單元用作標(biāo)識的行列號I0、J0是不變的，進(jìn)行疊加的時(shí)候只是增加了屬性表的長度，下表表示進(jìn)行多重疊加后的柵格多邊形的數(shù)據(jù)結(jié)構(gòu)：柵格數(shù)據(jù)疊加分析柵格編號屬性1屬性2…屬性nI0J0R1R2…Rn5.2.3空間要素屬性疊加第41頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五柵格數(shù)據(jù)來源復(fù)雜，疊加分析操作的前提是要將其轉(zhuǎn)換為統(tǒng)一的柵格數(shù)據(jù)格式，如BMP、GRID等，且各個(gè)疊加層必須具有統(tǒng)一的地理空間，即具有統(tǒng)一的空間參考（包括地圖投影、橢球體、基準(zhǔn)面等），統(tǒng)一的比例尺以及具有統(tǒng)一的分辨率（即像元大?。鸥駭?shù)據(jù)的疊加分析操作主要通過柵格之間的各種運(yùn)算來實(shí)現(xiàn)?？梢詫螌訑?shù)據(jù)進(jìn)行各種數(shù)學(xué)運(yùn)算如加、減、乘、除、指數(shù)、對數(shù)等，也可通過數(shù)學(xué)關(guān)系式建立多個(gè)數(shù)據(jù)層之間的關(guān)系模型。5.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析第42頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五基于不同的運(yùn)算方式和疊加形式：5.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析基于像元與像元之間一一對應(yīng)的運(yùn)算，每一個(gè)像元都是基于它自身的運(yùn)算，不考慮其他的與之相鄰的像元；局部變換將具有相同屬性值的像元作為整體進(jìn)行分析運(yùn)算；分帶變換基于研究區(qū)內(nèi)所有像元的運(yùn)算，輸出柵格的每一個(gè)像元值是基于全區(qū)的柵格運(yùn)算，這里像元是具有或沒有屬性值的網(wǎng)格（柵格）。全局變換以某一像元為中心，將周圍像元的值作為算子，進(jìn)行簡單求和、求平均值、最大值、最小值等；鄰域變換柵格疊加變換類型：第43頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五局部變換每一個(gè)像元經(jīng)過局部變換后的輸出值與這個(gè)像元本身有關(guān)系，而不考慮圍繞該像元的其他像元值?！?＝×＝

輸入柵格輸出柵格輸入柵格乘數(shù)柵格輸出柵格（a）單層局部變換（b）多層局部變換局部變換2011230232311260336906969336201123023231121122122222332334202226046692385.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析第44頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五鄰域變換如果要計(jì)算某一像元的值，就將該像元看作一個(gè)中心點(diǎn)，一定范圍內(nèi)圍繞它的格網(wǎng)可以看作它的輻射范圍，這個(gè)中心點(diǎn)的值取決于采用何種計(jì)算方法將周圍格網(wǎng)的值賦給中心點(diǎn)，其中的輻射范圍可自定義。鄰域變換2011230230231102＝鄰域求和787410131291012139578 7輸入柵格輸出柵格5.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析第45頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五分帶變換將同一區(qū)域內(nèi)具有相同像元值的格網(wǎng)看作一個(gè)整體進(jìn)行分析運(yùn)算，稱為分帶變換。＝

分帶變換201 1230 202 110 2輸入柵格分帶柵格輸出柵格123 4567 8123 4555 5875 5867 878 557 85.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析第46頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五全局變換全局變換是基于區(qū)域內(nèi)全部柵格的運(yùn)算，一般指在同一網(wǎng)格內(nèi)進(jìn)行像元與像元之間距離的量測。歐幾里德距離＝歐幾里德距離運(yùn)算1 1 12 2.01.0 0.00.01.41.0 1.00.01.00.0 1.01.01.41.0 1.42.0輸入柵格輸出柵格5.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析第47頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五在距離量測中像元間距離考慮全部的源數(shù)據(jù)，且要求像元間距離最短，但沒有考慮其他因素如運(yùn)費(fèi)等。成本距離量測運(yùn)算比空間距離量測運(yùn)算要復(fù)雜得多，需要另一個(gè)格網(wǎng)來定義經(jīng)過每個(gè)像元的成本或阻抗。交通費(fèi)用計(jì)算5.03.0 0.00.03.52.5 2.80.01.50.0 2.52.02.13.0 2.84.0輸入柵格成本柵格輸出柵格

1 1 1a2 bc224 4443 3214 1253 35.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析第48頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五柵格邏輯疊加?xùn)鸥駭?shù)據(jù)中的像元值有時(shí)無法用數(shù)值型字符來表示，不同專題要素用統(tǒng)一的量化系統(tǒng)表示也比較困難，故使用邏輯疊加更容易實(shí)現(xiàn)各個(gè)柵格層之間的運(yùn)算。圖層之間的布爾邏輯運(yùn)算包括：與（AND）、或（OR）、非（NOT）、異或（×OR）等。ABAANDBAORBANOTBA×ORB000000100111010101111100布爾邏輯運(yùn)算示例5.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析不同為1,相同為0第49頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五假設(shè)某市政府要在轄區(qū)范圍內(nèi)選擇理想地點(diǎn)建立一個(gè)垃圾場，有關(guān)垃圾場的選址條件如下所述：區(qū)域地表物質(zhì)應(yīng)具有低滲透率，以阻止可溶性物質(zhì)快速滲入地下水中；區(qū)域與現(xiàn)有市政區(qū)域范圍保持一定距離；區(qū)域不屬于環(huán)境敏感區(qū)；區(qū)域應(yīng)屬于農(nóng)業(yè)區(qū)，而非市政區(qū)或工業(yè)區(qū)；區(qū)域的地表平均坡度平穩(wěn)，并小于某個(gè)極限值；區(qū)域不發(fā)生洪水。5.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析第50頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五二值邏輯疊加模型：根據(jù)垃圾場選址條件組織有關(guān)圖件資料，包括表土滲透性圖、城區(qū)范圍圖、生態(tài)敏感度分布圖、城鄉(xiāng)區(qū)劃圖、地表坡度圖和洪泛區(qū)分布圖等。建立垃圾場選址的模型。該模型將以上圖層結(jié)合起來進(jìn)行布爾邏輯運(yùn)算，結(jié)果生成二值圖，其中值為1的地點(diǎn)表示滿足上述垃圾場選址的全部條件，值為0則表示不滿足選址條件。5.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析第51頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五具體模型如下：將各個(gè)圖層二值化（TRUE，F(xiàn)ALSE）或（0，1）。本例中各層數(shù)據(jù)的布爾邏輯條件如下：Ca=地表滲透性級別為低級；Cb=距離城區(qū)邊界的距離>1km；Cc=生態(tài)敏感性為不敏感級別；Cd=土地利用類型為農(nóng)業(yè)用地；Ce=地表坡度<2°；Cf=不屬于洪泛區(qū)范圍。對于各輸入數(shù)據(jù)層的布爾邏輯條件變量進(jìn)行邏輯與運(yùn)算，在區(qū)域某位置點(diǎn)上如果所有數(shù)據(jù)層的條件變量都是所要求的值，則結(jié)果變量OUTPUT為“1”，其他情況下為“0”。OUTPUT＝CaANDCbANDCcANDCdANDCeANDCf生成二值圖。滿足條件的位置就是二值圖中值為“1”的地點(diǎn)。5.2.3空間要素屬性疊加?xùn)鸥駭?shù)據(jù)疊加分析第52頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3網(wǎng)絡(luò)分析5.3.5流分析5.3.6動(dòng)態(tài)分段技術(shù)5.3.4資源分配5.3.7地址匹配5.3.1網(wǎng)絡(luò)分析概述5.3.3連通分析5.3.2最佳路徑分析第53頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述網(wǎng)絡(luò)分析是通過研究資源等的優(yōu)化問題進(jìn)行研究網(wǎng)絡(luò)的狀態(tài)以及模擬和分析資源在網(wǎng)絡(luò)上的流動(dòng)和分配情況，對網(wǎng)絡(luò)結(jié)構(gòu)及其的一種空間分析方法。網(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í)際問題抽象化、模型化、可操作化，根據(jù)網(wǎng)絡(luò)元素的拓?fù)潢P(guān)系（線性實(shí)體之間、線性實(shí)體與結(jié)點(diǎn)之間、結(jié)點(diǎn)與結(jié)點(diǎn)之間的連結(jié)、連通關(guān)系），通過考察網(wǎng)絡(luò)元素的空間、屬性數(shù)據(jù)，對網(wǎng)絡(luò)的性能特征進(jìn)行多方面的分析計(jì)算，從而為制定系統(tǒng)的優(yōu)化途徑和方案提供科學(xué)決策的依據(jù)，最終達(dá)到使系統(tǒng)運(yùn)行最優(yōu)的目標(biāo)。第54頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述在城市之間建立通訊網(wǎng)絡(luò)，使其中任意兩個(gè)城市之間都有直接或間接的通訊聯(lián)系，假設(shè)已知每兩個(gè)城市之間通訊線路的成本，要求找出一個(gè)成本最低的通訊網(wǎng)絡(luò)。圖論中的基本概念31城市1城市2679城市3城市4城市576548（a）通訊網(wǎng)絡(luò)問題中的數(shù)據(jù)（b）一個(gè)最小成本通訊網(wǎng)絡(luò)用圖形描述通訊網(wǎng)絡(luò)問題31城市1城市26城市3城市4城市54第55頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述圖論中的“圖”是指由點(diǎn)集合V和V中點(diǎn)與點(diǎn)之間的連線的集合E構(gòu)成的二元組（V,E）。V中的元素稱為結(jié)點(diǎn)，E中的元素稱為邊。圖論中所研究的圖是由實(shí)際問題抽象出來的邏輯關(guān)系圖，圖中點(diǎn)和線的位置與曲直無關(guān)緊要，點(diǎn)的多少和每條線是連接哪些點(diǎn)才是關(guān)鍵。圖論中的基本概念圖的結(jié)構(gòu)ABCDe3e4e5e1e2e6e7第56頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述圖論中的基本概念有向圖V1V2V3V4e1e2e3e4e5e6樹V1V2V3V4V5V6V7V8V10V9兩個(gè)端點(diǎn)重合的邊稱為環(huán)。如果有兩條邊的端點(diǎn)是同一對頂點(diǎn)，則稱這兩條邊為重邊。既沒有環(huán)也沒有重邊的圖，稱為簡單圖。如果圖中的邊是有向的，則稱為有向圖，其中的邊叫做弧。在無向圖中，首尾相接的一串邊的集合叫做路。在有向圖中，順向的首尾相接的一串邊的集合叫做有向路。如果一個(gè)圖中，任意兩個(gè)結(jié)點(diǎn)之間都存在一個(gè)路，則稱之為連通圖。起點(diǎn)和終點(diǎn)為同一個(gè)結(jié)點(diǎn)的路稱為回路（或圈）。如果一個(gè)連通圖中不存在任何回路，則稱為樹。任意一個(gè)連通圖，去掉一些邊后形成的樹叫做連通圖的生成樹。第57頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述給定一個(gè)圖，圖中的每一條邊賦以一個(gè)實(shí)數(shù)，稱這種數(shù)為邊的權(quán)數(shù)，稱這種圖為賦權(quán)圖。賦以權(quán)數(shù)的有向圖稱為賦權(quán)有向圖，也可稱之為網(wǎng)絡(luò)。根據(jù)需要賦權(quán)有向圖中的一條邊，必要時(shí)可以賦以多個(gè)權(quán)值，另外也可以給結(jié)點(diǎn)賦權(quán)，稱為點(diǎn)權(quán)網(wǎng)絡(luò)，相對于點(diǎn)權(quán)網(wǎng)絡(luò)，給邊賦權(quán)的網(wǎng)絡(luò)稱為邊權(quán)網(wǎng)絡(luò)。在機(jī)器實(shí)現(xiàn)中，鄰接矩陣表示法、關(guān)聯(lián)矩陣表示法、鄰接表表示法是用來描述圖與網(wǎng)絡(luò)常用的方法。圖論中的基本概念V2V0V1100V3V5V46020301010505帶權(quán)的有向圖第58頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述鄰接矩陣用來表示圖中任意兩點(diǎn)間的鄰接關(guān)系及其權(quán)值。如果兩點(diǎn)間有一條弧，則鄰接矩陣中對應(yīng)的元素為1；否則為0（也可用∞表示兩點(diǎn)間無任何連接關(guān)系），鄰接矩陣為對稱矩陣。對于加權(quán)圖的鄰接矩陣表示，一條弧所對應(yīng)的元素不再是1，而是相應(yīng)的權(quán)值。圖論中的基本概念24（a）有向圖153（b）鄰接矩陣0110000010010000010100110有向圖及其鄰接矩陣第59頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述關(guān)聯(lián)矩陣中，每行對應(yīng)圖的一個(gè)節(jié)點(diǎn)，每列對應(yīng)圖的一條弧。如果一個(gè)節(jié)點(diǎn)是一條弧的起點(diǎn)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為1；如果一個(gè)節(jié)點(diǎn)是一條弧的終點(diǎn)，則關(guān)聯(lián)矩陣中對應(yīng)的元素為–1；如果一個(gè)節(jié)點(diǎn)與一條弧不關(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)矩陣第60頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述圖的鄰接表是圖中所有節(jié)點(diǎn)鄰接表的集合。對每個(gè)節(jié)點(diǎn)，它的鄰接表就是它的所有出弧圖論中的基本概念24（a）有向圖153有向圖及其鄰接表04212345860426303093035074（b）鄰接表第61頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述網(wǎng)絡(luò)數(shù)據(jù)模型是現(xiàn)實(shí)世界網(wǎng)絡(luò)系統(tǒng)（如交通網(wǎng)、通訊網(wǎng)、自來水管網(wǎng)、煤氣管網(wǎng)等）的抽象表示。按照幾何形態(tài)，空間實(shí)體被抽象為點(diǎn)、線、面目標(biāo)，構(gòu)成網(wǎng)絡(luò)的最基本元素是線性實(shí)體以及這些實(shí)體的連接交匯點(diǎn)。前者稱為網(wǎng)線或鏈（Link），后者稱為結(jié)點(diǎn)（Node）。鏈（Link）鏈?zhǔn)菢?gòu)成網(wǎng)絡(luò)的骨架，是現(xiàn)實(shí)世界中各種線路的抽象和資源傳輸或通信聯(lián)絡(luò)的通道，可以代表公路、鐵路、街道、航線、水管、煤氣管、輸電線、河流等。鏈包括圖形信息和屬性信息，鏈的屬性信息包括阻礙強(qiáng)度和資源需求量，鏈的阻礙強(qiáng)度是指在通過一條鏈時(shí)所需要花費(fèi)的時(shí)間或者費(fèi)用等，如資源流動(dòng)的時(shí)間、速度。鏈?zhǔn)怯蟹较虻模?dāng)資源沿著網(wǎng)絡(luò)中的不同方向流動(dòng)時(shí)所受到的阻礙強(qiáng)度可能相同，也可能不同。網(wǎng)絡(luò)數(shù)據(jù)模型第62頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述結(jié)點(diǎn)（Node）結(jié)點(diǎn)是網(wǎng)線的端點(diǎn)，又是網(wǎng)線的匯合點(diǎn)，可以表示交叉路口、中轉(zhuǎn)站、河流匯合點(diǎn)等，其狀態(tài)屬性除了包括阻礙強(qiáng)度和資源需求量等，還有下面幾種特殊的類型。①障礙（Barrier）：禁止資源在網(wǎng)絡(luò)中的鏈上流動(dòng)的點(diǎn)。②拐點(diǎn)（Turn）：出現(xiàn)在網(wǎng)絡(luò)鏈中的分割結(jié)點(diǎn)上，狀態(tài)屬性有阻礙強(qiáng)度，如拐彎的時(shí)間和限制（例如在8：00到18：00不允許左拐等）。在地理網(wǎng)絡(luò)中，拐點(diǎn)對資源的流動(dòng)有很大影響，資源沿著某一條鏈流動(dòng)到有關(guān)結(jié)點(diǎn)后，既可以原路返回，也可以流向與該結(jié)點(diǎn)相連的任意一條鏈，如果阻礙強(qiáng)度值為負(fù)數(shù)，則表示資源禁止流向特定的弧段。網(wǎng)絡(luò)數(shù)據(jù)模型第63頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述結(jié)點(diǎn)（Node）③中心（Center）：網(wǎng)絡(luò)中具有一定的容量，能夠接受或分配資源的結(jié)點(diǎn)所在的位置。如水庫﹑商業(yè)中心、電站、學(xué)校等，其狀態(tài)屬性包括資源容量（如總量）﹑阻礙強(qiáng)度（如中心到鏈的最大距離或時(shí)間限制）。資源容量決定了為中心服務(wù)的弧段的數(shù)量，中心的阻礙強(qiáng)度是指沿某一路徑到達(dá)中心所經(jīng)歷的弧段總阻礙強(qiáng)度的最大值。④站點(diǎn)（Stop）：在路徑選擇中資源增減的結(jié)點(diǎn)，如庫房﹑車站等，其狀態(tài)屬性有兩種，一種是站的阻礙強(qiáng)度，它代表與站有關(guān)的費(fèi)用、時(shí)間等，如在某個(gè)庫房裝卸貨物所用時(shí)間等；一種是站的資源需求量，如產(chǎn)品數(shù)量、學(xué)生數(shù)、乘客數(shù)等。站的需求量為正值時(shí)，表示在該站上增加資源；若為負(fù)值，則表示在該站上減少資源。網(wǎng)絡(luò)數(shù)據(jù)模型第64頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述網(wǎng)絡(luò)分析功能路徑分析路徑分析是GIS中最基本的功能，其核心是對最佳路徑的求解。從網(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)或邊，這一類問題稱為連通分量求解；另一類連通分析問題是求解最少費(fèi)用連通方案，即在耗費(fèi)最小的情況下使全部結(jié)點(diǎn)相互連通。網(wǎng)絡(luò)分析功能第65頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述網(wǎng)絡(luò)分析功能資源分配資源分配也稱定位與分配問題，包括目標(biāo)選址和將需求按最近（這里遠(yuǎn)近是按加權(quán)距離來確定的）原則尋找供應(yīng)中心（資源發(fā)散或匯集地）兩個(gè)問題。流分析

流是資源在結(jié)點(diǎn)間的傳輸。流分析問題主要是按照某種優(yōu)化標(biāo)準(zhǔn)（時(shí)間最少、費(fèi)用最低、路程最短或運(yùn)送量最大等）設(shè)計(jì)的運(yùn)送方案，網(wǎng)絡(luò)流理論是其基礎(chǔ)理論。網(wǎng)絡(luò)分析功能第66頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.1網(wǎng)絡(luò)分析概述網(wǎng)絡(luò)分析功能動(dòng)態(tài)分段動(dòng)態(tài)分段技術(shù)是GIS網(wǎng)絡(luò)分析中一種基于網(wǎng)絡(luò)線的動(dòng)態(tài)分析、顯示和繪圖技術(shù)。通過建立一種比“弧段－結(jié)點(diǎn)”數(shù)據(jù)模型高級的“動(dòng)態(tài)段－動(dòng)態(tài)結(jié)點(diǎn)”模型，來實(shí)現(xiàn)根據(jù)不同的屬性按照某種度量標(biāo)準(zhǔn)對線性要素進(jìn)行相對位置的劃分。地址匹配地址匹配實(shí)質(zhì)是對地理位置的查詢，涉及到地址的編碼。地址匹配與其他網(wǎng)絡(luò)分析功能結(jié)合起來，可以滿足實(shí)際工作中復(fù)雜的分析要求。網(wǎng)絡(luò)分析功能第67頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.2最佳路徑分析最佳路徑分析也稱最優(yōu)路徑分析，以最短路徑分析為主。這里“最佳”包含很多含義，不僅指一般地理意義上的距離最短，還可以是成本最少、耗費(fèi)時(shí)間最短、資源流量（容量）最大、線路利用率最高等標(biāo)準(zhǔn)。很多網(wǎng)絡(luò)相關(guān)問題，如最可靠路徑問題、最大容量路徑問題、易達(dá)性評價(jià)問題和各種路徑分配問題均可納入最佳路徑問題的范疇之中。無論判斷標(biāo)準(zhǔn)和實(shí)際問題中的約束條件如何變化，其核心實(shí)現(xiàn)方法都是最短路徑算法。最短路徑問題從算法研究的角度考慮最短路徑問題通常可歸納為兩大類：一類是所有點(diǎn)對之間的最短路徑，另一類是單源點(diǎn)間的最短路徑問題。第68頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.2最佳路徑分析Dijkstra算法基本思想其基本思路是：假設(shè)每個(gè)點(diǎn)都有一對標(biāo)號（dj,pj），其中dj是從起源點(diǎn)s到點(diǎn)j的最短路徑的長度（從頂點(diǎn)到其本身的最短路徑是零路（沒有弧的路），其長度等于零）；pj則是從s到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn)。①初始化。起源點(diǎn)設(shè)置為ds

=0，ps為空，并標(biāo)記起源點(diǎn)s，記k=s，其他所有點(diǎn)設(shè)為未標(biāo)記點(diǎn)。②檢驗(yàn)從所有已標(biāo)記的點(diǎn)k到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置dj=min［dj,dk+lkj］，其中，lkj為從點(diǎn)k到j(luò)的直接連接距離。③選取下一個(gè)點(diǎn)。從所有未標(biāo)記的結(jié)點(diǎn)中，選取dj中最小的一個(gè)i，di=min［dj,所有未標(biāo)記的點(diǎn)j］，點(diǎn)i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的點(diǎn)。④找到點(diǎn)i的前一點(diǎn)。從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn)i的點(diǎn)j*，作為前一點(diǎn)，記為i=j*⑤標(biāo)記點(diǎn)i。如果所有點(diǎn)已標(biāo)記，則算法完全推出，否則記k=i，重復(fù)步驟②③④。最短路徑算法第69頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.2最佳路徑分析左圖為某一帶權(quán)有向圖，若對其施行Dijkstra算法，則所得從V0到其余各頂點(diǎn)的最短路徑以及運(yùn)算過程中距離的變化情況如右表所示。V2V0V1100V3V5V46020301010505帶權(quán)的有向圖終點(diǎn)從源點(diǎn)V0到各終點(diǎn)的距離值和最短路徑的求解過程i=1i=2i=3i=4i=5V1∞∞∞∞∞V210（V0,V2）V3∞60（V0,V2,V3）50（V0,V4,V3）V430（V0,V4）30（V0,V

4）V5100（V0,V5）100（V0,V5）90（V0,V4,V5）60（V0,V4,V3,V5）VjV2V4V3V5S﹛V0,V2﹜﹛V0,V2,V4﹜﹛V0,V2,V3,V4﹜﹛V0,V2,V3,V4,V5﹜最短路徑算法第70頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.2最佳路徑分析弗洛伊德算法其基本思想是：假設(shè)求從頂點(diǎn)Vi到Vj的最短路徑。若從Vi到Vj有弧，則從Vi到Vj存在一條長度為dij的路徑，該路徑不一定是最短路徑，需要進(jìn)行n次試探。首先判別?。╒i,V1）和弧（V1,Vj）是否存在。如果存在，則比較（Vi,Vj）和（Vi,V1,Vj）的路徑長度，較短者為從Vi到Vj的中間頂點(diǎn)的序號不大于1的最短路徑。假如在路徑上再增加一個(gè)頂點(diǎn)V2，若路徑（Vi,…,V2）和路徑（V2,…,Vj）分別是當(dāng)前找到的中間頂點(diǎn)的序號不大于1的最短路徑，那么后來的路徑（Vi,…,V2,…,Vj）就有可能是從Vi到Vj的中間頂點(diǎn)的序號不大于2的最短路徑。將它和已經(jīng)得到的從Vi到Vj的中間頂點(diǎn)的序號不大于1的最短路徑相比較，從中選出中間頂點(diǎn)的序號不大于2的最短路徑之后，再增加一個(gè)頂點(diǎn)V3，繼續(xù)進(jìn)行試探。依次類推，在經(jīng)過n次比較之后，最后求得的必是從Vi到Vj的最短路徑。最短路徑算法第71頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.2最佳路徑分析矩陣算法該算法是利用矩陣來求出圖的最短距離矩陣。算法步驟可表示為：最短路徑算法③D=AA[2]A[3]…A[n-2]=(di,j)n×n。②求出A,A[2],A[3],…,A[n-2]

；①已知圖的鄰接矩陣A；第72頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.2最佳路徑分析最佳路徑分析在汽車導(dǎo)航系統(tǒng)和各種應(yīng)急系統(tǒng)（如110報(bào)警、119火警以及醫(yī)療救護(hù)系統(tǒng)等）中應(yīng)用非常廣泛，系統(tǒng)應(yīng)用需求決定了最佳路徑分析應(yīng)是高效率的，比如一般要求計(jì)算出到出事地點(diǎn)的最佳路徑的時(shí)間必須是在1～3s內(nèi)，且在行車過程中需要實(shí)時(shí)計(jì)算出車輛前方的行駛路線。但前面介紹的三種算法在時(shí)間復(fù)雜度上都不盡如人意，很難滿足不斷發(fā)展的各種系統(tǒng)的要求，從而促使人們考慮從各個(gè)角度解決其實(shí)現(xiàn)的效率問題。針對不同的網(wǎng)絡(luò)特征、應(yīng)用需求及具體的軟硬件環(huán)境，各種最短路徑算法不斷涌現(xiàn)，在空間復(fù)雜度、時(shí)間復(fù)雜度、易實(shí)現(xiàn)性及應(yīng)用范圍等方面各具特色。最短路徑算法的優(yōu)化第73頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.2最佳路徑分析以路徑分析應(yīng)用最廣泛的交通道路網(wǎng)絡(luò)為例，提供一個(gè)解決實(shí)際問題的基本模式。假定某地區(qū)交通管理部門接到舉報(bào)在該區(qū)域內(nèi)某一地點(diǎn)發(fā)生交通事故，需要有關(guān)人員立刻趕到現(xiàn)場，選擇一條路途最短的行進(jìn)路線到達(dá)指定地點(diǎn)。在解決問題之前要了解交通網(wǎng)絡(luò)數(shù)據(jù)的基本特征。首先，對于一定區(qū)域范圍內(nèi)龐大的交通網(wǎng)絡(luò)要考慮它的存儲結(jié)構(gòu)，既要有利于網(wǎng)絡(luò)分析算法的實(shí)現(xiàn)，又能夠在節(jié)約存儲空間的前提下根據(jù)需要擴(kuò)充數(shù)據(jù)，對交通網(wǎng)絡(luò)進(jìn)行綜合分析。然后是網(wǎng)絡(luò)搜索，主要依據(jù)求解單源點(diǎn)間最短路徑的的需要，首先將網(wǎng)絡(luò)邊的權(quán)值設(shè)為兩結(jié)點(diǎn)間的戴克斯徒拉算法思想，同樣也可以對其進(jìn)行優(yōu)化改進(jìn)以提高效率。根據(jù)實(shí)際應(yīng)用距離，并定義沿著起點(diǎn)到終點(diǎn)的方向?yàn)榭臻g有效方向，相反的方向?yàn)闊o效方向；然后賦給網(wǎng)絡(luò)邊、結(jié)點(diǎn)相應(yīng)的字段值，并定義站點(diǎn)、拐點(diǎn)、橋梁等特殊地物的屬性，最后通過具體的程序設(shè)計(jì)來實(shí)現(xiàn)搜索過程。路徑分析的實(shí)現(xiàn)第74頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.3連通分析在地理網(wǎng)絡(luò)中從某一點(diǎn)出發(fā)能夠到達(dá)的全部結(jié)點(diǎn)或邊有哪些，如何選擇對于用戶來說成本最小的線路，即連通分析所要解決的問題。連通分析的求解過程實(shí)質(zhì)上是對應(yīng)的圖的生成樹的求解過程，其中研究最多的是最小生成樹問題?；靖拍頥1V2V4V3無向圖（連通圖）第75頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.3連通分析連通性是圖論的一個(gè)重要概念。在無向圖G=(V,E)中，如果從頂點(diǎn)Vs到頂點(diǎn)Vt有路徑，則稱Vs和Vt是連通的。如果對于圖G中的任意兩個(gè)頂點(diǎn)Vi,Vj∈V，Vi和Vj都是連通的，則稱G為連通圖。無向圖及其連通分量（a）無向圖GV9V2V1V8V3V5V6V7V4V9V8V2V1V3V5V6V7V4（b）G的三個(gè)連通分量基本概念第76頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.3連通分析一個(gè)連通圖的生成樹是含有該連通圖的全部頂點(diǎn)的一個(gè)極小連通子圖，包含三個(gè)條件：①它是連通的；②它包含原有連通圖的全部結(jié)點(diǎn)；③它不含任何回路。依據(jù)連通圖的生成樹的定義可知，若連通圖G的頂點(diǎn)個(gè)數(shù)為n，則G的生成樹的邊數(shù)為n-1；樹無回路，但不相鄰頂點(diǎn)連成一邊，就會得到一個(gè)回路；樹是連通的，但去掉任意一條邊，就會變?yōu)椴贿B通的?；靖拍畹?7頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.3連通分析從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次，這一過程叫做圖的遍歷。遍歷圖的基本方法有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索?；舅枷胧牵簭膱D中的某個(gè)頂點(diǎn)出發(fā)，然后訪問任意一個(gè)該點(diǎn)的鄰接點(diǎn)，并以該點(diǎn)的鄰接點(diǎn)為新的出發(fā)點(diǎn)繼續(xù)訪問下一層級的鄰接點(diǎn)，從而使整個(gè)搜索過程向縱深方向發(fā)展，直到圖中的所有頂點(diǎn)都被訪問過為止。從圖中的某個(gè)頂點(diǎn)出發(fā)，訪問該頂點(diǎn)之后依次訪問它的所有鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)按深度優(yōu)先搜索遍歷圖的其他頂點(diǎn)，直至所有頂點(diǎn)都被訪問到為止。基本概念第78頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.3連通分析圖（a）是一個(gè)具有8個(gè)結(jié)點(diǎn)的網(wǎng)絡(luò)圖，對其分別進(jìn)行深度優(yōu)先搜索和廣度優(yōu)先搜索，其搜索過程如圖（b）和（c）。（a）網(wǎng)絡(luò)圖V1V2V3V4V5V8V6V7基本概念V1V2V3V4V5V8V6V71234567（b）廣度優(yōu)先搜索過程V1V2V3V4V5V8V6V71524673（c）深度優(yōu)先搜索過程第79頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.3連通分析克羅斯克爾（Kruskal）算法是1956年提出的，俗稱“避圈法”。設(shè)圖G是由m個(gè)結(jié)點(diǎn)構(gòu)成的連通賦權(quán)圖，則構(gòu)造最小生成樹的步驟如下：最小生成樹算法1先把圖G中的各邊按權(quán)數(shù)從小到大重新排列，并取權(quán)數(shù)最小的一條邊為生成樹T中的邊；2在剩下的邊中，按順序取下一條邊，若該邊與生成樹中已有的邊構(gòu)成回路，則舍去該邊，否則選擇進(jìn)入生成樹中；3重復(fù)步驟2，直到有m-1條邊被選進(jìn)T中，這m-1條邊就是圖G的最小生成樹。第80頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五(2)最小生成數(shù)之一

(3)最小生成樹之二第81頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.3連通分析構(gòu)造最小生成樹的另一個(gè)著名算法Prim算法的基本思想是：假設(shè)N=(V,E)是連通網(wǎng)，生成的最小生成樹為T=(V,TE)，求T的步驟如下：最小生成樹算法1初始化：U={u0}，TE={φ}；2在所有u∈U，v∈V-U的邊（u,v）∈E中，找一條權(quán)最小的邊（u0,v0），TE+{（u0,v0）}→TE，{v0}+U→U；3如果U=V，則算法結(jié)束，否則重復(fù)步驟2；4最后得到最小生成樹T=<V,TE>，其中TE為最小生成樹的邊集。第82頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.3連通分析圖1中帶權(quán)圖最小生成樹求算過程如圖2所示。1243566536264551圖1帶權(quán)圖124356212435624124356241124356245112435632451圖2求帶權(quán)圖最小生成樹的過程（a）（b）（c）（d）（e）最小生成樹算法第83頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配在多數(shù)的應(yīng)用中，需要解決在網(wǎng)絡(luò)中選定幾個(gè)供應(yīng)中心，并將網(wǎng)絡(luò)的各邊和點(diǎn)分配給某一中心，使各中心所覆蓋范圍內(nèi)每一點(diǎn)到中心的總的加權(quán)距離最小，實(shí)際上包括定位與分配兩個(gè)問題。定位是指已知需求源的分布，確定在哪里布設(shè)供應(yīng)點(diǎn)最合適的問題；分配指的是已知供應(yīng)點(diǎn)，確定其為哪些需求源提供服務(wù)的問題。第84頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配選址功能涉及在某一指定區(qū)域內(nèi)選擇服務(wù)性設(shè)施的位置，如確定市郊商店區(qū)﹑消防站﹑工廠﹑飛機(jī)場﹑倉庫等的最佳位置。選址問題的數(shù)學(xué)模型取決于可供選擇的范圍，以及所選位置的質(zhì)量判斷標(biāo)準(zhǔn)這兩個(gè)條件。在一個(gè)地理網(wǎng)絡(luò)中，能夠從網(wǎng)絡(luò)的結(jié)點(diǎn)和邊上找到一些特定的點(diǎn)使它們滿足某種優(yōu)化條件，這些點(diǎn)可用于較簡單的定位問題。

選址問題（定位問題）

第85頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配給定一個(gè)地理網(wǎng)絡(luò)D=（V,E），其中V表示地理網(wǎng)絡(luò)結(jié)點(diǎn)的集合，E表示地理網(wǎng)絡(luò)邊的集合。令d(p,q)表示從頂點(diǎn)p到頂點(diǎn)q之間的距離；令R表示矩陣，矩陣的第p、q個(gè)元素是d(p,q)，矩陣R的元素稱為頂點(diǎn)—頂點(diǎn)距離（Vertex-vertexDistance，VVD）；表示從網(wǎng)絡(luò)邊（vi,vj）上的f_點(diǎn)到結(jié)點(diǎn)q之間的距離，這個(gè)長度稱為點(diǎn)—頂點(diǎn)距離（Point-vertexDistance，PVD）；表示從頂點(diǎn)到網(wǎng)絡(luò)邊（vi,vj）的最大距離，此長度稱為頂點(diǎn)—弧距離（Vertex-arcDistance）。選址問題（定位問題）

第86頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配從頂點(diǎn)p到任一頂點(diǎn)的最大距離從頂點(diǎn)p到所有頂點(diǎn)的總距離從頂點(diǎn)p到所有弧的最大距離從頂點(diǎn)p到所有弧的總距離從網(wǎng)絡(luò)邊（vi,vj）上的f_點(diǎn)到任一結(jié)點(diǎn)的最大距離從網(wǎng)絡(luò)邊（vi,vj）上的f_點(diǎn)到所有各結(jié)點(diǎn)的總距離選址問題（定位問題）

第87頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配基于以上變量的定義，給出有關(guān)中心點(diǎn)和中位點(diǎn)的概念。使最大距離達(dá)到最小的位置稱為網(wǎng)絡(luò)的中心點(diǎn)，使最大距離總和達(dá)到最小的位置稱為網(wǎng)絡(luò)的中位點(diǎn)。一個(gè)地理網(wǎng)絡(luò)的中心點(diǎn)主要有中心、一般中心、絕對中心和一般絕對中心等；一個(gè)地理網(wǎng)絡(luò)的中位點(diǎn)主要有中位點(diǎn)、一般中位點(diǎn)、絕對中位點(diǎn)和一般絕對中位點(diǎn)等。選址問題（定位問題）

第88頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配地理網(wǎng)絡(luò)的中心點(diǎn)是網(wǎng)絡(luò)中距最遠(yuǎn)結(jié)點(diǎn)最近的一個(gè)結(jié)點(diǎn)vx，即地理網(wǎng)絡(luò)的一般中心是距最遠(yuǎn)點(diǎn)最近的一個(gè)結(jié)點(diǎn)vx，即地理網(wǎng)絡(luò)的絕對中心是距最遠(yuǎn)結(jié)點(diǎn)最近的任意一點(diǎn)vx，即地理網(wǎng)絡(luò)的一般絕對中心是距最遠(yuǎn)點(diǎn)最近的任意一點(diǎn)vx，即選址問題（定位問題）

第89頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配地理網(wǎng)絡(luò)的中位點(diǎn)是從該點(diǎn)到其他各結(jié)點(diǎn)有最小總距離的一個(gè)結(jié)點(diǎn)vx，即地理網(wǎng)絡(luò)的一般中位點(diǎn)是從該點(diǎn)到其他各結(jié)點(diǎn)有最小總距離的一個(gè)結(jié)點(diǎn)vx，即地理網(wǎng)絡(luò)的絕對中位點(diǎn)是從該點(diǎn)到所有各結(jié)點(diǎn)有最小總距離的任意一點(diǎn)，即地理網(wǎng)絡(luò)的一般絕對中位點(diǎn)是從該點(diǎn)到所有各條網(wǎng)絡(luò)邊有最小的總距離的任意一點(diǎn)，即選址問題（定位問題）

第90頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配實(shí)例分析現(xiàn)有一指定郵區(qū)，需在該郵區(qū)范圍內(nèi)的5個(gè)城市中選擇一個(gè)城市作為中心局所在地。將城市用圖的頂點(diǎn)表示，各頂點(diǎn)之間的連線表示各城市間郵件的進(jìn)、出和轉(zhuǎn)口的關(guān)系，連線的權(quán)值則設(shè)為兩城市間運(yùn)送郵件所耗費(fèi)的成本，郵件的運(yùn)送成本包含諸如路程長短、郵運(yùn)工具、業(yè)務(wù)量的大小、郵件的流向及經(jīng)轉(zhuǎn)次數(shù)等因素。郵區(qū)城市示意圖51342312572341選址問題（定位問題）

第91頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配首先先求出R矩陣?？衫肍loyd算法或Dantzig算法求出R矩陣。郵區(qū)城市示意圖51342312572341R矩陣選址問題（定位問題）

第92頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配如果選擇以中心點(diǎn)法為標(biāo)準(zhǔn)，得到的頂點(diǎn)指的是該頂點(diǎn)所代表的城市與其他城市間的郵件往來的最大成本為最小?？梢韵惹蟪鰪某鞘?到其他各個(gè)城市的運(yùn)送郵件的最大成本，然后依次求出城市2、3、4、5到其他各個(gè)城市運(yùn)送郵件的最大成本，計(jì)算過程如下：

選址問題（定位問題）

從頂點(diǎn)4到其他頂點(diǎn)的最大距離為3，即從城市4向其他城市運(yùn)送郵件的最大成本為最小，可知郵區(qū)中心局地址設(shè)置在該城市，可保證從郵區(qū)中心局到該郵區(qū)的其他收投點(diǎn)的郵件的最大運(yùn)送成本為最小。第93頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配如果選擇以中位點(diǎn)法為標(biāo)準(zhǔn)，則求出的中位點(diǎn)的實(shí)際意義表示從該點(diǎn)向其他城市運(yùn)送郵件的總成本為最小。根據(jù)中位點(diǎn)的數(shù)學(xué)表達(dá)式要先求出SVV（i）：選址問題（定位問題）

由此得即頂點(diǎn)4是該郵區(qū)的中位點(diǎn)，從城市4向其他各城市運(yùn)送郵件的總成本為最小。第94頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配分配問題在現(xiàn)實(shí)生活中體現(xiàn)為設(shè)施的服務(wù)范圍及其資源的分配范圍的確定等一類問題，資源的分配能為城市中的每一條街道上的學(xué)生確定最近的學(xué)校，為水庫提供其供水區(qū)等。資源分配是模擬資源如何在中心（學(xué)校、消防站、水庫等）和周圍的網(wǎng)線（街道、水路等）、結(jié)點(diǎn)（交叉路口、汽車中轉(zhuǎn)站等）間流動(dòng)的。分配問題第95頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配實(shí)際生活中，許多行業(yè)和部門都涉及到利用服務(wù)設(shè)施提供相關(guān)服務(wù)的問題，常見的服務(wù)范圍有：①到服務(wù)設(shè)施或中心的最短距離不超過一定范圍的覆蓋區(qū)域，如一個(gè)供水站50公里以內(nèi)的區(qū)域，構(gòu)成該供水站的供水區(qū)；②到服務(wù)設(shè)施或中心的最短時(shí)間不超過一定限制的覆蓋區(qū)域，如一個(gè)消防站10分鐘所能到達(dá)的范圍是該消防站在10分鐘的服務(wù)范圍。中心服務(wù)范圍分析作為基本網(wǎng)絡(luò)分析功能，是指一個(gè)服務(wù)中心在給定的時(shí)間或范圍內(nèi)能夠到達(dá)的區(qū)域，它為評價(jià)服務(wù)中心的位置及其通達(dá)性提供了有利工具。分配問題第96頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配確定中心服務(wù)范圍的基本思想是依次求出服務(wù)費(fèi)用不超過中心阻值的路徑，組成這些路徑的網(wǎng)絡(luò)結(jié)點(diǎn)和邊的集合構(gòu)成了該中心的服務(wù)范圍。主要步驟為：根據(jù)拓?fù)潢P(guān)系，計(jì)算地理網(wǎng)絡(luò)的最大鄰接結(jié)點(diǎn)數(shù)。1構(gòu)造鄰接結(jié)點(diǎn)矩陣和初始判斷矩陣描述地理網(wǎng)絡(luò)結(jié)構(gòu)。2應(yīng)用廣度優(yōu)先搜索算法確定地理網(wǎng)絡(luò)中心的服務(wù)范圍。3分配問題第97頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配具體求解中心資源的分配范圍時(shí)與服務(wù)范圍的搜索方法類似，設(shè)D=（V,E,c）為一給定的帶中心的地理網(wǎng)絡(luò)，P為滿足資源分配范圍條件的網(wǎng)絡(luò)邊和網(wǎng)絡(luò)結(jié)點(diǎn)的集合。算法的主要步驟如下：①將中心所在的結(jié)點(diǎn)作為V0，放入已標(biāo)記結(jié)點(diǎn)集S中，并初始化有關(guān)變量；②如果整個(gè)網(wǎng)絡(luò)都已被分配，則停止；否則，執(zhí)行步驟④；③如果總貨源量都已被分配，則停止；否則，執(zhí)行步驟④；④在尚未分配的結(jié)點(diǎn)集中，尋找距離中心V0路徑最短的結(jié)點(diǎn)Vn，假設(shè)Vn的前一點(diǎn)是Vm，將（Vm,Vn）作為當(dāng)前處理的邊；分配問題⑤⑥⑦⑧+⑨⑩第98頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配⑤判斷網(wǎng)絡(luò)流在邊（Vm,Vn）上的運(yùn)行情況：

⑥如果（Vm,Vn）邊流向Vn點(diǎn)的流量為0，則該邊停止運(yùn)輸；如果（Vm,Vn）邊流向Vn點(diǎn)的流量小于該邊的需求量，則將該邊的一部分分配給中心后，停止運(yùn)輸；如果（Vm,Vn）邊流向Vn點(diǎn)的流量大于該邊的需求量，則考察網(wǎng)絡(luò)流在Vn點(diǎn)上的接受量PRn、消耗量PFn和發(fā)出量POn；⑦判斷網(wǎng)絡(luò)流在結(jié)點(diǎn)上的運(yùn)行情況，與網(wǎng)絡(luò)流在邊上的運(yùn)行情況類似；⑧如果POn≤0，則該點(diǎn)停止運(yùn)輸；如果POn

＞0，則考察與結(jié)點(diǎn)Vn相鄰的邊；分配問題⑨⑩第99頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配⑨如果存在與Vn點(diǎn)相鄰的邊（Vn,Vr），該邊尚未分配而該邊的點(diǎn)Vn已經(jīng)分配，則給該邊分配它所需要的量LDnr，此時(shí)，從Vn點(diǎn)流向其他相鄰的、且另一端點(diǎn)尚未分配的邊的流量為POn

=POn－LDnr；⑩記錄已分配的結(jié)點(diǎn)Vm、邊（Vm,Vn）或邊（Vn,Vr），并從未分配的點(diǎn)、邊集合和中減去這些元素，將點(diǎn)Vn作為當(dāng)前結(jié)點(diǎn)。最后，計(jì)算全網(wǎng)絡(luò)點(diǎn)或邊的總消耗量LET、PET，點(diǎn)或邊的分配數(shù)LNT、PNT以及總的消耗量TF。分配問題END第100頁，共138頁，2022年，5月20日，17點(diǎn)56分，星期五5.3.4資源分配許多資源分配問題的供應(yīng)點(diǎn)布設(shè)要求滿足多種組合條件，比如在選擇供應(yīng)點(diǎn)時(shí)不僅要求使總的加權(quán)距離最小，有時(shí)還要使總服務(wù)范圍最大，有時(shí)又限定服務(wù)范圍最大距離不能超過一定的限值等，這些問題都可以分解為多個(gè)單目標(biāo)問題，利用單目標(biāo)方程即最小目標(biāo)值法來求解。所謂目標(biāo)方程是用數(shù)學(xué)方式表達(dá)