歡迎光臨南京遠(yuǎn)洋運(yùn)輸股份有限公司官網(wǎng)!
搜索 企業(yè)郵箱 公司OA 請(qǐng)選擇語言版本: En
求新 務(wù)實(shí) 立信 望遠(yuǎn)
知識(shí)庫
當(dāng)前位置:首頁 > 學(xué)習(xí)園地 > 知識(shí)庫 > 經(jīng)驗(yàn)交流 > 瀏覽文章

經(jīng)驗(yàn)交流

矢量電子航海圖的分割方法研究
時(shí)間:2009年08月05日   作者:佚名  點(diǎn)擊次數(shù): 【字體:

摘要:為解決嵌入式系統(tǒng)應(yīng)用電子航海圖出現(xiàn)的單幅圖存儲(chǔ)量、圖廓范圍過大,以及圖幅重疊等問題,以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)算

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

1.單幅矢量圖的存儲(chǔ)數(shù)據(jù)量大,而且大小很不平均。以我國的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.單幅矢量圖的范圍大大超過了一般顯示終端的大小。我國SHAPE格式海圖分幅與紙質(zhì)海圖一致,尺寸約100cm×80cm。為顯示屏幕內(nèi)小范圍數(shù)據(jù),而遍歷整幅海圖,造成海圖繪制時(shí)間過長,效率不高。

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

本文提出分割矢量圖的方法解決以上問題。通過調(diào)整分割大小,可保證所有單幅圖的數(shù)據(jù)量在一定限度之內(nèi)適應(yīng)不同主機(jī)資源約束。通過預(yù)先的分割,可以采用簡單的數(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ù),為可變長記錄文件。索引文件記錄對(duì)應(yīng)的圖形文件,記錄相對(duì)于圖形文件開始點(diǎn)的偏移量。屬性文件為dBase表文件結(jié)構(gòu),記錄了物標(biāo)的屬性。圖形文件記錄與屬性文件記錄通過記錄號(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ù)存在,除類似周長、面積、最小外接矩形等屬性隨之改變外,其它類似燈標(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)屬性信息(周長、面積、長度、最小外接矩形等)

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

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

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

}

分割結(jié)束;

對(duì)于點(diǎn)狀物標(biāo),分割方法很簡單,只需判斷點(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是多邊形SC的一個(gè)交點(diǎn)。如果S沿著S的邊界方向在I點(diǎn)從C的外部進(jìn)入C的內(nèi)部,則稱IS對(duì)于C的一個(gè)進(jìn)點(diǎn)。反之,如果SI點(diǎn)從C的內(nèi)部出到C的外部,則稱IS對(duì)于C的一個(gè)出點(diǎn)。進(jìn)點(diǎn)和出點(diǎn)定義是一個(gè)多邊形相對(duì)另一個(gè)同多邊形的[5]。如圖2所示,陰影部分為多邊形內(nèi)部,IS對(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分別為兩多邊形的外部輪廓,S1n、C1n分別為兩多邊形的“洞”。在這里,多邊形的內(nèi)外邊界都是順時(shí)針方向。

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)集中仍有沒有被經(jīng)過的剩余交點(diǎn),則繼續(xù)按照同樣的方法處理剩余的交點(diǎn),直到所有的交點(diǎn)都被經(jīng)過。處理完畢得到的多邊形就是布爾運(yùn)算的結(jié)果。

如圖3所示,S0C0交點(diǎn)為(I0,I6)。根據(jù)進(jìn)出點(diǎn)的定義,I0S0C0的進(jìn)點(diǎn)、I6S0C0的出點(diǎn)。S0C0的結(jié)果多邊形為(I0,矢量電子航海圖的分割方法研究,I6,矢量電子航海圖的分割方法研究),設(shè)為A。S0C0沒有未處理交點(diǎn)。再看S1C1交點(diǎn)為(I2I4),I2S1C1的進(jìn)點(diǎn)、I4S1C1的出點(diǎn)。S1C1的結(jié)果多邊形為(I2矢量電子航海圖的分割方法研究,矢量電子航海圖的分割方法研究,矢量電子航海圖的分割方法研究,I4矢量電子航海圖的分割方法研究,矢量電子航海圖的分割方法研究矢量電子航海圖的分割方法研究),設(shè)為B。S1C1也沒有未處理交點(diǎn)。將B反向得(I2矢量電子航海圖的分割方法研究,矢量電子航海圖的分割方法研究,矢量電子航海圖的分割方法研究,I4,矢量電子航海圖的分割方法研究,矢量電子航海圖的分割方法研究矢量電子航海圖的分割方法研究)。又求得AB的交點(diǎn)(I1,I5,I7I3)。其中,I1、I7A相對(duì)B的出點(diǎn),B相對(duì)A的進(jìn)點(diǎn);I5I3A相對(duì)B的進(jìn)點(diǎn),B相對(duì)A的出點(diǎn)。從I1開始,A∩B的一個(gè)結(jié)果多邊形為(I1,I2I3,I0);由于還有未處理的交點(diǎn)(I5,I7),再從I1開始,另一個(gè)結(jié)果多邊形為(I5,I6,I7I4)。因此,AB得到的兩個(gè)多邊形即為SC的最終結(jié)果。

矢量電子航海圖的分割方法研究

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

該算法具備以不規(guī)則形狀分割矢量圖的功能,圖4是對(duì)同一幅海圖進(jìn)行星型和矩形分割的結(jié)果。從應(yīng)用角度來看,矩形分割最為廣泛。矩形大小主要考慮內(nèi)存和顯示器尺寸。以我國出版的SHAPE格式矢量電子航海圖為例,數(shù)據(jù)總量約800MByte,存在700萬、400萬、230萬、100萬、50萬、25萬、10萬等比例尺級(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é)語

目前本文研究的算法僅限于無拓?fù)潢P(guān)系的矢量圖。對(duì)于類似S57等有拓?fù)涞氖噶繄D,還需考慮分割后拓?fù)潢P(guān)系的重建。

