多邊形圖形矢柵混合模型的改進(jìn)及編碼方法*

邱 國 清

(閩南師范大學(xué) 計(jì)算機(jī)學(xué)院， 福建 漳州 363000)

矢柵混合模型和矢柵一體化模型是數(shù)據(jù)模型研究的兩個(gè)部分。其中，矢柵混合模型是將矢量結(jié)構(gòu)和柵格結(jié)構(gòu)的數(shù)據(jù)不加任何處理分別存儲在同一個(gè)空間數(shù)據(jù)庫中，當(dāng)需要使用時(shí)只需將兩種數(shù)據(jù)分別調(diào)入，這樣就可以極大地提高地圖編輯對象的信息量和準(zhǔn)確性，矢柵混合模型已經(jīng)在GIS和制圖中得到了廣泛的應(yīng)用，但該模型數(shù)據(jù)重復(fù)存儲占用了大量的存儲空間[1]，為了彌補(bǔ)該缺點(diǎn)，提出了將存儲空間中的矢量數(shù)據(jù)和柵格數(shù)據(jù)進(jìn)行編碼處理，同時(shí)對這兩種編碼進(jìn)行壓縮，以達(dá)到減少存儲空間和提高效率的目的。

圖1:復(fù)雜多邊形圖形

1 矢量數(shù)據(jù)編碼及壓縮方式

矢量數(shù)據(jù)結(jié)構(gòu)是通過記錄坐標(biāo)的方式，盡可能精確地表示點(diǎn)線多邊形等地理實(shí)體[2]，該數(shù)據(jù)結(jié)構(gòu)精度高，易于空間信息的可視化表達(dá)[3]。矢量數(shù)據(jù)的編碼及壓縮比較簡單而且方法有多種。

2 柵格數(shù)據(jù)的編碼

柵格數(shù)據(jù)結(jié)構(gòu)又稱為網(wǎng)格數(shù)據(jù)結(jié)構(gòu)，每個(gè)小方格用(x,y)坐標(biāo)表示，其最明顯的特點(diǎn)就是屬性明確，定位隱含[4]。

2.1 四叉樹原理

四叉樹編碼方式是柵格數(shù)據(jù)編碼最常用的方法之一，該編碼方式將圖形分為四個(gè)部分，逐塊檢查其格網(wǎng)屬性值，但該編碼方式最大缺點(diǎn)在于轉(zhuǎn)換的不定性，同一個(gè)圖形可能會有多種不同的四叉樹，這樣就不利于形狀分析和模式識別，為此還需要將四叉樹轉(zhuǎn)換成二叉樹，這樣就能保證只得出一棵對應(yīng)的編碼樹。

2.2 四叉樹轉(zhuǎn)換成二叉樹

利用霍夫曼原理[5]將四叉樹轉(zhuǎn)換成二叉樹，該基本原理是按照字符出現(xiàn)概率的大小，概率大的字符分配短碼，概率小的字符分配長碼來構(gòu)造最短的平均碼長，以圖1為例，假設(shè)點(diǎn)1、2、3的屬性值為1，點(diǎn)4、5、6、7的屬性值2，點(diǎn)8、9、10、11的屬性值為3，點(diǎn)12的屬性值為4，該圖形編碼中每個(gè)像素元的屬性值出現(xiàn)的概率大小計(jì)算如表1所示。

表1:概率表

用霍夫曼編碼方法，對屬性值進(jìn)行編碼，其編碼過程如表2所示。

表2:編碼過程

2.3 霍夫曼編碼樹

表2的編碼過程可用圖2的編碼樹來表示。

圖2:霍夫曼編碼樹

3 Morton碼的原理

Morton碼的計(jì)算如下[6]：

圖3:Morton碼

圖4:Morton碼的計(jì)算過程

這樣就可以行列表示二維柵格陣列圖形，用Morton碼寫成二維數(shù)組，通過Morton碼來確定節(jié)點(diǎn)的坐標(biāo)。

圖5:復(fù)雜多邊形轉(zhuǎn)化后的編碼

4 矢柵數(shù)據(jù)轉(zhuǎn)化后的存儲編碼

對于矢量數(shù)據(jù)結(jié)構(gòu)才采用元子空間填充來表達(dá)。圖1是復(fù)雜多邊形的原始矢量數(shù)據(jù)結(jié)構(gòu)，采用元子空間填充后，轉(zhuǎn)化成圖5復(fù)雜多邊形的十進(jìn)制四叉樹。

柵格數(shù)據(jù)結(jié)構(gòu)本身就可以直接采用十進(jìn)制四叉數(shù)編碼方式存儲，假設(shè)圖1中點(diǎn)1、2、3、4、5、6、7的屬性值為，點(diǎn)8、9、10、11、12的屬性值為2，其它都為0，那么多邊形圖形的柵格結(jié)構(gòu)為圖6所示，

圖6:多邊形圖形柵格數(shù)據(jù)結(jié)構(gòu)

通過圖5和圖6可以看出，將矢量數(shù)據(jù)結(jié)構(gòu)采用元子填充后，矢量數(shù)據(jù)和柵格數(shù)據(jù)都可以采用十進(jìn)制四叉樹編碼，從而保證了編碼的一致性。

5 總結(jié)

矢柵混合模型中的矢量數(shù)據(jù)和柵格數(shù)據(jù)轉(zhuǎn)換同樣的編碼，對于重復(fù)的數(shù)據(jù)不需要在同一個(gè)數(shù)據(jù)庫中反復(fù)存儲，節(jié)省了存儲空間，混合模型中數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換成同一個(gè)格式，這樣在數(shù)據(jù)處理更加方便，提高了編碼的效率。

〔參考文獻(xiàn)〕

[1]閆浩文，等. 計(jì)算機(jī)地圖制圖原理與算法基礎(chǔ)[M].北京：科學(xué)出版社,2007：108-109.

[2]何嘉珈. 矢柵數(shù)據(jù)一體化存儲技術(shù)研究[J].科技資訊，2009，(26)：233.

[3]王昌、滕艷輝. 矢量柵格一體化數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)與應(yīng)用[J]. 計(jì)算機(jī)工程，2010，20(36)：88-89.

[4]王建、杜道生. 矢量數(shù)據(jù)向柵格數(shù)據(jù)轉(zhuǎn)換的一種改進(jìn)算法[J].地理與地理信息科學(xué)，2004，20(1)：31-34.

[5]付先平. 多媒體技術(shù)及應(yīng)用[M]. 北京：清華大學(xué)出版社，2007：53-55.

[6]艾自興，龍毅. 計(jì)算機(jī)地圖制圖[M].武漢：武漢大學(xué)出版社,2005:37-45.