倪文輝，李維慶，甘元芳

（國家測繪地理信息局 第三地理信息制圖院，四川 成都 610100）

0 引 言

2013年至2015年開展的第一次全國地理國情普查開啟了我國測繪地理信息工作的一個(gè)新領(lǐng)域，地理國情信息為科學(xué)制定經(jīng)濟(jì)社會(huì)發(fā)展重大戰(zhàn)略、長遠(yuǎn)規(guī)劃和宏觀政策提供了一種新的基礎(chǔ)信息。地理國情普查數(shù)據(jù)采集工作完成后，以及隨著常態(tài)化地理國情監(jiān)測的開展，在未來很長一段時(shí)間內(nèi)，地理國情普查成果及地理國情監(jiān)測成果的轉(zhuǎn)化應(yīng)用將是測繪地理信息部門的一項(xiàng)重要工作。各類型地理國情專題圖產(chǎn)品制作便是地理國情普查成果圖形化展示的有效途徑。

地理國情專題制圖最大的工作量集中在制圖綜合階段。地理國情數(shù)據(jù)制圖綜合既包含地表覆蓋圖斑制圖綜合，也包括水系、道路、構(gòu)筑物等實(shí)體要素的制圖綜合。其中水系實(shí)體要素是地理國情普查成果的重點(diǎn)線狀國情要素，其特點(diǎn)是數(shù)量大、圖形結(jié)構(gòu)形態(tài)多樣，節(jié)點(diǎn)多、流向復(fù)雜[1]。水系實(shí)體要素實(shí)現(xiàn)自動(dòng)綜合是地理國情普查圖制作過程中首先要解決和亟需解決的問題。水系實(shí)體要素的綜合處理主要是通過對(duì)水系實(shí)體要素的矢量方向進(jìn)行遍歷，并根據(jù)制圖比例尺需求，按照舍棄次要水系，保留主要水系，舍棄無名稱水系，保留有名稱水系，舍棄密集區(qū)短小水系，保留稀疏區(qū)源頭水系等原則進(jìn)行綜合處理。然而，軟件工具自動(dòng)綜合處理時(shí)，一旦遇到水系實(shí)體要素形成閉合環(huán)路，就會(huì)在局部形成遍歷“死循環(huán)”，導(dǎo)致程序無法繼續(xù)處理。針對(duì)這個(gè)問題，本文將有向圖基本理論與方法應(yīng)用到循環(huán)水系檢測中，對(duì)傳統(tǒng)深度優(yōu)先遍歷(DFS)算法改進(jìn)形成循環(huán)水系檢測的技術(shù)流程和方法，并結(jié)合生產(chǎn)實(shí)踐針對(duì)性地研發(fā)出實(shí)用性軟件工具，解決了地理國情普查圖制作水系實(shí)體自動(dòng)綜合的技術(shù)問題，極大地提高了制圖生產(chǎn)效率。

1 研究區(qū)及數(shù)據(jù)源

考慮到不同地域水系形態(tài)特征，本文選取四川地區(qū)的縣市和江蘇地區(qū)縣市開展試驗(yàn)。四川地區(qū)位于中國西南腹地，地處長江上游，全省河網(wǎng)密布、水資源豐富，水系主要呈樹狀分布，大小支流眾多。江蘇地區(qū)跨江瀕海，地勢(shì)平坦，水網(wǎng)發(fā)達(dá)，河渠縱橫且呈格網(wǎng)狀分布。選取上述兩個(gè)研究區(qū)進(jìn)行試驗(yàn)具有一定的代表性和廣泛性。

本文研究所用數(shù)據(jù)的來源為第一次全國地理國情普查的地表覆蓋和國情要素?cái)?shù)據(jù)成果。該成果現(xiàn)勢(shì)性2015年，包括不分區(qū)（分為地理單元數(shù)據(jù)、構(gòu)筑物要素?cái)?shù)據(jù)、交通數(shù)據(jù)、水域數(shù)據(jù)及元數(shù)據(jù)）和分區(qū)（分為地表覆蓋數(shù)據(jù)、交通數(shù)據(jù)、水域數(shù)據(jù)）兩類。

2 水系有向圖構(gòu)建

