空間分析算法平面掃描算法

平面掃描算法的主要內(nèi)容是對(duì)空間對(duì)象進(jìn)行一遍掃描，并在掃描過程中完成對(duì)空間對(duì)象的性質(zhì)或空間對(duì)象之間的關(guān)系的分析。在掃描過程中，掃描線自左向右移動(dòng)，依一定順序遍歷所有與掃描線相交的空間元素，判斷它們之間的順序和其他空間拓?fù)潢P(guān)系，依照一定規(guī)則進(jìn)行分析。圖1中給出了平面掃描算法的示意，其中粗線段表示和掃描線相交的線段。

任何平面掃描算法的基本要素都包括：事件點(diǎn)列表，掃描線狀態(tài)，事件點(diǎn)觸發(fā)的動(dòng)作。 其中，事件點(diǎn)列表 指依照系統(tǒng)確定的空間排序關(guān)系，事先確定或在掃描過程中計(jì)算出的算法感興趣的空間元素的有序序列；掃描線狀態(tài)指依照確定的排序規(guī)則記錄當(dāng)前與掃描線相交的空間元素的有序表 ；事件點(diǎn)觸發(fā)的動(dòng)作指掃描到事件點(diǎn)時(shí)做出的分析或操作。

事先確定的事件點(diǎn)列表在掃描過程中不再變化，稱為靜態(tài)事件點(diǎn)列表；需要在掃描過程中計(jì)算的事件點(diǎn)列表稱為動(dòng)態(tài)事件點(diǎn)列表。和掃描線相交的線段以及落在掃描線上的點(diǎn)是掃描線狀態(tài)的組成元素。事件點(diǎn)可以是任何分析算法感興趣的空間元素，包括對(duì)象之間交點(diǎn)和特定線段元素等。

可以將掃描線狀態(tài)看成一種抽象數(shù)據(jù)類型，記為 Sweep_Status，它擁有自己的數(shù)據(jù)組織方式、排序規(guī)則和操作方法。掃描線狀態(tài)中的排序規(guī)則是按照各個(gè)空間元素和掃描線交點(diǎn)的 Y 坐標(biāo)的大小來排序，在這種排序關(guān)系的組織下可以對(duì)一個(gè)與掃描線相交的空間元素取前驅(qū)或則后繼。圖1中標(biāo)號(hào) 1 到 4 給出了與掃描線相交的線段的排序順序。

平面掃描算法是一個(gè)算法框架，給定上述三個(gè)要素的具體實(shí)現(xiàn)，就可以給定一個(gè)具有一定的功能的空間分析算法。下面 S 是 Sweep_Status 類型的變量，s 是空間線段，對(duì)掃描線狀態(tài)定義一系列操作。

關(guān)于掃描線狀態(tài)的操作：

(1) new_sweep()，生成一個(gè)新的掃描線狀態(tài)的數(shù)據(jù)結(jié)構(gòu)，返回 Sweep_Status類型的變量；

(2) add_left(S,s)，當(dāng)掃描過程中遇到左半線段類型的事件點(diǎn)的時(shí)候，向 S 中插入一個(gè)左半線段對(duì)應(yīng)的線段元素 s，操作返回一個(gè)插入線段后的掃描線狀態(tài)；

(3) del_right(S,s)，當(dāng)掃描過程中遇到右半線段類型的事件點(diǎn)的時(shí)候，在掃描線中刪除右半線段對(duì)應(yīng)的線段元素， S、s 及返回值的定義同 add_left(S,s)；

(4) pred_of(S,elem)，在掃描線狀態(tài)中定位空間元素 elem 的前驅(qū)，即確定存在于S中且按照掃描線的排序規(guī)則比elem小的元素的集合中最大的元素的位置，操作結(jié)果設(shè)置 S 的數(shù)據(jù)項(xiàng) current 指向 elem 的前驅(qū)，current = 0 表示前驅(qū)不存在，返回 current 被設(shè)置后的掃描線狀態(tài)；

(5) current_exists(S)，當(dāng) S 的數(shù)據(jù)項(xiàng) current = 0，返回 FALSE，否則返回 TRUE；

(6) set_attr(S，attr)設(shè)置 S 中 current 所指的空間元素的屬性，attr 是屬性集合；

(7) get_attr(S)取 S 中 current 所指的空間元素的屬性，返回屬性集合；

InsideAbove 是區(qū)域類型對(duì)象 R 中的線段的一個(gè)屬性，它表示這個(gè)線段的上方或者左側(cè)是區(qū)域的內(nèi)部?？梢杂闷矫鎾呙杷惴ㄅ袛嗖⒃O(shè)置 R 中的線段 s 是否具有屬性 InsideAbove：如果它在掃描線狀態(tài)中的序號(hào)為奇數(shù)，則 s 具有屬性InsideAbove；否則不具備這種屬性。這種判斷和設(shè)置在建立空間對(duì)象的時(shí)候完成，圖1中給出了示例。

