內(nèi)河電子海圖上可航區(qū)域中心線自動繪制

白 云， 代志強， 張東華， 李 寧

(武漢中原電子集團 應(yīng)用電子研發(fā)中心， 武漢 430074)

內(nèi)河電子海圖上可航區(qū)域中心線自動繪制

白 云， 代志強， 張東華， 李 寧

(武漢中原電子集團 應(yīng)用電子研發(fā)中心， 武漢 430074)

為研究內(nèi)河可航區(qū)域中心線自動繪制技術(shù)，分別提出可航水深面形成算法和可航區(qū)域中心線生成算法。在可航水深面形成算法的實現(xiàn)中，參考計算幾何學(xué)求點集凸包領(lǐng)域的相關(guān)理論和算法，推廣實現(xiàn)包圍點集的任意多邊形算法。可航區(qū)域中心線生成算法更像一個解決方案，是在可航水深面形成的基礎(chǔ)上進一步實現(xiàn)得到的，在船舶水上導(dǎo)航方面具有較大意義。所提出的算法已在基于長江航道圖2.0的嵌入式ECS產(chǎn)品上得到應(yīng)用，取得了良好效果。

水路運輸；可航中心線；自動繪制； 凸包； 任意多邊形

中國海事局和長江航道局共同擬定：在船載電子海圖系統(tǒng)(Electronic Chart System, ECS)產(chǎn)品上，實現(xiàn)長江電子航道圖2.0版的應(yīng)用需求。在長江電子航道圖2.0版高級功能需求中，要求根據(jù)長江航道圖上已有的水深點，以河段為單位，根據(jù)船的吃水深度，計算出船的可航區(qū)域，并在終端航道圖上自動繪制該可航區(qū)域的中心線。這是一個全新的技術(shù)設(shè)想，出于項目開發(fā)需求，對該問題進行深入研究，對研究得到的技術(shù)以算法的形成描述出來。

1 算 法

對可航區(qū)域中心線自動繪制技術(shù)的研究中，實際上最終形成了2種算法，即：可航水深面形成算法，可航區(qū)域中心線生成算法。

1.1可航水深面形成算法

1.1.1平面點集求凸包問題

在平面上存在的若干離散點已知的情況下確定一個覆蓋這些點的面積最小的凸多邊形，是計算幾何領(lǐng)域著名的求點集最小凸包問題。其和另一個求多邊形凸包數(shù)問題的研究一起，促使了計算幾何學(xué)的最終形成。

20世紀60年代以來，有關(guān)平面點集凸包問題的研究引起了相關(guān)學(xué)者的廣泛關(guān)注。經(jīng)過多年研究，已擁有多種求解此問題的算法，并已在圖形學(xué)、圖像處理[1-4]、材料切割[2]、GIS(Geographic Information System)[4-6]等領(lǐng)域得到廣泛應(yīng)用。較為經(jīng)典的算法有卷包裹算法[2-3,7-8](Gift Swapping Method)、Jarvis進步法[2-3,9]、Graham_Scan算法[2-3,7,10]、分治算法[7,11]等。Jarvis算法是2維平面,卷包裹算法是n維空間，兩種算法在2維平面下是完全相同的，因此有文獻也將Jarvis進步法稱為卷包裹算法。卷包裹算法是一種比較簡單、容易實現(xiàn)的算法，其缺點是效率不高。該算法的思想為：

(1) 從點集中尋找最小y坐標值對應(yīng)的點，即可求得凸包的第1個頂點P0；

(2) 過該P0作一條水平直線l0，使l0繞P0順時針旋轉(zhuǎn)，點集中第1個被l0碰到的點(記為P1)便是凸包的第2個頂點；

(3) 以P1為中心，按照上面的方法，尋求下一個凸包的頂點，直到l0旋轉(zhuǎn)360°，返回至P0處，便獲得了凸包的所有頂點。

該步驟實際上涉及了求2條射線夾角的問題，該夾角應(yīng)被規(guī)范到 [0°,180°]，否則算法無法實現(xiàn)。

1.1.2覆蓋平面點集的任意多邊形生成算法

在GIS領(lǐng)域，最小凸包常用于描述空間物體的最小形態(tài)。若使用其對長江地圖上已知若干水深點的面域的形態(tài)進行描繪，將使描繪區(qū)域包含大量非法(不滿足要求)水面區(qū)域。因此，需要考慮實現(xiàn)一種覆蓋平面點集的任意多邊形算法。

