摘要：為解決嵌入式系統(tǒng)應(yīng)用電子航海圖出現(xiàn)的單幅圖存儲(chǔ)量、圖廓范圍過(guò)大，以及圖幅重疊等問(wèn)題，以SHAPE格式圖為例，設(shè)計(jì)并實(shí)現(xiàn)了矢量電子航海圖的分割方法。采用多邊形布爾運(yùn)算法則處理多邊形的剪裁，不限制實(shí)體和剪裁多邊形類型，使得該分割方法不僅適用于等經(jīng)緯網(wǎng)格分割，也適用于不規(guī)則分割。應(yīng)用該分割方法對(duì)海圖數(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)算

矢量電子航海圖（以下簡(jiǎn)稱矢量圖）是目前國(guó)內(nèi)外電子海圖應(yīng)用系統(tǒng)主流的數(shù)據(jù)類型，具體格式包括SHAPE、S57、MAPINFO等。在嵌入式系統(tǒng)上開(kāi)發(fā)矢量圖的應(yīng)用程序，將不可避免地面臨以下問(wèn)題：

1．單幅矢量圖的存儲(chǔ)數(shù)據(jù)量大，而且大小很不平均。以我國(guó)的SHAPE格式為例，單幅圖存儲(chǔ)的數(shù)據(jù)量從幾百k到十幾M，對(duì)主機(jī)內(nèi)存和CPU速度有較高要求。高端的PC機(jī)很容易滿足這兩點(diǎn)，而很多基于電子海圖的嵌入式應(yīng)用，由于CPU速度有限，裝載數(shù)據(jù)的時(shí)間往往超出用戶預(yù)計(jì)的范圍；或者其內(nèi)存就不足以裝載一幅海圖。

2．單幅矢量圖的范圍大大超過(guò)了一般顯示終端的大小。我國(guó)SHAPE格式海圖分幅與紙質(zhì)海圖一致，尺寸約100cm×80cm。為顯示屏幕內(nèi)小范圍數(shù)據(jù)，而遍歷整幅海圖，造成海圖繪制時(shí)間過(guò)長(zhǎng)，效率不高。

3．矢量圖之間存在重疊現(xiàn)象。不僅浪費(fèi)了存儲(chǔ)空間，而且在查詢物標(biāo)時(shí)容易出現(xiàn)二義性。

本文提出分割矢量圖的方法解決以上問(wèn)題。通過(guò)調(diào)整分割大小，可保證所有單幅圖的數(shù)據(jù)量在一定限度之內(nèi)適應(yīng)不同主機(jī)資源約束。通過(guò)預(yù)先的分割，可以采用簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)達(dá)到較高的顯示效率。而且，對(duì)于數(shù)據(jù)的重疊部分，分割后可以剔出，保證數(shù)據(jù)的唯一性。本文以SHAPE格式海圖為研究對(duì)象，應(yīng)用計(jì)算機(jī)圖形學(xué)中多邊形布爾運(yùn)算法則處理多邊形的剪裁，不限制實(shí)體和剪裁多邊形類型，使得該方法不僅適用于等間隔經(jīng)緯網(wǎng)分割，也適用于不規(guī)則分割。

1 矢量圖組織結(jié)構(gòu)

SHAPE格式矢量圖以圖幅為單位組織，一幅圖一個(gè)目錄，其文件由一個(gè)控制文件、多個(gè)圖形文件、索引文件、屬性文件組成。從內(nèi)容上看，一幅圖主要包括圖幅元數(shù)據(jù)、物標(biāo)的幾何和屬性數(shù)據(jù)。

圖形文件記錄物標(biāo)的幾何位置數(shù)據(jù)，為可變長(zhǎng)記錄文件。索引文件記錄對(duì)應(yīng)的圖形文件，記錄相對(duì)于圖形文件開(kāi)始點(diǎn)的偏移量。屬性文件為dBase表文件結(jié)構(gòu)，記錄了物標(biāo)的屬性。圖形文件記錄與屬性文件記錄通過(guò)記錄號(hào)一一對(duì)應(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ù)存在，除類似周長(zhǎng)、面積、最小外接矩形等屬性隨之改變外，其它類似燈標(biāo)燈質(zhì)、等深區(qū)水深等描述性屬性不隨分割操作而改變。

