摘要：為解決嵌入式系統(tǒng)應(yīng)用電子航海圖出現(xiàn)的單幅圖存儲量、圖廓范圍過大，以及圖幅重疊等問題，以SHAPE格式圖為例，設(shè)計(jì)并實(shí)現(xiàn)了矢量電子航海圖的分割方法。采用多邊形布爾運(yùn)算法則處理多邊形的剪裁，不限制實(shí)體和剪裁多邊形類型，使得該分割方法不僅適用于等經(jīng)緯網(wǎng)格分割，也適用于不規(guī)則分割。應(yīng)用該分割方法對海圖數(shù)據(jù)進(jìn)行預(yù)處理，可以適應(yīng)硬件資源有限的嵌入式應(yīng)用，從而提高系統(tǒng)設(shè)計(jì)的自由度、降低總體成本，促進(jìn)電子海圖系統(tǒng)的推廣。
關(guān)鍵詞：水路運(yùn)輸；電子航海圖；嵌入式系統(tǒng)；多邊形剪裁；布爾運(yùn)算
矢量電子航海圖（以下簡稱矢量圖）是目前國內(nèi)外電子海圖應(yīng)用系統(tǒng)主流的數(shù)據(jù)類型，具體格式包括SHAPE、S57、MAPINFO等。在嵌入式系統(tǒng)上開發(fā)矢量圖的應(yīng)用程序，將不可避免地面臨以下問題：
1．單幅矢量圖的存儲數(shù)據(jù)量大，而且大小很不平均。以我國的SHAPE格式為例，單幅圖存儲的數(shù)據(jù)量從幾百k到十幾M，對主機(jī)內(nèi)存和CPU速度有較高要求。高端的PC機(jī)很容易滿足這兩點(diǎn)，而很多基于電子海圖的嵌入式應(yīng)用，由于CPU速度有限，裝載數(shù)據(jù)的時間往往超出用戶預(yù)計(jì)的范圍；或者其內(nèi)存就不足以裝載一幅海圖。
2．單幅矢量圖的范圍大大超過了一般顯示終端的大小。我國SHAPE格式海圖分幅與紙質(zhì)海圖一致，尺寸約100cm×80cm。為顯示屏幕內(nèi)小范圍數(shù)據(jù)，而遍歷整幅海圖，造成海圖繪制時間過長，效率不高。
3．矢量圖之間存在重疊現(xiàn)象。不僅浪費(fèi)了存儲空間，而且在查詢物標(biāo)時容易出現(xiàn)二義性。
本文提出分割矢量圖的方法解決以上問題。通過調(diào)整分割大小，可保證所有單幅圖的數(shù)據(jù)量在一定限度之內(nèi)適應(yīng)不同主機(jī)資源約束。通過預(yù)先的分割，可以采用簡單的數(shù)據(jù)結(jié)構(gòu)達(dá)到較高的顯示效率。而且，對于數(shù)據(jù)的重疊部分，分割后可以剔出，保證數(shù)據(jù)的唯一性。本文以SHAPE格式海圖為研究對象，應(yīng)用計(jì)算機(jī)圖形學(xué)中多邊形布爾運(yùn)算法則處理多邊形的剪裁，不限制實(shí)體和剪裁多邊形類型，使得該方法不僅適用于等間隔經(jīng)緯網(wǎng)分割，也適用于不規(guī)則分割。
1 矢量圖組織結(jié)構(gòu)
SHAPE格式矢量圖以圖幅為單位組織，一幅圖一個目錄，其文件由一個控制文件、多個圖形文件、索引文件、屬性文件組成。從內(nèi)容上看，一幅圖主要包括圖幅元數(shù)據(jù)、物標(biāo)的幾何和屬性數(shù)據(jù)。
圖形文件記錄物標(biāo)的幾何位置數(shù)據(jù)，為可變長記錄文件。索引文件記錄對應(yīng)的圖形文件，記錄相對于圖形文件開始點(diǎn)的偏移量。屬性文件為dBase表文件結(jié)構(gòu)，記錄了物標(biāo)的屬性。圖形文件記錄與屬性文件記錄通過記錄號一一對應(yīng)。控制文件主要包括：圖幅名稱、比例尺、圖廓邊界、投影方式等海圖元數(shù)據(jù)。
圖1 SHAPE格式圖組織結(jié)構(gòu)示意
2 分割流程
分割不僅包括幾何數(shù)據(jù)的剪裁，也包括元數(shù)據(jù)、屬性數(shù)據(jù)的重新賦值。分割后生成的新圖必須符合原有標(biāo)準(zhǔn)。受分割操作影響的元數(shù)據(jù)主要是圖廓邊界，屬性數(shù)據(jù)依賴于幾何數(shù)據(jù)存在，除類似周長、面積、最小外接矩形等屬性隨之改變外，其它類似燈標(biāo)燈質(zhì)、等深區(qū)水深等描述性屬性不隨分割操作而改變。
設(shè)定分割窗口；
if（矢量圖是否與分割窗口相交）then
{以原始圖廓與分割窗口的交集作為新的圖廓邊界；
Repeat
提取物標(biāo)層的信息，如物標(biāo)種類、數(shù)量、幾何類型、最小外接矩形、屬性類型列表等；
Repeat
根據(jù)記錄號提取物標(biāo)幾何數(shù)據(jù)和屬性數(shù)據(jù)
采用不同的剪裁算法處理點(diǎn)、線、面物標(biāo)
將原物標(biāo)屬性復(fù)制到分割后的物標(biāo)，重新計(jì)算新物標(biāo)與幾何特征相關(guān)屬性信息（周長、面積、長度、最小外接矩形等）
Until該層所有物標(biāo)處理完畢；
重新計(jì)算該層包含的物標(biāo)數(shù)量，最小外接矩形等信息；
Until所有物標(biāo)層處理完畢；
}
分割結(jié)束；
對于點(diǎn)狀物標(biāo)，分割方法很簡單，只需判斷點(diǎn)位是否位于分割窗口之內(nèi)，采取保留或放棄即可。線狀物標(biāo)的剪裁算法[1-2]也比較成熟，本文采用Reppaport A提出的線段剪裁算法。
3 多邊形剪裁
面狀物標(biāo)的處理相對復(fù)雜，特別是SHAPE格式規(guī)定的多邊形有如下幾個特點(diǎn)：
1．包含有“洞”多邊形。
2．多邊形頂點(diǎn)數(shù)目巨大。
3．頂點(diǎn)位置用浮點(diǎn)數(shù)表示。
以上特點(diǎn)分別從適用范圍、時間空間復(fù)雜度、數(shù)值魯棒性方面，對剪裁算法提出較高的要求。在分析比較文獻(xiàn)[3-10]的基礎(chǔ)上，本文依據(jù)Vatti B.R.算法[3]，采用布爾運(yùn)算法則剪裁SHAPE圖中的復(fù)雜多邊形，取得較好效果。為了便于描述，首先引入多邊形裁剪的一些基本概念。
3.1 基本概念
1）多邊形邊的方向與內(nèi)外區(qū)域的關(guān)系
當(dāng)多邊形邊的方向?yàn)轫槙r針時，沿著邊的方向，右側(cè)區(qū)域?yàn)槎噙呅蔚膬?nèi)部，左側(cè)區(qū)域?yàn)槎噙呅蔚耐獠俊７粗绻噙呅芜叺姆较驗(yàn)槟鏁r針，則左側(cè)區(qū)域?yàn)槎噙呅蔚膬?nèi)部，右側(cè)區(qū)域?yàn)槎噙呅蔚耐獠俊?/SPAN>
2）進(jìn)點(diǎn)和出點(diǎn)的定義
設(shè)I是多邊形S和C的一個交點(diǎn)。如果S沿著S的邊界方向在I點(diǎn)從C的外部進(jìn)入C的內(nèi)部，則稱I為S對于C的一個進(jìn)點(diǎn)。反之，如果S在I點(diǎn)從C的內(nèi)部出到C的外部，則稱I為S對于C的一個出點(diǎn)。進(jìn)點(diǎn)和出點(diǎn)定義是一個多邊形相對另一個同多邊形的[5]。如圖2所示，陰影部分為多邊形內(nèi)部，I為S對于C的進(jìn)點(diǎn)，是C對于S的出點(diǎn)。
圖2 進(jìn)點(diǎn)和出點(diǎn)的定義
3.2 布爾運(yùn)算和實(shí)例
下面介紹采用布爾運(yùn)算法則處理矢量圖中有“洞”多邊形的基本思路。不失一般性，設(shè)實(shí)體多邊形S和剪裁多邊形C都為有洞多邊形，采用集合表示方法
（1）
（2）
式（1）和式（2）中：S0、C0分別為兩多邊形的外部輪廓，S1…n、C1…n分別為兩多邊形的“洞”。在這里，多邊形的內(nèi)外邊界都是順時針方向。
1）確定兩多邊形內(nèi)外部輪廓之間的布爾算子。
多邊形剪裁的結(jié)果是兩個多邊形的交集。根據(jù)集合的布爾運(yùn)算法則，
（3）
以上結(jié)論可描述為：兩外部輪廓進(jìn)行交集運(yùn)算，得到交集的結(jié)果多邊形；洞與洞之間進(jìn)行并集運(yùn)算，如果結(jié)果多邊形之間還有相交，繼續(xù)并運(yùn)算；然后將洞的并集多邊形全部反向，與外部輪廓的交集多邊形再求交，得到最終結(jié)果。
對于分解后的每個布爾運(yùn)算，進(jìn)行“2）~4）”的操作：
2）求兩多邊形之間的交點(diǎn)，形成交點(diǎn)集。
3）判斷各交點(diǎn)處一個多邊形相對于另一個多邊形的出點(diǎn)、入點(diǎn)性質(zhì)。
4）從多邊形第一個交點(diǎn)出發(fā)，根據(jù)布爾算子和交點(diǎn)的進(jìn)出點(diǎn)性質(zhì)，判斷是否把跟蹤路線切換到另一個多邊形，并選擇正確的方向沿著相應(yīng)多邊形的邊繼續(xù)跟蹤。對于“交”操作，在交點(diǎn)處進(jìn)入多邊形；對于“并”操作，在交點(diǎn)處出多邊形。當(dāng)?shù)竭_(dá)下一個交點(diǎn)時，再次判斷是否切換多邊形，以及選擇正確的方向繼續(xù)跟蹤，直至又回到第一個交點(diǎn)，形成一條完整的回路[3]。如果交點(diǎn)集中仍有沒有被經(jīng)過的剩余交點(diǎn)，則繼續(xù)按照同樣的方法處理剩余的交點(diǎn)，直到所有的交點(diǎn)都被經(jīng)過。處理完畢得到的多邊形就是布爾運(yùn)算的結(jié)果。
如圖3所示，S0與C0交點(diǎn)為（I0，I6）。根據(jù)進(jìn)出點(diǎn)的定義，I0是S0到C0的進(jìn)點(diǎn)、I6是S0到C0的出點(diǎn)。S0∩C0的結(jié)果多邊形為（I0，，I6，
），設(shè)為A。S0與C0沒有未處理交點(diǎn)。再看S1與C1交點(diǎn)為（I2，I4），I2是S1到C1的進(jìn)點(diǎn)、I4是S1到C1的出點(diǎn)。S1∪C1的結(jié)果多邊形為（I2，
，
，
，I4，
，
，
），設(shè)為B。S1與C1也沒有未處理交點(diǎn)。將B反向得（I2，
，
，
，I4，
，
，
）。又求得A與B的交點(diǎn)（I1，I5，I7，I3）。其中，I1、I7是A相對B的出點(diǎn)，B相對A的進(jìn)點(diǎn)；I5、I3是A相對B的進(jìn)點(diǎn)，B相對A的出點(diǎn)。從I1開始，A∩B的一個結(jié)果多邊形為（I1，I2，I3，I0）；由于還有未處理的交點(diǎn)（I5，I7），再從I1開始，另一個結(jié)果多邊形為（I5，I6，I7，I4）。因此，A∩B得到的兩個多邊形即為S∩C的最終結(jié)果。
圖3 多邊形剪裁實(shí)例
該算法具備以不規(guī)則形狀分割矢量圖的功能，圖4是對同一幅海圖進(jìn)行星型和矩形分割的結(jié)果。從應(yīng)用角度來看，矩形分割最為廣泛。矩形大小主要考慮內(nèi)存和顯示器尺寸。以我國出版的SHAPE格式矢量電子航海圖為例，數(shù)據(jù)總量約800MByte，存在700萬、400萬、230萬、100萬、50萬、25萬、10萬等比例尺級別的單幅圖對應(yīng)紙質(zhì)圖幅。對于兩種硬件條件（工業(yè)主板：64M內(nèi)存、12寸液晶屏；掌上電腦：32M程序內(nèi)存、5寸液晶屏），對相應(yīng)比例尺圖采用30°、20°、10°、5°、2°、1°和20°、10°、5°、2°、1°、30′經(jīng)緯度方格兩種方案進(jìn)行分割。兩種方案分割后的矢量圖，在相應(yīng)的硬件環(huán)境下均滿足內(nèi)存約束，且顯示速度達(dá)到適時性要求。
圖4 海圖分割結(jié)果
4 結(jié)語
目前本文研究的算法僅限于無拓?fù)潢P(guān)系的矢量圖。對于類似S57等有拓?fù)涞氖噶繄D，還需考慮分割后拓?fù)潢P(guān)系的重建。
參考文獻(xiàn)
[1] Reppaport A．An efficient algorithm for line and polygon clipping[J]．Visual Computer，1991，7（1）：19-28
[2] 劉勇奎，顏葉，石教英．一個有效的多邊形窗口的線裁剪算法[J]．計(jì)算機(jī)學(xué)報(bào)，1999，22（11）：1209-1214．
[3] Vatti B R．A generic solution to polygon clipping[J]．Communications of the ACM，1992，35（1）：56-63．
[4] Greiner G，Hormann K．Efficient clipping of arbitrary polygons[J]．ACM Transactions on Graphics，1998，17（2）：71-83．
[5] Rivero M L，Feito F R．Boolean operations on general planar polygons[J]．Computer &Graphics，2000，24（6）：881-896
[6] 劉勇奎，高云，黃有群．一個有效的多邊形裁剪算法[J]．軟件學(xué)報(bào)，2003，14（4）：845-856．
[7] 劉紅軍，王從軍，黃樹槐．帶有孔洞的多邊形的布爾算法[J]．華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，31（8）：18-20．
[8] 董未名，瑪依拉•巴榜，周登文，等．平面擴(kuò)展簡單多邊形的布爾運(yùn)算[J]．計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003，15（9）：1134-1140．
[9] 謝步瀛，張巖．用分段法與鏈表法的二維布爾運(yùn)算[J]．工程圖學(xué)學(xué)報(bào)，2003，24（2）：78-84．
[10] 姚輝學(xué)，盧章平．海量數(shù)據(jù)多邊形布爾運(yùn)算的區(qū)域分割算法[J]．中國圖象圖形學(xué)報(bào)，2007，12（3）：552-557．
作者：鐘云海 鄭海 周建波 來源：中國航海
