摘要：為解決嵌入式系統(tǒng)應(yīng)用電子航海圖出現(xiàn)的單幅圖存儲量、圖廓范圍過大，以及圖幅重疊等問題，以SHAPE格式圖為例，設(shè)計并實現(xià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)鍵詞：水路運輸；電子航海圖；嵌入式系統(tǒng)；多邊形剪裁；布爾運算

矢量電子航海圖（以下簡稱矢量圖）是目前國內(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)象。不僅浪費了存儲空間，而且在查詢物標(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é)中多邊形布爾運算法則處理多邊形的剪裁，不限制實體和剪裁多邊形類型，使得該方法不僅適用于等間隔經(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]，采用布爾運算法則剪裁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 布爾運算和實例

下面介紹采用布爾運算法則處理矢量圖中有“洞”多邊形的基本思路。不失一般性，設(shè)實體多邊形S和剪裁多邊形C都為有洞多邊形，采用集合表示方法

（1）

（2）

式（1）和式（2）中：S0、C0分別為兩多邊形的外部輪廓，S1…n、C1…n分別為兩多邊形的“洞”。在這里，多邊形的內(nèi)外邊界都是順時針方向。

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

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

（3）

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

對于分解后的每個布爾運算，進(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)過。處理完畢得到的多邊形就是布爾運算的結(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ò)展簡單多邊形的布爾運算[J]．計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報，2003，15（9）：1134-1140．

[9] 謝步瀛，張巖．用分段法與鏈表法的二維布爾運算[J]．工程圖學(xué)學(xué)報，2003，24（2）：78-84．

[10] 姚輝學(xué)，盧章平．海量數(shù)據(jù)多邊形布爾運算的區(qū)域分割算法[J]．中國圖象圖形學(xué)報，2007，12（3）：552-557．

作者：鐘云海 鄭海 周建波  來源：中國航海