在研究卷包裹算法時，產(chǎn)生一種想法：若在運用該算法獲得每個凸包頂點Pi的過程中加設(shè)一個以Pi為圓心、半徑為R的圓，然后從落入該圓內(nèi)的平面點中尋求所求凸包的頂點，也有可能得到一個覆蓋平面點集的多邊形。經(jīng)過深入研究，成功發(fā)現(xiàn)一種可覆蓋平面點集的任意多邊形算法，具體如下：

(1) 已知集合{Pi}，定義一個集合類型變量Polygon，設(shè)置距離半徑R的值，定義向量a=(ax,ay)，并初始化ax=1，ay=0(即x軸正方向)；

(2) 在笛卡爾直角坐標系下，遍歷{Pi}每個點，尋找集合中最小y坐標值對應(yīng)的點(若有多個點的y坐標都為最小值，可不必考慮)，記其為P0=(x0,y0)，P0便是所求多邊形的第1個頂點，將其壓入變量Polygon中；

(4) 用P0←P1，a←P1P0替代，即x0=x1，y0=y1，ax=x1-x0，ay=y1-y0；

(5) 判斷P1是否等于P0。若不相等，則返回“(3)”；若相等，則退出循環(huán)，算法終止。

在算法中，半徑R的值要根據(jù)實際離散點數(shù)據(jù)選擇。若R值較小，不能保證每次設(shè)定的圓內(nèi)都有點集中的點落入，可能導(dǎo)致結(jié)果出錯。若R值過大，則所得多邊形對平面點集分布區(qū)域估計比較粗略。在具體應(yīng)用中，可根據(jù)平面點集的分布狀態(tài)估計R的合理值，再利用實驗結(jié)果反復(fù)調(diào)整。圖1具體說明了“1.1.1”和“1.1.2”算法產(chǎn)生的不同效果。

圖1 “1.1.1”和“1.1.2”算法結(jié)果比較圖

1.1.3可航水深面形成算法

在獲得覆蓋平面點集的任意多邊形算法后，還需要一種點集子集劃分算法[12]，只有如此才能具備形成可航水深面的能力。對于一片水域(此水域用記錄了水位信息的海量離散水深點表示)，若給出一個界定可航區(qū)域的臨界值，求該臨界值下的可航區(qū)域，通常得到的結(jié)果是在一個較大的可航區(qū)域中包若干個非法(不滿足可航要求)區(qū)域。因此，需對這些非法點組成的集合按某種規(guī)則進行劃分，獲得其所有互不相交的子集。

點集子集劃分算法運用了遞歸算法。

(1) 預(yù)設(shè)一個半徑值R，該半徑值應(yīng)該為“1.1.2”中所設(shè)半徑的1/2；

(2) 創(chuàng)建一個新的集合對象，從已知集合中任意取出一個元素，存入該新集合，于是原始集合被劃分為2個子集：選擇點集(新集合)和剩余點集；

(3) 計算兩子集元素之間的距離，若該距離lt;2R，則將該距離對應(yīng)的剩余點集的點從該集合中取走，存入選擇點集，并退出本次遍歷；

(4) 重新遍歷選擇和剩余集合，直到兩子集元素之間的距離都gt;2R，此時表明在距離R的界定下，一個新子集已經(jīng)確立；

(5) 遞歸調(diào)用函數(shù)本身，尋找下一個子集，直到剩余集合的元素個數(shù)為0，遞歸結(jié)束，至此完成了對原集合的一個劃分。

在實現(xiàn)了覆蓋平面點集的任意多邊形算法和平面點集分塊算法之后，剩下的工作就容易實現(xiàn)了。圖2給出了水深面形成的算法流程圖。

圖2 “1.1.3”算法流程圖

1.2可航區(qū)域中心線生成算法

可航區(qū)域中心線生成算法需要以可航水深面形成算法為基礎(chǔ)，同時利用一種地理測繪數(shù)據(jù)——長江干線航道骨架線。該數(shù)據(jù)由長江航道局提供，大致每隔2～3 km會產(chǎn)生一個結(jié)點，可用其描述長江的線性幾何形狀。

求取可航區(qū)域中心線的一個基本方法是：將長江干線骨架線的每一條線段按一定距離分成若干段，在每個分點處作骨架線的垂線，垂線與可航水深面邊界有2個交點，計算這2個交點的中點，然后將所有的中點按順序連接起來，即可形成可航中心線。問題似乎并不難解決，但事實上，在考慮到可航區(qū)域內(nèi)有洞多邊形以及需要面對復(fù)雜數(shù)據(jù)時，問題就顯得很難處理。

