邱國(guó)清

(漳州師范學(xué)院 計(jì)算機(jī)科學(xué)與工程系， 福建 漳州 363000)

0 引言

鏈?zhǔn)骄幋a主要是記錄線(xiàn)狀地物和面狀地物的邊界，它把邊界表示為：由某一點(diǎn)出發(fā)并按某些基本方向確定的單位矢量鏈 ?；臼噶糠较蚩捎?～7整數(shù)表示，該編碼對(duì)探測(cè)邊界急彎和凹進(jìn)部分都很容易，比較適合存儲(chǔ)圖形數(shù)據(jù)，但該編碼也存在一個(gè)缺點(diǎn)，它對(duì)于疊置運(yùn)算無(wú)法實(shí)現(xiàn)，對(duì)局部修改會(huì)改變整體結(jié)構(gòu)，鏈?zhǔn)骄幋a是由若干基本矢量方向組成的鏈，這些矢量方向不可以用來(lái)運(yùn)算，必須將這些矢量方向轉(zhuǎn)換成可以用來(lái)運(yùn)算的編碼。本文采用二叉樹(shù)原理、Morton碼和霍夫曼原理，利用拓?fù)浣Y(jié)構(gòu)將鏈?zhǔn)骄幋a的單位矢量方向轉(zhuǎn)換成編碼。

1 結(jié)點(diǎn)的編碼和搜索

拓?fù)浣Y(jié)構(gòu)可以描述地圖特征的三個(gè)空間關(guān)系：區(qū)域定義、連通性和鄰接性。多邊形由一條或多條弧段圍成的區(qū)域來(lái)定義?；《捂?zhǔn)孜蚕噙B，自行封閉。在數(shù)字化過(guò)程中，對(duì)結(jié)點(diǎn)坐標(biāo)進(jìn)行匹配，使得連通的弧段結(jié)點(diǎn)都具有相同坐標(biāo)的特性，并在此基礎(chǔ)上對(duì)弧段結(jié)點(diǎn)按照數(shù)值大小進(jìn)行排序。

多邊形的搜索方法有很多，其中左轉(zhuǎn)算法具有計(jì)算簡(jiǎn)單、循環(huán)次數(shù)少、容易實(shí)現(xiàn)等特點(diǎn)：

1)以起點(diǎn)弧段L的尾結(jié)點(diǎn)N為起點(diǎn)搜索點(diǎn)，通過(guò)結(jié)點(diǎn)的弧段記錄表，讀出與該結(jié)點(diǎn)相連的所有弧段的標(biāo)識(shí)碼L[i]；

2)分別計(jì)算弧段L[i]與X軸正向的夾角a[i],0≤a[i]≤2π .計(jì)算夾角時(shí)，以結(jié)點(diǎn)N和L[i]上與該結(jié)點(diǎn)最近的拐點(diǎn)所連的直線(xiàn)代表L[i] 來(lái)計(jì)算夾角。

3)若L對(duì)應(yīng)的夾角a為a[i] 中的最小角，則a[i]中的最大角amax所對(duì)應(yīng)的弧L[i] 為搜索的后續(xù)弧段L*；否則，計(jì)算△a[i]=a-a[i] ，取最小正 △a[i]所對(duì)應(yīng)的弧L[k]為后續(xù)弧段L*.

4)以L*的尾端為起點(diǎn)，重復(fù)(1)～(3)，直到L*=L.

2 多邊形的搜索

當(dāng)弧段關(guān)系確定后，算法初始輸入的離散弧段已經(jīng)通過(guò)起始和終止結(jié)點(diǎn)坐標(biāo)匹配為對(duì)應(yīng)的邏輯結(jié)點(diǎn)，通過(guò)此邏輯結(jié)點(diǎn)和弧段組成的“邏輯網(wǎng)絡(luò)”就可以進(jìn)行多邊形搜索。

3 多余多邊形的處理

為了避免在矢量化過(guò)程中生成重復(fù)多余的多邊形，應(yīng)在將要生成一個(gè)多邊形之前，通過(guò)索引機(jī)制快速地檢查是否已經(jīng)存在與之相同的多邊形：首先由將生成多邊形最小外接矩形的中心行列號(hào)確定該中心所在的網(wǎng)格，然后把將生成多邊形的最小外接矩形與網(wǎng)格中所有多邊形的最小外接矩形進(jìn)行比較，如果某一個(gè)多邊形的最小外接矩形與將生成多邊形的最小外接矩形相同，則將生成多邊形為多余多邊形，應(yīng)不予生成[2]。

4 鏈?zhǔn)骄幋a原理

鏈?zhǔn)骄幋a的前兩個(gè)數(shù)字表示起點(diǎn)的行、列數(shù)，從第三個(gè)數(shù)字開(kāi)始的每個(gè)數(shù)字表示單位矢量的方向，8個(gè)方向以0～7整數(shù)表示。

圖1 鏈?zhǔn)骄幋a圖

在圖1中，包含兩個(gè)多邊形，共用一條邊(該邊包含6、7、8、9、10、11共5個(gè)點(diǎn))。根據(jù)統(tǒng)計(jì)，方向?yàn)?的有4、9、13共3個(gè)點(diǎn)；方向?yàn)?的有5、16共2個(gè)點(diǎn)；方向?yàn)?的有6、8、10、14、17共5個(gè)點(diǎn)；方向?yàn)?的有7、15共2個(gè)點(diǎn)；方向?yàn)?的有11、18共2個(gè)點(diǎn)；方向?yàn)?的有12共1個(gè)點(diǎn)；方向?yàn)?的有1共1個(gè)點(diǎn)；方向?yàn)?的有2、6共2個(gè)點(diǎn)。

5 鏈?zhǔn)骄幋a轉(zhuǎn)換成二叉樹(shù)

霍夫曼編碼的基本思想[3]是按照字符出現(xiàn)概率的大小，概率大的字符分配短碼，概率小的字符分配長(zhǎng)碼來(lái)構(gòu)造最短的平均碼長(zhǎng)，以圖一為例，該圖形編碼中每個(gè)方向出現(xiàn)的概率大小計(jì)算如表1所示。

表1 概率表

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

表2 編碼過(guò)程

表2的編碼過(guò)程可用圖2的編碼樹(shù)來(lái)表示。

圖2 霍夫曼編碼樹(shù)

通過(guò)霍夫曼編碼樹(shù)，可以將鏈?zhǔn)骄幋a的方向矢量轉(zhuǎn)換為可用來(lái)運(yùn)算的編碼。

6 總結(jié)

根據(jù)霍夫曼編碼和二叉樹(shù)的原理將鏈?zhǔn)骄幋a中的方向矢量轉(zhuǎn)換為可以運(yùn)算的編碼，由于鏈?zhǔn)骄幋a方式中的每個(gè)節(jié)點(diǎn)是依據(jù)行、列以及單位矢量的方向表示，所以當(dāng)鏈?zhǔn)骄幋a被轉(zhuǎn)換成霍夫曼編碼樹(shù)時(shí)，每個(gè)節(jié)點(diǎn)都由唯一的霍夫曼編碼表示，從而克服鏈?zhǔn)骄幋a方式對(duì)于疊置運(yùn)算無(wú)法實(shí)現(xiàn)以及相鄰區(qū)域的邊界被重復(fù)存儲(chǔ)而產(chǎn)生冗余。

參考文獻(xiàn):

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

[2]扶卿華,倪紹祥,郭 劍. 柵格數(shù)據(jù)矢量化及其存在問(wèn)題的解決[J].現(xiàn)代測(cè)繪,2004,27(3):8～11.

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

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