基于有向圖理論的循環(huán)水系檢測(cè)方法研究與制圖試驗(yàn)

倪文輝，李維慶，甘元芳

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

0 引 言

2013年至2015年開展的第一次全國地理國情普查開啟了我國測(cè)繪地理信息工作的一個(gè)新領(lǐng)域，地理國情信息為科學(xué)制定經(jīng)濟(jì)社會(huì)發(fā)展重大戰(zhàn)略、長遠(yuǎn)規(guī)劃和宏觀政策提供了一種新的基礎(chǔ)信息。地理國情普查數(shù)據(jù)采集工作完成后，以及隨著常態(tài)化地理國情監(jiān)測(cè)的開展，在未來很長一段時(shí)間內(nèi)，地理國情普查成果及地理國情監(jiān)測(cè)成果的轉(zhuǎn)化應(yīng)用將是測(cè)繪地理信息部門的一項(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)水系檢測(cè)中，對(duì)傳統(tǒng)深度優(yōu)先遍歷(DFS)算法改進(jìn)形成循環(huán)水系檢測(cè)的技術(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測(cè)出構(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)路檢測(cè)的技術(shù)流程，改進(jìn)DFS算法實(shí)現(xiàn)思路如圖2所示。

圖2 改進(jìn)DFS算法檢測(cè)水系環(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)路檢測(cè)試驗(yàn)

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

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

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

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

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

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

檢測(cè)結(jié)果表明，改進(jìn)前的DFS算法檢測(cè)環(huán)路時(shí)存在明顯的“漏環(huán)”現(xiàn)象，只能檢測(cè)出水系中較少部分的環(huán)路而不能將環(huán)路全部檢測(cè)出來。造成這種情況主要是由于DFS算法對(duì)水系有向圖進(jìn)行遍歷時(shí)，訪問過的節(jié)點(diǎn)已經(jīng)被標(biāo)記，當(dāng)檢測(cè)到外圍的環(huán)路時(shí)，環(huán)路中的頂點(diǎn)已經(jīng)被全部被標(biāo)記了訪問狀態(tài)，當(dāng)再次訪問頂點(diǎn)的其他連接點(diǎn)時(shí)，不再訪問，此種算法雖然能檢測(cè)出部分環(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)被全部檢測(cè)出來，檢測(cè)效果較好，針對(duì)檢測(cè)出的環(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)路檢測(cè)的解決方法。通過水系的矢量特征，構(gòu)建水系有向圖，再通過有向圖的深度優(yōu)先遍歷算法，搜索水系中存在的環(huán)路并輸出。改進(jìn)前后的試驗(yàn)結(jié)果對(duì)比表明，改進(jìn)的DFS算法能夠有效檢測(cè)出水系中的環(huán)路，并且檢測(cè)結(jié)果更加精確。在試驗(yàn)成功的基礎(chǔ)上，利用地理信息系統(tǒng)開發(fā)平臺(tái)，研發(fā)了水系環(huán)路檢測(cè)工具，并將其集成應(yīng)用到地理國情普查圖制作的工藝流程中，批量解決了水系綜合處理過程中出現(xiàn)“死鎖”的問題，提高了制圖效率。