參考文獻(xiàn)

[1] Reppaport AAn efficient algorithm for line and polygon clipping[J]Visual Computer,19917119-28

[2] 劉勇奎,顏葉,石教英.一個(gè)有效的多邊形窗口的線裁剪算法[J].計(jì)算機(jī)學(xué)報(bào),1999,2211):1209-1214

[3] Vatti B RA generic solution to polygon clipping[J]Communications of the ACM,199235156-63

[4] Greiner G,Hormann KEfficient clipping of arbitrary polygons[J]ACM Transactions on Graphics1998,17271-83

[5] Rivero M LFeito F RBoolean operations on general planar polygons[J]Computer &Graphics,2000246881-896

[6] 劉勇奎,高云,黃有群.一個(gè)有效的多邊形裁剪算法[J].軟件學(xué)報(bào),2003144):845-856

[7] 劉紅軍,王從軍,黃樹槐.帶有孔洞的多邊形的布爾算法[J].華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版),200331818-20

[8] 董未名,瑪依拉•巴榜,周登文,等.平面擴(kuò)展簡單多邊形的布爾運(yùn)算[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2003,159):1134-1140

[9] 謝步瀛,張巖.用分段法與鏈表法的二維布爾運(yùn)算[J].工程圖學(xué)學(xué)報(bào),2003242):78-84

[10] 姚輝學(xué),盧章平.海量數(shù)據(jù)多邊形布爾運(yùn)算的區(qū)域分割算法[J].中國圖象圖形學(xué)報(bào),2007,123):552-557

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

關(guān)于我們

南京遠(yuǎn)洋運(yùn)輸股份有限公司是一個(gè)專門經(jīng)營干散貨船舶運(yùn)輸?shù)膶I(yè)船東公司,成立于1988年,原名南京遠(yuǎn)洋運(yùn)輸公 司,1994年進(jìn) 行了股份制改 造,更為現(xiàn)名。

業(yè)務(wù)領(lǐng)域

南京遠(yuǎn)洋擁有船舶資產(chǎn),是以經(jīng)營遠(yuǎn)洋貨物運(yùn)輸為主、又集國際船舶管理、國際船舶代理、海員勞務(wù)輸出、船舶物 料供應(yīng)和投資 咨詢服務(wù)為一體的綜合性遠(yuǎn)洋運(yùn)輸企業(yè)。

加入我們

我們堅(jiān)信:人才是發(fā)展之本!
我們依據(jù)各崗位職責(zé)的不同,參考當(dāng)前市場(chǎng)實(shí)際,為廣大員工提供富有競爭力的薪資福利。

聯(lián)系我們

公司地址:南京市江東中路311號(hào)中泰國際廣場(chǎng)05幢18 樓 郵政編碼:210019
電話:025-58802148 87792001
傳真:025-58802147
微信公眾號(hào)

微信掃一掃關(guān)注我們