摘要:為解決嵌入式系統(tǒng)應(yīng)用電子航海圖出現(xiàn)的單幅圖存儲量、圖廓范圍過大,以及圖幅重疊等問題,以SHAPE格式圖為例,設(shè)計并實現(xiàn)了矢量電子航海圖的分割方法。采用多邊形布爾運(yùn)算法則處理多邊形的剪裁,不限制實體和剪裁多邊形類型,使得該分割方法不僅適用于等經(jīng)緯網(wǎng)格分割,也適用于不規(guī)則分割。應(yīng)用該分割方法對海圖數(shù)據(jù)進(jìn)行預(yù)處理,可以適應(yīng)硬件資源有限的嵌入式應(yīng)用,從而提高系統(tǒng)設(shè)計的自由度、降低總體成本,促進(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ī)很容易滿足這兩點,而很多基于電子海圖的嵌入式應(yīng)用,由于CPU速度有限,裝載數(shù)據(jù)的時間往往超出用戶預(yù)計的范圍;或者其內(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ī)圖形學(xué)中多邊形布爾運(yùn)算法則處理多邊形的剪裁,不限制實體和剪裁多邊形類型,使得該方法不僅適用于等間隔經(jīng)緯網(wǎng)分割,也適用于不規(guī)則分割。
1 矢量圖組織結(jié)構(gòu)
SHAPE格式矢量圖以圖幅為單位組織,一幅圖一個目錄,其文件由一個控制文件、多個圖形文件、索引文件、屬性文件組成。從內(nèi)容上看,一幅圖主要包括圖幅元數(shù)據(jù)、物標(biāo)的幾何和屬性數(shù)據(jù)。
圖形文件記錄物標(biāo)的幾何位置數(shù)據(jù),為可變長記錄文件。索引文件記錄對應(yīng)的圖形文件,記錄相對于圖形文件開始點的偏移量。屬性文件為dBase表文件結(jié)構(gòu),記錄了物標(biāo)的屬性。圖形文件記錄與屬性文件記錄通過記錄號一一對應(yīng)??刂莆募饕ǎ簣D幅名稱、比例尺、圖廓邊界、投影方式等海圖元數(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ù)
采用不同的剪裁算法處理點、線、面物標(biāo)
將原物標(biāo)屬性復(fù)制到分割后的物標(biāo),重新計算新物標(biāo)與幾何特征相關(guān)屬性信息(周長、面積、長度、最小外接矩形等)
Until該層所有物標(biāo)處理完畢;
重新計算該層包含的物標(biāo)數(shù)量,最小外接矩形等信息;
Until所有物標(biāo)層處理完畢;
}
分割結(jié)束;
對于點狀物標(biāo),分割方法很簡單,只需判斷點位是否位于分割窗口之內(nèi),采取保留或放棄即可。線狀物標(biāo)的剪裁算法[1-2]也比較成熟,本文采用Reppaport A提出的線段剪裁算法。
3 多邊形剪裁
面狀物標(biāo)的處理相對復(fù)雜,特別是SHAPE格式規(guī)定的多邊形有如下幾個特點:
1.包含有“洞”多邊形。
2.多邊形頂點數(shù)目巨大。
3.頂點位置用浮點數(shù)表示。
以上特點分別從適用范圍、時間空間復(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)多邊形邊的方向為順時針時,沿著邊的方向,右側(cè)區(qū)域為多邊形的內(nèi)部,左側(cè)區(qū)域為多邊形的外部。反之,如果多邊形邊的方向為逆時針,則左側(cè)區(qū)域為多邊形的內(nèi)部,右側(cè)區(qū)域為多邊形的外部。
2)進(jìn)點和出點的定義
設(shè)I是多邊形S和C的一個交點。如果S沿著S的邊界方向在I點從C的外部進(jìn)入C的內(nèi)部,則稱I為S對于C的一個進(jìn)點。反之,如果S在I點從C的內(nèi)部出到C的外部,則稱I為S對于C的一個出點。進(jìn)點和出點定義是一個多邊形相對另一個同多邊形的[5]。如圖2所示,陰影部分為多邊形內(nèi)部,I為S對于C的進(jìn)點,是C對于S的出點。
圖2 進(jìn)點和出點的定義
3.2 布爾運(yùn)算和實例
下面介紹采用布爾運(yùn)算法則處理矢量圖中有“洞”多邊形的基本思路。不失一般性,設(shè)實體多邊形S和剪裁多邊形C都為有洞多邊形,采用集合表示方法
式(1)和式(2)中:S0、C0分別為兩多邊形的外部輪廓,S1…n、C1…n分別為兩多邊形的“洞”。在這里,多邊形的內(nèi)外邊界都是順時針方向。
1)確定兩多邊形內(nèi)外部輪廓之間的布爾算子。
多邊形剪裁的結(jié)果是兩個多邊形的交集。根據(jù)集合的布爾運(yùn)算法則,
以上結(jié)論可描述為:兩外部輪廓進(jìn)行交集運(yùn)算,得到交集的結(jié)果多邊形;洞與洞之間進(jìn)行并集運(yùn)算,如果結(jié)果多邊形之間還有相交,繼續(xù)并運(yùn)算;然后將洞的并集多邊形全部反向,與外部輪廓的交集多邊形再求交,得到最終結(jié)果。
對于分解后的每個布爾運(yùn)算,進(jìn)行“2)~4)”的操作:
2)求兩多邊形之間的交點,形成交點集。
3)判斷各交點處一個多邊形相對于另一個多邊形的出點、入點性質(zhì)。
4)從多邊形第一個交點出發(fā),根據(jù)布爾算子和交點的進(jìn)出點性質(zhì),判斷是否把跟蹤路線切換到另一個多邊形,并選擇正確的方向沿著相應(yīng)多邊形的邊繼續(xù)跟蹤。對于“交”操作,在交點處進(jìn)入多邊形;對于“并”操作,在交點處出多邊形。當(dāng)?shù)竭_(dá)下一個交點時,再次判斷是否切換多邊形,以及選擇正確的方向繼續(xù)跟蹤,直至又回到第一個交點,形成一條完整的回路[3]。如果交點集中仍有沒有被經(jīng)過的剩余交點,則繼續(xù)按照同樣的方法處理剩余的交點,直到所有的交點都被經(jīng)過。處理完畢得到的多邊形就是布爾運(yùn)算的結(jié)果。
如圖3所示,S0與C0交點為(I0,I6)。根據(jù)進(jìn)出點的定義,I0是S0到C0的進(jìn)點、I6是S0到C0的出點。S0∩C0的結(jié)果多邊形為(I0,,I6,),設(shè)為A。S0與C0沒有未處理交點。再看S1與C1交點為(I2,I4),I2是S1到C1的進(jìn)點、I4是S1到C1的出點。S1∪C1的結(jié)果多邊形為(I2,,,,I4,,,),設(shè)為B。S1與C1也沒有未處理交點。將B反向得(I2,,,,I4,,,)。又求得A與B的交點(I1,I5,I7,I3)。其中,I1、I7是A相對B的出點,B相對A的進(jìn)點;I5、I3是A相對B的進(jìn)點,B相對A的出點。從I1開始,A∩B的一個結(jié)果多邊形為(I1,I2,I3,I0);由于還有未處理的交點(I5,I7),再從I1開始,另一個結(jié)果多邊形為(I5,I6,I7,I4)。因此,A∩B得到的兩個多邊形即為S∩C的最終結(jié)果。
圖3 多邊形剪裁實例
該算法具備以不規(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ī)學(xué)報,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é)報,2003,14(4):845-856.
[7] 劉紅軍,王從軍,黃樹槐.帶有孔洞的多邊形的布爾算法[J].華中科技大學(xué)學(xué)報(自然科學(xué)版),2003,31(8):18-20.
[8] 董未名,瑪依拉•巴榜,周登文,等.平面擴(kuò)展簡單多邊形的布爾運(yùn)算[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2003,15(9):1134-1140.
[9] 謝步瀛,張巖.用分段法與鏈表法的二維布爾運(yùn)算[J].工程圖學(xué)學(xué)報,2003,24(2):78-84.
[10] 姚輝學(xué),盧章平.海量數(shù)據(jù)多邊形布爾運(yùn)算的區(qū)域分割算法[J].中國圖象圖形學(xué)報,2007,12(3):552-557.
作者:鐘云海 鄭海 周建波 來源:中國航海