倪文輝，李維慶，甘元芳

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

0 引 言

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

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

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

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

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

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

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

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

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

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

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

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

1）讀取水系實體要素數(shù)據(jù)(HYDL)，并遍歷水系實體的每個要素(Feature)。

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

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

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

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

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

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

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

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

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

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

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

2.3 DFS算法理論

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

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

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

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

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

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

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

3 制圖試驗

3.1 水系實體處理

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

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

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

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

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

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

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

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

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

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

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

4 結(jié)束語

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