地理信息系統(tǒng)(Geographic Information System，簡稱GIS)是采集、處理、存儲(chǔ)、查詢、分析和顯示與地球表面空間相關(guān)的數(shù)據(jù)的計(jì)算機(jī)系統(tǒng)。對(duì)于具體應(yīng)用來說，它是利用計(jì)算機(jī)科學(xué)管理和綜合分析現(xiàn)實(shí)世界與空間位置相關(guān)的地理數(shù)據(jù)，為規(guī)劃、管理、研究等提供輔助決策的信息系統(tǒng)。

空間分析是建立在對(duì)空間數(shù)據(jù)的有效管理之上的，是地理信息系統(tǒng)區(qū)別于一般信息系統(tǒng)的主要功能特征，也成為評(píng)價(jià)一個(gè)空間信息系統(tǒng)功能的主要指標(biāo)之一。空間分析是基于空間對(duì)象的位置和形態(tài)特征的空間數(shù)據(jù)分析技術(shù)，其目的在于提取和傳輸空間信息。利用空間分析技術(shù)，通過對(duì)原始數(shù)據(jù)模型的觀察和實(shí)驗(yàn)，用戶可以獲得新的經(jīng)驗(yàn)和知識(shí)，并以此作為空間行為的決策依據(jù)?？臻g分析在水污染監(jiān)測、城市規(guī)劃與管理、地震災(zāi)害和損失估計(jì)、洪水災(zāi)害分析、礦產(chǎn)資源評(píng)價(jià)、道路交通管理、地形地貌分析和軍事領(lǐng)域等領(lǐng)域都有廣泛應(yīng)用。

平面點(diǎn)集 S 的凸包是包含 S 中所有點(diǎn)的最小凸多邊形，其頂點(diǎn)為 S 中的點(diǎn)。

設(shè)多邊形 Q 的頂點(diǎn)是給定平面內(nèi)的點(diǎn)

