內河電子海圖上可航區域中心線自動繪制

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

(武漢中原電子集團 應用電子研發中心， 武漢 430074)

內河電子海圖上可航區域中心線自動繪制

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

(武漢中原電子集團 應用電子研發中心， 武漢 430074)

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

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

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

1 算 法

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

1.1可航水深面形成算法

1.1.1平面點集求凸包問題

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

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

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

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

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

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

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

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

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

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

(2) 在笛卡爾直角坐標系下，遍歷{Pi}每個點，尋找集合中最小y坐標值對應的點(若有多個點的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)”；若相等，則退出循環，算法終止。

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

圖1 “1.1.1”和“1.1.2”算法結果比較圖

1.1.3可航水深面形成算法

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

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

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

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

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

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

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

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

圖2 “1.1.3”算法流程圖

1.2可航區域中心線生成算法

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

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

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

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

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

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

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

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

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

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

圖3 “1.2”算法流程圖

2 仿真實驗

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

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

注：多邊形為假設的可航區邊界，中間虛線為假設的長江骨架線，環繞洞多邊形的線是生成的中心線

圖5 “1.2”算法試驗圖

注：灰色區域為形成的可航水深面，中間黑線為生成的動態中心線

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

3 結 語

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

在內河電子海圖上，自動形成可航區域并生成其可航中心線技術是一種新型航海技術。隨著人們對航海自動導航技術的要求越來越高，相信在不久的將來，會有更多、更優秀的與此相關的算法或技術產生，中國的航海技術將取得更大的進步。

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

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

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

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

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

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

[7] 周培德.計算幾何-算法分析與設計[M].北京:清華大學出版社,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] 蔣紅斐.平面點集凸包快速構建算法的研究[J].計算機工程與應用,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

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

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

1000-4653(2014)04-0011-04

U675.81

A