對于某一可航水深面，其外邊界僅有一個且最大，而內(nèi)邊界(洞多邊形)通常有多個，這會造成通過作一條垂線獲得的中心點不止一個。因此，在產(chǎn)生的前后中心點組間 (通過同一條垂線獲得的中心點稱其為一個中心點組)進行連線，并保證不與可航內(nèi)邊界相交，以及保證線路的連續(xù)性和智能性，成為解決該問題的難點和關(guān)鍵。在經(jīng)過不斷模擬長江可航區(qū)域和多次試驗后，最終確立如下解決方案。

在獲得各中心點組時，需對每組中心點按縱坐標y值的大小排序。在此前提下，設(shè)需要在第i組和第i+1中心點組之間連線。根據(jù)前后兩組所含中心點個數(shù)，可分5種情況對應(yīng)處理：

1) 當兩組所含中心點個數(shù)相等時，按順序前后一一對應(yīng)相連。

2) 當兩組所含中心點個數(shù)為多對一時，第i組所含每個中心點都與第i+1組中的點相連，同時判斷連線與附近多邊形是否相交。若相交，則從下一組中尋找不相交連線。

3) 當兩組所含中心點個數(shù)為一對多(gt;1)時，第i+1組所含中心點均與第i組中的點相連，同時判斷連線與附近多邊形是否相交。若相交，則從上一組中尋找不相交連線。

4) 當兩組所含中心點個數(shù)為多對少(gt;1)時，將第i組中心點按次序每2個點分為1組，其中相鄰組共用1個中心點；所得各小組依順序與第i+1組中對應(yīng)相連，若有溢出，溢出點均與第i+1組最后一個點相連，同時判斷連線與附近多邊形是否相交；若某連線與附近多邊形相交，設(shè)立一個整型參數(shù)m，m的選擇與數(shù)據(jù)水深點分布有關(guān)(一般取3或4即可)，然后從第i+2組到第i+m組中尋找與第i組中心點不相交的連線。若存在，最終選擇1條距離最短的連線；若不存在，則從第i-1組到第i-m組尋找與第i+1組中心點不相交的連線；上下搜尋不超出m范圍。

5) 當兩組所含中心點個數(shù)為少(gt;1)對多時，做法和多對少類似，只是第i組和第i+1組在前幾句表述中的位置需要置換。

解決了相鄰中心點組連線問題后，仍會遇到很多其他問題。例如，某條連線在某處與某個多邊形非常接近但沒有相交，顯然這樣的航路是不安全的，解決方法是對內(nèi)多邊形作Buffer區(qū)，將“判斷是否與多邊形相交”改為“判斷與其Buffer區(qū)是否相交”。此外，還需解決當可航區(qū)邊界(外邊界或內(nèi)邊界)像月牙形狀時，一條垂線可能會與某邊界多邊形有2個以上交點，以及提早與尾部相交，某中心點組的某些點的地理位置在小于其序號的中心點組的前面而造成連線回折等問題(因篇幅有限，不進行詳細介紹)。圖3為該可航區(qū)域中心線生成算法的流程圖。

圖3 “1.2”算法流程圖

2 仿真實驗

由于所提出的算法主要針對長江電子地圖2.0版的水深點數(shù)據(jù)和表示長江幾何形狀的地圖數(shù)據(jù)，因此在進行算法仿真時應(yīng)使試驗數(shù)據(jù)盡可能地符合長江地圖相關(guān)數(shù)據(jù)特點。長江地圖水深點數(shù)據(jù)分布情況為：沿長江走勢每隔一段距離(該距離不是一個固定值，但均相差不大)會出現(xiàn)一排記錄長江水位信息的離散的平面幾何點(簡稱水深點)，橫跨長江兩岸，動態(tài)記錄水位信息，且這些點分布也比較均勻。利用VC++編譯環(huán)境在視窗口上依照長江地圖數(shù)據(jù)特點隨機生成一些平面點，并讓一個隨機函數(shù)產(chǎn)生這些點的水位信息，接著輸入一個值作為判斷可航區(qū)域的臨界值，利用可航區(qū)域形成算法生成可航區(qū)域的邊界多邊形。另外，在VC視窗上，分別用一條線和一個多邊形模擬長江干線航道的骨架線和部分長江區(qū)域，然后通過可航中心線生成算法繪制可航中心線。為展示算法的繪制效果，分別給出試驗示意圖和實際工程應(yīng)用圖(見圖4～圖6)。