設(shè)二維點(diǎn)集 S = {

許多空間分析問題都可以歸結(jié)為凸包問題，求取凸包的算法有增量法、格雷厄姆掃描法、卷包裹法和分治法等。

(1) 增量法：首先取幾個(gè)點(diǎn)，形成初始凸包，然后不斷尋找當(dāng)前凸包外的新頂點(diǎn)來更新凸包，直到所有的點(diǎn)都在凸包內(nèi)。其計(jì)算復(fù)雜度為 O(

(2) 格雷厄姆掃描法：首先找到最小 Y 坐標(biāo)點(diǎn)，接著按照其它點(diǎn)和該極值點(diǎn)的連線與 x 軸的夾角的角度值排序，通過判斷連續(xù) 3 個(gè)點(diǎn)的空間關(guān)系，從而得到逆時(shí)針排列的凸包頂點(diǎn)。其計(jì)算復(fù)雜度為 O(nlogn)。

(3) 卷包裹法：以某極值點(diǎn)作為開始點(diǎn)，根據(jù)其他點(diǎn)都位于相鄰頂點(diǎn)連線同側(cè)的原則，找到所有的頂點(diǎn)。其計(jì)算復(fù)雜度為 O(nh)，這里 n 和 h 分別為點(diǎn)數(shù)和凸包邊界數(shù)。

(4) 分治法：先按坐標(biāo)將點(diǎn)集分成 2 個(gè)子集 L 和 R，使得 L 中所有的點(diǎn)在 R的左邊，遞歸地找到 L 和 R 的凸包，通過子凸包的公切線對(duì)其合并。其計(jì)算復(fù)雜度為 O(nlogn)。

所有這些算法的計(jì)算復(fù)雜度都大于或等于 O(nlogn)，凸包算法時(shí)間復(fù)雜度的下限為 O(nlogn)，雖然有些算法在特殊情況下可以達(dá)到線性時(shí)間的復(fù)雜度，不過在最壞的情況下，計(jì)算復(fù)雜度仍不低于 O(nlogn)。

由圖論的知識(shí)可知，地圖上的點(diǎn)構(gòu)成一帶權(quán)無向圖(有向圖可視為特例的一種)，要找出任意兩地間的最短路徑,對(duì)地圖中的所有點(diǎn)，首先要建立一個(gè)鄰接矩陣，它表示圖中任意兩地間的鄰接關(guān)系及其權(quán)值(若兩地間無任何連接關(guān)系則設(shè)為無窮大)，易知該矩陣為對(duì)稱矩陣。從該矩陣出發(fā)，可以利用圖論中的迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法等求出最短路徑。

Dijkstra算法

Dijkstra算法的基本思路是：首先，引進(jìn)一個(gè)輔助向量Dist，它的每個(gè)分量Dist [i]表示當(dāng)前找到的從始點(diǎn)V到每個(gè)終點(diǎn)Vi 的最短路徑的長度。它的初始值為:若從V到Vi有弧，則Dist [i]為弧上的權(quán)值;否則置Dist[i]為無窮大。顯然，長度為Dist[i]=Min{Dist[i]|Vi

Dijkstra算法描述為：

(1) 假設(shè)用帶權(quán)的鄰接矩陣Cost來表示帶權(quán)有向圖，Cost[i,j]表示弧(Vi , V j)上權(quán)值。若(Vi,Vj)不存在，則置Cost[i,j]為無窮大。S為已找到從V出發(fā)的最短路徑的終點(diǎn)的集合，它的初始狀態(tài)為空集。

(2) 選擇Vj，使得Dist [i] =Min {Dist [i] |Vi 不

(4) 重復(fù)操作(2) , (3)共N-1次。由此求得從V到圖上其余各頂點(diǎn)的最短路徑是依路徑長度遞增的序列。

弗洛伊德算法

弗洛伊德算法能夠求得每一對(duì)頂點(diǎn)之間的最短路徑，其基本思想是：假設(shè)從頂點(diǎn)Vi到Vj的最短路徑。若從Vi到Vj有弧，則從Vi到Vj存在一條長度為COST [ i, j]的路徑，該路徑不一定是最短路徑，尚需進(jìn)行n次試探。首先考慮路徑(Vi, V1, Vj)是否存在(即判別弧(Vi, V1)和弧(V1, Vj)是否存在)。如果存在，則比較(Vi, Vj)和(Vi, V1, Vj)的路徑長度，較短者為從Vi到Vj的中點(diǎn)頂點(diǎn)的序號(hào)不大于1的最短路徑。假如在路徑上再增加一個(gè)頂點(diǎn)V2，也就是說，若(Vi，…，V2)和(V2，...，Vj)分別是當(dāng)前找到的中間頂點(diǎn)的序號(hào)不大于1的最短路徑，那么(Vi，...，V2，...，Vj)就有可能是從Vi到Vj的中間頂點(diǎn)的序號(hào)不大于2的最短路徑。將它和已經(jīng)得到的從Vi 到Vj的中間頂點(diǎn)的序號(hào)不大于1的最短路徑相比較，從中選出中間頂點(diǎn)的序號(hào)不大于2的最短路徑之后，再增加一個(gè)頂點(diǎn)V3，繼續(xù)進(jìn)行試探。依次類推，在經(jīng)過n次比較之后，最后求得的必是從Vi 到Vj的最短路徑。按此方法，可同時(shí)求得各對(duì)頂點(diǎn)間的最短路徑。算法共需3層循環(huán)，總的時(shí)間復(fù)雜度是O(

《計(jì)算機(jī)算法設(shè)計(jì)與分析（第5版）》修正了第4版中發(fā)現(xiàn)的一些錯(cuò)誤，并將各章的習(xí)題分為算法分析題和算法實(shí)現(xiàn)題兩部分，增加了算法實(shí)踐性內(nèi)容，增加了有關(guān)串和序列的算法內(nèi)容。

該教材各章的論述中，首先介紹一種算法設(shè)計(jì)策略的基本思想，然后從解決計(jì)算機(jī)科學(xué)和應(yīng)用中的實(shí)際問題入手，描述幾個(gè)算法。同時(shí)對(duì)每個(gè)算法所需的時(shí)間和空間進(jìn)行分析，使讀者既能學(xué)到一些常用的算法，也能通過對(duì)算法設(shè)計(jì)策略的反復(fù)應(yīng)用，牢固掌握這些算法設(shè)計(jì)的基本策略。該教材選擇某些問題，通過對(duì)解同一問題的不同算法的比較，使讀者體會(huì)到每種算法的設(shè)計(jì)要點(diǎn)。

該教材采用面向?qū)ο蟮腃 語言作為算法描述手段，在保持C 優(yōu)點(diǎn)的同時(shí)，盡量使算法描述簡明、清晰。每章的章首為學(xué)習(xí)要點(diǎn)提示，章末配有難易適度的習(xí)題，分為算法分析題和算法實(shí)現(xiàn)題兩部分，以強(qiáng)化實(shí)踐環(huán)節(jié) 。

空間分析是地理信息系統(tǒng)的主要功能特征?！犊臻g分析（第2版）》以全新的思路，將各種空間分析的方法與模型區(qū)分為基本分析方法和專門應(yīng)用模型兩個(gè)層次，以空間信息的構(gòu)成為主體框架，組織和闡述了空間分析的基本內(nèi)容。全書共分為七章，著重?cái)⑹隽丝臻g分布、空間位置、空間形態(tài)、空間距離，以及空間方位、拓?fù)?、相似和相關(guān)等分析的基本理論和算法實(shí)現(xiàn)。

《空間分析（第2版）》可作為有關(guān)專業(yè)研究生的教學(xué)用書，亦可用作有關(guān)專業(yè)本科生的選修課教材或教學(xué)參考書，同時(shí)也適合于地理、測繪、土地、城建、規(guī)劃等領(lǐng)域從事地理信息處理與分析的研究人員和工程技術(shù)人員閱讀參考。學(xué)習(xí)或閱讀《空間分析（第2版）》最好先具備地理信息系統(tǒng)方面的基礎(chǔ)知識(shí)。

• 配套教材

《計(jì)算機(jī)算法設(shè)計(jì)與分析（第5版）》有配套教材——《計(jì)算機(jī)算法設(shè)計(jì)與分析習(xí)題解答（第5版）》 。