設(shè)定分割窗口；

if（矢量圖是否與分割窗口相交）then

{以原始圖廓與分割窗口的交集作為新的圖廓邊界；

Repeat

提取物標(biāo)層的信息，如物標(biāo)種類、數(shù)量、幾何類型、最小外接矩形、屬性類型列表等；

Repeat

根據(jù)記錄號(hào)提取物標(biāo)幾何數(shù)據(jù)和屬性數(shù)據(jù)

采用不同的剪裁算法處理點(diǎn)、線、面物標(biāo)

將原物標(biāo)屬性復(fù)制到分割后的物標(biāo)，重新計(jì)算新物標(biāo)與幾何特征相關(guān)屬性信息（周長(zhǎng)、面積、長(zhǎng)度、最小外接矩形等）

Until該層所有物標(biāo)處理完畢；

重新計(jì)算該層包含的物標(biāo)數(shù)量，最小外接矩形等信息；

Until所有物標(biāo)層處理完畢；

}

分割結(jié)束；

對(duì)于點(diǎn)狀物標(biāo)，分割方法很簡(jiǎn)單，只需判斷點(diǎn)位是否位于分割窗口之內(nèi)，采取保留或放棄即可。線狀物標(biāo)的剪裁算法[1-2]也比較成熟，本文采用Reppaport A提出的線段剪裁算法。

3 多邊形剪裁

面狀物標(biāo)的處理相對(duì)復(fù)雜，特別是SHAPE格式規(guī)定的多邊形有如下幾個(gè)特點(diǎn)：

1．包含有“洞”多邊形。

2．多邊形頂點(diǎn)數(shù)目巨大。

3．頂點(diǎn)位置用浮點(diǎn)數(shù)表示。

以上特點(diǎn)分別從適用范圍、時(shí)間空間復(fù)雜度、數(shù)值魯棒性方面，對(duì)剪裁算法提出較高的要求。在分析比較文獻(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(shí)針時(shí)，沿著邊的方向，右側(cè)區(qū)域?yàn)槎噙呅蔚膬?nèi)部，左側(cè)區(qū)域?yàn)槎噙呅蔚耐獠?。反之，如果多邊形邊的方向?yàn)槟鏁r(shí)針，則左側(cè)區(qū)域?yàn)槎噙呅蔚膬?nèi)部，右側(cè)區(qū)域?yàn)槎噙呅蔚耐獠俊?/SPAN>

2）進(jìn)點(diǎn)和出點(diǎn)的定義

設(shè)I是多邊形S和C的一個(gè)交點(diǎn)。如果S沿著S的邊界方向在I點(diǎn)從C的外部進(jìn)入C的內(nèi)部，則稱I為S對(duì)于C的一個(gè)進(jìn)點(diǎn)。反之，如果S在I點(diǎn)從C的內(nèi)部出到C的外部，則稱I為S對(duì)于C的一個(gè)出點(diǎn)。進(jìn)點(diǎn)和出點(diǎn)定義是一個(gè)多邊形相對(duì)另一個(gè)同多邊形的[5]。如圖2所示，陰影部分為多邊形內(nèi)部，I為S對(duì)于C的進(jìn)點(diǎn)，是C對(duì)于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)外邊界都是順時(shí)針?lè)较颉?/SPAN>

1）確定兩多邊形內(nèi)外部輪廓之間的布爾算子。

多邊形剪裁的結(jié)果是兩個(gè)多邊形的交集。根據(jù)集合的布爾運(yùn)算法則，

（3）

以上結(jié)論可描述為：兩外部輪廓進(jìn)行交集運(yùn)算，得到交集的結(jié)果多邊形；洞與洞之間進(jìn)行并集運(yùn)算，如果結(jié)果多邊形之間還有相交，繼續(xù)并運(yùn)算；然后將洞的并集多邊形全部反向，與外部輪廓的交集多邊形再求交，得到最終結(jié)果。

對(duì)于分解后的每個(gè)布爾運(yùn)算，進(jìn)行“2）~4）”的操作：