圖4 “1.1.3”算法試驗圖(可航臨界值為8)

注：多邊形為假設(shè)的可航區(qū)邊界，中間虛線為假設(shè)的長江骨架線，環(huán)繞洞多邊形的線是生成的中心線

圖5 “1.2”算法試驗圖

注：灰色區(qū)域為形成的可航水深面，中間黑線為生成的動態(tài)中心線

圖6 可航水深面形成及其中心線生成算法工程應(yīng)用圖

3 結(jié) 語

基于2.0版長江電子航道圖的應(yīng)用需求，研究了內(nèi)河可航區(qū)域中心線自動繪制技術(shù)，分別提出了可航水深面形成算法和可航區(qū)域中心線生成算法。在可航水深面形成算法中，提出了覆蓋平面點集的任意多邊形算法，該算法可以看作對卷包裹算法的推廣，使得對平面點集面狀區(qū)域的估計更為精確；而可航區(qū)域中心線生成算法在大多數(shù)情況下都能得到良好的繪制結(jié)果。兩種算法均已在公司項目中得到實際應(yīng)用，實踐證明算法具有良好的穩(wěn)定性和較高的效率。

在內(nèi)河電子海圖上，自動形成可航區(qū)域并生成其可航中心線技術(shù)是一種新型航海技術(shù)。隨著人們對航海自動導(dǎo)航技術(shù)的要求越來越高，相信在不久的將來，會有更多、更優(yōu)秀的與此相關(guān)的算法或技術(shù)產(chǎn)生，中國的航海技術(shù)將取得更大的進步。

[1] 劉斌,王濤.一種高效的平面點集凸包遞歸算法[J].自動化學(xué)報,2012,38(8): 1375-1379.

[2] 陳平.計算幾何若干問題的研究[D]. 浙江:浙江大學(xué),2006.

[3] 周之英.平面點集凸殼的實時算法[J].計算機學(xué)報,1985,8(2):136-142.

[4] 劉人午,楊德宏,李燕,等.一種改進的最小凸包生成算法[J].大地測量與地球動力學(xué),2011,31(3): 130-133.

[5] 程三友,李英杰.一種新的最小凸包算法及其應(yīng)用[J].地理與地理信息科學(xué),2009,25(5):43-45.

[6] 吳文周,李利番,王結(jié)臣.平面點集凸包Graham 算法的改進[J]. 測繪科學(xué),2010,35(6)：123-125.

[7] 周培德.計算幾何-算法分析與設(shè)計[M].北京:清華大學(xué)出版社,1999：57-84.

[8] CHAND D R, KAPUR S S. An Algorithm for Convex Polytopes[J]. Journal of the ACM ,1982:64-68.

[9] JARVIS A R. On the Identification of the Convex Hull of a Finite Set of Points in the Plane[J].Proc Lett,1973,2(1):18-22．

[10] GRAHAM R L. An Efficient Algorithm for Determining the Convex Hull of a Finite Point Set[J].Info Proc Lett, 1972(1):132-133.

[11] PREPARATA F P. An Optimal Real Time Algorithm for Planar Convex Hulls[J].ACM ,1979(22): 402-406.

[12] 蔣紅斐.平面點集凸包快速構(gòu)建算法的研究[J].計算機工程與應(yīng)用,2002(20)：48-49.

AutomaticPlottingofCenterLineofNavigableWatersonInlandRiverElectronicCharts

BAIYun，DAIZhiqiang，ZHANGDonghua，LINing

(Applied Electronics Ramp;D Center, Wuhan Zhongyuan Electronics Group Co., Ltd, Wuhan 430074, China)

The algorithms to define the cross sections of a navigable channel and the center line of the channel based on the water depth data of the inland river electronic charts are introduced. The algorithm for finding the bounding arbitrary polygon of the channel cross section is designed based on the convex hull principle of computational geometry. The central line algorithm gives the center line of the channel through processing the series of bounding polygons of cross sections to indicate the navigable path. The proposed algorithms have been integrated with the digital hydrographic chart of the Changjiang River (version 2.0) and proved to be effective.

waterway transportation; navigable center line； automatic plotting； convex hull； arbitrary polygon

2014-07-13

國家高技術(shù)研究發(fā)展計劃(“八六三”計劃)項目(2012AA112303)

白 云(1977—)， 男，浙江鎮(zhèn)海人，博士，主要研究方向為嵌入式軟件、無線通信等。E-mail: yiab2010@qq.com

1000-4653(2014)04-0011-04

U675.81

A