隨著計(jì)算機(jī)圖形學(xué)及相關(guān)技術(shù)的發(fā)展和在地圖制圖中的深入應(yīng)用，推動(dòng)了地圖綜合的發(fā)展及地圖概括的自動(dòng)化進(jìn)程。線狀要素的自動(dòng)綜合成為制圖綜合領(lǐng)域研究的熱點(diǎn)與重點(diǎn)，用于制圖綜合的模型和算法也日益增多，研究取得了一些階段性成果。在地物要素簡化方面，制圖綜合研究人員陸續(xù)提出基于自然規(guī)律的線劃要素的化簡方法，基于Snake技術(shù)的線光滑與位移方法，基于約束點(diǎn)的曲線一致性化簡方法，并建立了道格拉斯-普克法、James法、光欄法等一系列經(jīng)典的要素簡化算法，并基于這些算法衍生出適應(yīng)于不同環(huán)境下的算法[2]。本文基于有向圖理論研究建立了DFS改進(jìn)算法，并應(yīng)用于制圖生產(chǎn)。

2.1 水系有向圖構(gòu)建方法

有向圖D是一個(gè)有序的三元數(shù)組(V(D)，E(D)，ψ(D))，其中V(D)為非空的頂點(diǎn)集，E(D)為邊集合，ψ(D)稱為關(guān)聯(lián)函數(shù)，它使D的每條邊對(duì)應(yīng)D的有序頂點(diǎn)對(duì)[3]。如果e是D的一條邊，而u與v是使得ψ(u,v)=e的頂點(diǎn)，那么稱e是由u連接到v，標(biāo)為e=(u,v)，同時(shí)稱u為e的起點(diǎn)，v為e的終點(diǎn)。

設(shè)D=(V，E)是有向圖，其中，V={v1,v2,…,vn},E={e1,e2,…,em}，A(D)=(aij)mxn是D的鄰接矩陣，aij是以vi為始點(diǎn)vj為終點(diǎn)的邊的條數(shù)，1≤i≤n,1≤j≤n。水系實(shí)體具有明顯的方向特性，水系中的每個(gè)要素(Feature)都是從起點(diǎn)到終點(diǎn)的連接線，可以從from point和to point獲取其起點(diǎn)和終點(diǎn)的坐標(biāo)[4]，如圖1所示。

圖1 水系實(shí)體要素的矢量方向Fig.1 Vector directions of water entity

水系有向圖構(gòu)建的方法：

1）讀取水系實(shí)體要素?cái)?shù)據(jù)(HYDL)，并遍歷水系實(shí)體的每個(gè)要素(Feature)。

2）獲取構(gòu)建有向圖的頂點(diǎn)數(shù)據(jù)集V。首先獲取第1個(gè)要素的from point（起點(diǎn)）和to point（終點(diǎn)）坐標(biāo)，編號(hào)為0和1，并存儲(chǔ)到頂點(diǎn)數(shù)據(jù)集V中；再遍歷第2個(gè)要素的from point（起點(diǎn)）和to point（終點(diǎn)），分別判斷該頂點(diǎn)是否已經(jīng)存儲(chǔ)在V中，如果V中存在，則V中不加入該頂點(diǎn)，否則作為新的頂點(diǎn)加入到V中；同樣的方法遍歷完水系實(shí)體的所有要素，獲得水系有向圖的頂點(diǎn)集V和頂點(diǎn)數(shù)量N(D)。

3）獲取水系有向圖的有向邊E。對(duì)每個(gè)遍歷的水系實(shí)體要素，將要素的起點(diǎn)和終點(diǎn)記錄在有向邊E中，如{[起點(diǎn)編號(hào)，終點(diǎn)編號(hào)]}，得到水系有向圖的邊集E和邊的數(shù)量N(E)。

4）通過得到的V和E點(diǎn)集，計(jì)算水系有向圖鄰接矩陣A(D)。

2.2 拓?fù)渑判?/h3>

對(duì)于有向圖G，若它的一個(gè)節(jié)點(diǎn)序列LS：v1,v2,…,vn滿足這樣的條件：＜vi,vj＞是G的邊時(shí)，在LS中vi位于vj之前，否則(不是邊時(shí)）在LS中vi與vj的前后次序任意，則稱LS為圖G的一個(gè)拓?fù)湫蛄?，求拓?fù)湫蛄械牟僮鞣Q為拓?fù)渑判?Topological Sorting)。一個(gè)有向無環(huán)圖必須滿足兩個(gè)條件：

1）每個(gè)頂點(diǎn)出現(xiàn)且只出現(xiàn)一次；

2）若存在一條從頂點(diǎn)A到頂點(diǎn)B的路徑，那么序列中頂點(diǎn)A出現(xiàn)在頂點(diǎn)B的前面。

