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

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

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

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

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

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

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

1 矢量圖組織結構

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

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

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

2 分割流程

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

設定分割窗口；

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

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

Repeat

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

Repeat

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

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

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

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

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

Until所有物標層處理完畢；

}

分割結束；

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

3 多邊形剪裁

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

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

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

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

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

3.1 基本概念

1）多邊形邊的方向與內外區域的關(guān)系

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

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

設I是多邊形S和C的一個(gè)交點(diǎn)。如果S沿著(zhù)S的邊界方向在I點(diǎn)從C的外部進(jìn)入C的內部，則稱(chēng)I為S對于C的一個(gè)進(jìn)點(diǎn)。反之，如果S在I點(diǎn)從C的內部出到C的外部，則稱(chēng)I為S對于C的一個(gè)出點(diǎn)。進(jìn)點(diǎn)和出點(diǎn)定義是一個(gè)多邊形相對另一個(gè)同多邊形的[5]。如圖2所示，陰影部分為多邊形內部，I為S對于C的進(jìn)點(diǎn)，是C對于S的出點(diǎn)。

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

3.2 布爾運算和實(shí)例

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

（1）

（2）

式（1）和式（2）中：S0、C0分別為兩多邊形的外部輪廓，S1…n、C1…n分別為兩多邊形的“洞”。在這里，多邊形的內外邊界都是順時(shí)針?lè )较颉?/SPAN>

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

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

（3）

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

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

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

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

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

如圖3所示，S0與C0交點(diǎn)為（I0，I6）。根據進(jìn)出點(diǎn)的定義，I0是S0到C0的進(jìn)點(diǎn)、I6是S0到C0的出點(diǎn)。S0∩C0的結果多邊形為（I0，，I6，），設為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的結果多邊形為（I2，，，，I4，，，），設為B。S1與C1也沒(méi)有未處理交點(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開(kāi)始，A∩B的一個(gè)結果多邊形為（I1，I2，I3，I0）；由于還有未處理的交點(diǎn)（I5，I7），再從I1開(kāi)始，另一個(gè)結果多邊形為（I5，I6，I7，I4）。因此，A∩B得到的兩個(gè)多邊形即為S∩C的最終結果。

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

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

圖4 海圖分割結果

4 結語(yǔ)

目前本文研究的算法僅限于無(wú)拓撲關(guān)系的矢量圖。對于類(lèi)似S57等有拓撲的矢量圖，還需考慮分割后拓撲關(guān)系的重建。

參考文獻

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

[2] 劉勇奎，顏葉，石教英．一個(gè)有效的多邊形窗口的線(xiàn)裁剪算法[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] 劉勇奎，高云，黃有群．一個(gè)有效的多邊形裁剪算法[J]．軟件學(xué)報，2003，14（4）：845-856．

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

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

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

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

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