摘要：為解決嵌入式系統應用電子航海圖出現的單幅圖存儲量、圖廓范圍過大，以及圖幅重疊等問題，以SHAPE格式圖為例，設計并實現了矢量電子航海圖的分割方法。采用多邊形布爾運算法則處理多邊形的剪裁，不限制實體和剪裁多邊形類型，使得該分割方法不僅適用于等經緯網格分割，也適用于不規則分割。應用該分割方法對海圖數據進行預處理，可以適應硬件資源有限的嵌入式應用，從而提高系統設計的自由度、降低總體成本，促進電子海圖系統的推廣。

關鍵詞：水路運輸；電子航海圖；嵌入式系統；多邊形剪裁；布爾運算

矢量電子航海圖（以下簡稱矢量圖）是目前國內外電子海圖應用系統主流的數據類型，具體格式包括SHAPE、S57、MAPINFO等。在嵌入式系統上開發矢量圖的應用程序，將不可避免地面臨以下問題：

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

2．單幅矢量圖的范圍大大超過了一般顯示終端的大小。我國SHAPE格式海圖分幅與紙質海圖一致，尺寸約100cm×80cm。為顯示屏幕內小范圍數據，而遍歷整幅海圖，造成海圖繪制時間過長，效率不高。

3．矢量圖之間存在重疊現象。不僅浪費了存儲空間，而且在查詢物標時容易出現二義性。

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

1 矢量圖組織結構

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

圖形文件記錄物標的幾何位置數據，為可變長記錄文件。索引文件記錄對應的圖形文件，記錄相對于圖形文件開始點的偏移量。屬性文件為dBase表文件結構，記錄了物標的屬性。圖形文件記錄與屬性文件記錄通過記錄號一一對應?？刂莆募饕ǎ簣D幅名稱、比例尺、圖廓邊界、投影方式等海圖元數據。

圖1 SHAPE格式圖組織結構示意

2 分割流程

分割不僅包括幾何數據的剪裁，也包括元數據、屬性數據的重新賦值。分割后生成的新圖必須符合原有標準。受分割操作影響的元數據主要是圖廓邊界，屬性數據依賴于幾何數據存在，除類似周長、面積、最小外接矩形等屬性隨之改變外，其它類似燈標燈質、等深區水深等描述性屬性不隨分割操作而改變。

設定分割窗口；

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

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

Repeat

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

Repeat

根據記錄號提取物標幾何數據和屬性數據

采用不同的剪裁算法處理點、線、面物標

將原物標屬性復制到分割后的物標，重新計算新物標與幾何特征相關屬性信息（周長、面積、長度、最小外接矩形等）

Until該層所有物標處理完畢；

重新計算該層包含的物標數量，最小外接矩形等信息；

Until所有物標層處理完畢；

}

分割結束；

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

3 多邊形剪裁

面狀物標的處理相對復雜，特別是SHAPE格式規定的多邊形有如下幾個特點：

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

2．多邊形頂點數目巨大。

3．頂點位置用浮點數表示。

以上特點分別從適用范圍、時間空間復雜度、數值魯棒性方面，對剪裁算法提出較高的要求。在分析比較文獻[3-10]的基礎上，本文依據Vatti B.R.算法[3]，采用布爾運算法則剪裁SHAPE圖中的復雜多邊形，取得較好效果。為了便于描述，首先引入多邊形裁剪的一些基本概念。

3.1 基本概念

1）多邊形邊的方向與內外區域的關系

當多邊形邊的方向為順時針時，沿著邊的方向，右側區域為多邊形的內部，左側區域為多邊形的外部。反之，如果多邊形邊的方向為逆時針，則左側區域為多邊形的內部，右側區域為多邊形的外部。

2）進點和出點的定義