通過拓?fù)渑判蚩梢钥焖贆z測出構(gòu)建的有向圖中是否存在環(huán)路，具體步驟如下：

①從有向圖中選擇一個(gè)沒有前驅(qū)（即入度為0）的頂點(diǎn)并輸出。

②從有向圖中刪除該頂點(diǎn)和所有以它為起點(diǎn)的有向邊。

③重復(fù)步驟①和步驟②直到當(dāng)前的有向圖為空或當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)為止。否則說明有向圖中必然存在環(huán)。

2.3 DFS算法理論

深度優(yōu)先搜索算法（Depth-First-Search，簡稱DFS）是一種用于遍歷或搜索樹或圖的算法，是沿著樹的深度遍歷樹的節(jié)點(diǎn)，盡可能深地搜索樹的分支[5]。當(dāng)節(jié)點(diǎn)v的所有邊都已經(jīng)被遍歷過，搜索將回到發(fā)現(xiàn)節(jié)點(diǎn)v的那條邊的起始點(diǎn)，這一過程一直進(jìn)行到已發(fā)現(xiàn)從源節(jié)點(diǎn)可達(dá)的所有節(jié)點(diǎn)為止。如果還存在未被發(fā)現(xiàn)的節(jié)點(diǎn)，則選擇其中一個(gè)作為源點(diǎn)并重復(fù)以上過程，整個(gè)過程反復(fù)進(jìn)行直到所有節(jié)點(diǎn)都被訪問為止。

本文在研究水系有向圖理論的基礎(chǔ)上，改進(jìn)深度優(yōu)先算法(DFS)得到一種新型算法，形成了水系中環(huán)路檢測的技術(shù)流程，改進(jìn)DFS算法實(shí)現(xiàn)思路如圖2所示。

圖2 改進(jìn)DFS算法檢測水系環(huán)路流程圖Fig.2 Improved DFS algorithm to detect hydrologic loop fl ow chart

1）選取水系有向圖頂點(diǎn)集中的第一個(gè)頂點(diǎn)V作為起始頂點(diǎn)，標(biāo)記其訪問狀態(tài)Visited為true，并將該頂點(diǎn)存入棧Stack中；

2）對(duì)V頂點(diǎn)的連接頂點(diǎn)采用DFS算法進(jìn)行遍歷，當(dāng)連接頂點(diǎn)出度為0時(shí)出棧，出棧時(shí)判斷該頂點(diǎn)是不是在棧中，如果是，則存在環(huán)[6]；

3）出棧時(shí)，判斷該頂點(diǎn)是否存在另一個(gè)連接頂點(diǎn)，同時(shí)標(biāo)記該頂點(diǎn)的訪問狀態(tài)Visited為false，這時(shí)候在繼續(xù)遍歷訪問時(shí)，不會(huì)因?yàn)樵L問過某頂點(diǎn)而不會(huì)再進(jìn)行遍歷，避免了漏環(huán)的存在；

4）找到環(huán)后，通過建立水系有向圖中頂點(diǎn)與線要素的關(guān)聯(lián)規(guī)則，找到頂點(diǎn)所對(duì)應(yīng)的邊，并將該邊對(duì)應(yīng)的要素輸出[7]。

3 制圖試驗(yàn)

3.1 水系實(shí)體處理

以一幅區(qū)縣圖為例，水系實(shí)體要素達(dá)2 000多條，數(shù)據(jù)制圖綜合時(shí)采用軟件進(jìn)行自動(dòng)綜合處理（包括標(biāo)記長度不夠指標(biāo)的河流、河流彎曲化簡、湖泊彎曲化簡等步驟），處理過程如圖3所示。

圖3 水系實(shí)體處理過程圖Fig.3 Water entity processing chart

如果水系中存在環(huán)狀流向，則程序一直保持循環(huán)遍歷的狀態(tài)，無法繼續(xù)進(jìn)行到下一個(gè)步驟，至此水系自動(dòng)綜合將無法實(shí)現(xiàn)軟件自動(dòng)化，只能依靠人工進(jìn)行綜合判斷取舍，大大增加了工作量。

3.2 水系環(huán)路檢測試驗(yàn)

本文以Microsoft Visual Studio 2010與ArcEngine10.1為開發(fā)平臺(tái)，針對(duì)水系環(huán)狀流向問題，改進(jìn)深度優(yōu)先遍歷算法(DFS)形成一種新型算法，利用新型算法研發(fā)出快速、高效、可操作性強(qiáng)的循環(huán)水系檢測工具，具體開發(fā)工具界面運(yùn)行如圖4所示。