2）求兩多邊形之間的交點(diǎn)，形成交點(diǎn)集。

3）判斷各交點(diǎn)處一個(gè)多邊形相對(duì)于另一個(gè)多邊形的出點(diǎn)、入點(diǎn)性質(zhì)。

4）從多邊形第一個(gè)交點(diǎn)出發(fā)，根據(jù)布爾算子和交點(diǎn)的進(jìn)出點(diǎn)性質(zhì)，判斷是否把跟蹤路線切換到另一個(gè)多邊形，并選擇正確的方向沿著相應(yīng)多邊形的邊繼續(xù)跟蹤。對(duì)于“交”操作，在交點(diǎn)處進(jìn)入多邊形；對(duì)于“并”操作，在交點(diǎn)處出多邊形。當(dāng)?shù)竭_(dá)下一個(gè)交點(diǎn)時(shí)，再次判斷是否切換多邊形，以及選擇正確的方向繼續(xù)跟蹤，直至又回到第一個(gè)交點(diǎn)，形成一條完整的回路[3]。如果交點(diǎn)集中仍有沒(méi)有被經(jīng)過(guò)的剩余交點(diǎn)，則繼續(xù)按照同樣的方法處理剩余的交點(diǎn)，直到所有的交點(diǎn)都被經(jīng)過(guò)。處理完畢得到的多邊形就是布爾運(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沒(méi)有未處理交點(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也沒(méi)有未處理交點(diǎn)。將B反向得（I2，，，，I4，，，）。又求得A與B的交點(diǎn)（I1，I5，I7，I3）。其中，I1、I7是A相對(duì)B的出點(diǎn)，B相對(duì)A的進(jìn)點(diǎn)；I5、I3是A相對(duì)B的進(jìn)點(diǎn)，B相對(duì)A的出點(diǎn)。從I1開(kāi)始，A∩B的一個(gè)結(jié)果多邊形為（I1，I2，I3，I0）；由于還有未處理的交點(diǎn)（I5，I7），再?gòu)?/SPAN>I1開(kāi)始，另一個(gè)結(jié)果多邊形為（I5，I6，I7，I4）。因此，A∩B得到的兩個(gè)多邊形即為S∩C的最終結(jié)果。

圖3 多邊形剪裁實(shí)例

該算法具備以不規(guī)則形狀分割矢量圖的功能，圖4是對(duì)同一幅海圖進(jìn)行星型和矩形分割的結(jié)果。從應(yīng)用角度來(lái)看，矩形分割最為廣泛。矩形大小主要考慮內(nèi)存和顯示器尺寸。以我國(guó)出版的SHAPE格式矢量電子航海圖為例，數(shù)據(jù)總量約800MByte，存在700萬(wàn)、400萬(wàn)、230萬(wàn)、100萬(wàn)、50萬(wàn)、25萬(wàn)、10萬(wàn)等比例尺級(jí)別的單幅圖對(duì)應(yīng)紙質(zhì)圖幅。對(duì)于兩種硬件條件（工業(yè)主板：64M內(nèi)存、12寸液晶屏；掌上電腦：32M程序內(nèi)存、5寸液晶屏），對(duì)相應(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á)到適時(shí)性要求。

圖4 海圖分割結(jié)果

4 結(jié)語(yǔ)

目前本文研究的算法僅限于無(wú)拓?fù)潢P(guān)系的矢量圖。對(duì)于類似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] 劉勇奎，顏葉，石教英．一個(gè)有效的多邊形窗口的線裁剪算法[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] 劉勇奎，高云，黃有群．一個(gè)有效的多邊形裁剪算法[J]．軟件學(xué)報(bào)，2003，14（4）：845-856．

[7] 劉紅軍，王從軍，黃樹(shù)槐．帶有孔洞的多邊形的布爾算法[J]．華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2003，31（8）：18-20．

[8] 董未名，瑪依拉•巴榜，周登文，等．平面擴(kuò)展簡(jiǎn)單多邊形的布爾運(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]．中國(guó)圖象圖形學(xué)報(bào)，2007，12（3）：552-557．

作者：鐘云海 鄭海 周建波  來(lái)源：中國(guó)航海