設I是多邊形S和C的一個交點。如果S沿著S的邊界方向在I點從C的外部進入C的內部，則稱I為S對于C的一個進點。反之，如果S在I點從C的內部出到C的外部，則稱I為S對于C的一個出點。進點和出點定義是一個多邊形相對另一個同多邊形的[5]。如圖2所示，陰影部分為多邊形內部，I為S對于C的進點，是C對于S的出點。

圖2 進點和出點的定義

3.2 布爾運算和實例

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

（1）

（2）

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

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

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

（3）

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

對于分解后的每個布爾運算，進行“2）~4）”的操作：

2）求兩多邊形之間的交點，形成交點集。

3）判斷各交點處一個多邊形相對于另一個多邊形的出點、入點性質。

4）從多邊形第一個交點出發，根據布爾算子和交點的進出點性質，判斷是否把跟蹤路線切換到另一個多邊形，并選擇正確的方向沿著相應多邊形的邊繼續跟蹤。對于“交”操作，在交點處進入多邊形；對于“并”操作，在交點處出多邊形。當到達下一個交點時，再次判斷是否切換多邊形，以及選擇正確的方向繼續跟蹤，直至又回到第一個交點，形成一條完整的回路[3]。如果交點集中仍有沒有被經過的剩余交點，則繼續按照同樣的方法處理剩余的交點，直到所有的交點都被經過。處理完畢得到的多邊形就是布爾運算的結果。

如圖3所示，S0與C0交點為（I0，I6）。根據進出點的定義，I0是S0到C0的進點、I6是S0到C0的出點。S0∩C0的結果多邊形為（I0，，I6，），設為A。S0與C0沒有未處理交點。再看S1與C1交點為（I2，I4），I2是S1到C1的進點、I4是S1到C1的出點。S1∪C1的結果多邊形為（I2，，，，I4，，，），設為B。S1與C1也沒有未處理交點。將B反向得（I2，，，，I4，，，）。又求得A與B的交點（I1，I5，I7，I3）。其中，I1、I7是A相對B的出點，B相對A的進點；I5、I3是A相對B的進點，B相對A的出點。從I1開始，A∩B的一個結果多邊形為（I1，I2，I3，I0）；由于還有未處理的交點（I5，I7），再從I1開始，另一個結果多邊形為（I5，I6，I7，I4）。因此，A∩B得到的兩個多邊形即為S∩C的最終結果。

圖3 多邊形剪裁實例

該算法具備以不規則形狀分割矢量圖的功能，圖4是對同一幅海圖進行星型和矩形分割的結果。從應用角度來看，矩形分割最為廣泛。矩形大小主要考慮內存和顯示器尺寸。以我國出版的SHAPE格式矢量電子航海圖為例，數據總量約800MByte，存在700萬、400萬、230萬、100萬、50萬、25萬、10萬等比例尺級別的單幅圖對應紙質圖幅。對于兩種硬件條件（工業主板：64M內存、12寸液晶屏；掌上電腦：32M程序內存、5寸液晶屏），對相應比例尺圖采用30°、20°、10°、5°、2°、1°和20°、10°、5°、2°、1°、30′經緯度方格兩種方案進行分割。兩種方案分割后的矢量圖，在相應的硬件環境下均滿足內存約束，且顯示速度達到適時性要求。

圖4 海圖分割結果

4 結語

目前本文研究的算法僅限于無拓撲關系的矢量圖。對于類似S57等有拓撲的矢量圖，還需考慮分割后拓撲關系的重建。

參考文獻

[1] Reppaport A．An efficient algorithm for line and polygon clipping[J]．Visual Computer，1991，7（1）：19-28

[2] 劉勇奎，顏葉，石教英．一個有效的多邊形窗口的線裁剪算法[J]．計算機學報，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]．軟件學報，2003，14（4）：845-856．

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

[8] 董未名，瑪依拉•巴榜，周登文，等．平面擴展簡單多邊形的布爾運算[J]．計算機輔助設計與圖形學學報，2003，15（9）：1134-1140．

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

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

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