圖4 水系環(huán)路檢測工具Fig.4 hydrologic loop detection tool

該檢測工具的算法步驟為：首先通過水系環(huán)路檢測工具，自動(dòng)搜索地理國情普查圖制圖數(shù)據(jù)庫中的水系要素，建立水系有向圖，并利用拓?fù)渑判驒z測水系有向圖中有無環(huán)路；然后再通過改進(jìn)DFS算法計(jì)算搜索水系中的所有環(huán)路而不是部分環(huán)路；最后利用開發(fā)的工具輸出檢測結(jié)果文件HYDL_error，檢測結(jié)果如圖5所示。

圖5 水系要素中環(huán)路檢測結(jié)果Fig.5 Loop detection results of hydrologic elements

為了對(duì)深度優(yōu)先搜索算法(DFS)改進(jìn)前后水系環(huán)路檢測結(jié)果進(jìn)行對(duì)比分析，本文選取了同一區(qū)域的水系數(shù)據(jù)分別采用改進(jìn)前和改進(jìn)后的DFS算法檢測水系中的環(huán)路，結(jié)果如圖6所示。

圖6 DFS算法改進(jìn)前后水系環(huán)路檢測結(jié)果對(duì)比Fig.6 Comparison of loop detection results before and after DFS algorithm improvement

檢測結(jié)果表明，改進(jìn)前的DFS算法檢測環(huán)路時(shí)存在明顯的“漏環(huán)”現(xiàn)象，只能檢測出水系中較少部分的環(huán)路而不能將環(huán)路全部檢測出來。造成這種情況主要是由于DFS算法對(duì)水系有向圖進(jìn)行遍歷時(shí)，訪問過的節(jié)點(diǎn)已經(jīng)被標(biāo)記，當(dāng)檢測到外圍的環(huán)路時(shí)，環(huán)路中的頂點(diǎn)已經(jīng)被全部被標(biāo)記了訪問狀態(tài)，當(dāng)再次訪問頂點(diǎn)的其他連接點(diǎn)時(shí)，不再訪問，此種算法雖然能檢測出部分環(huán)路，但是沒有解決水系自動(dòng)綜合實(shí)現(xiàn)的問題，仍然會(huì)導(dǎo)致程序處于無限循環(huán)的狀態(tài)。而改進(jìn)后的DFS算法在處理環(huán)路時(shí)，出棧的過程中會(huì)重新修改頂點(diǎn)的訪問狀態(tài)，當(dāng)再次訪問到時(shí)可以繼續(xù)訪問其連接的其他頂點(diǎn)，由圖6知，水系中的環(huán)路已經(jīng)被全部檢測出來，檢測效果較好，針對(duì)檢測出的環(huán)路，可對(duì)其進(jìn)行局部人工反向或者程序反向修改，修改后的水系要素實(shí)體數(shù)據(jù)可重新導(dǎo)入普查圖制圖軟件進(jìn)行自動(dòng)化處理，能夠快速輸出成果。因此，制圖自動(dòng)綜合程序可快速順利運(yùn)行，不再出現(xiàn)循環(huán)遍歷的情況。

4 結(jié)束語

本文對(duì)地理國情普查圖制作工藝流程中水系自動(dòng)綜合處理遇到的水系環(huán)狀流向造成程序“死循環(huán)”問題進(jìn)行了研究，并提出了一種以有向圖的基本理論為基礎(chǔ)，對(duì)傳統(tǒng)DFS搜索的改進(jìn)形成的一種新型水系環(huán)路檢測的解決方法。通過水系的矢量特征，構(gòu)建水系有向圖，再通過有向圖的深度優(yōu)先遍歷算法，搜索水系中存在的環(huán)路并輸出。改進(jìn)前后的試驗(yàn)結(jié)果對(duì)比表明，改進(jìn)的DFS算法能夠有效檢測出水系中的環(huán)路，并且檢測結(jié)果更加精確。在試驗(yàn)成功的基礎(chǔ)上，利用地理信息系統(tǒng)開發(fā)平臺(tái)，研發(fā)了水系環(huán)路檢測工具，并將其集成應(yīng)用到地理國情普查圖制作的工藝流程中，批量解決了水系綜合處理過程中出現(xiàn)“死鎖”的問題，提高了制圖效率。