多邊形鏈式編碼方式的改進及其編碼方法

邱國清

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

0 引言

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

1 結點的編碼和搜索

拓撲結構可以描述地圖特征的三個空間關系：區(qū)域定義、連通性和鄰接性。多邊形由一條或多條弧段圍成的區(qū)域來定義?；《捂準孜蚕噙B，自行封閉。在數(shù)字化過程中，對結點坐標進行匹配，使得連通的弧段結點都具有相同坐標的特性，并在此基礎上對弧段結點按照數(shù)值大小進行排序。

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

1)以起點弧段L的尾結點N為起點搜索點，通過結點的弧段記錄表，讀出與該結點相連的所有弧段的標識碼L[i]；

2)分別計算弧段L[i]與X軸正向的夾角a[i],0≤a[i]≤2π .計算夾角時，以結點N和L[i]上與該結點最近的拐點所連的直線代表L[i] 來計算夾角。

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

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

2 多邊形的搜索

當弧段關系確定后，算法初始輸入的離散弧段已經通過起始和終止結點坐標匹配為對應的邏輯結點，通過此邏輯結點和弧段組成的“邏輯網絡”就可以進行多邊形搜索。

3 多余多邊形的處理

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

4 鏈式編碼原理

鏈式編碼的前兩個數(shù)字表示起點的行、列數(shù)，從第三個數(shù)字開始的每個數(shù)字表示單位矢量的方向，8個方向以0～7整數(shù)表示。

圖1 鏈式編碼圖

在圖1中，包含兩個多邊形，共用一條邊(該邊包含6、7、8、9、10、11共5個點)。根據統(tǒng)計，方向為0的有4、9、13共3個點；方向為1的有5、16共2個點；方向為2的有6、8、10、14、17共5個點；方向為3的有7、15共2個點；方向為4的有11、18共2個點；方向為5的有12共1個點；方向為6的有1共1個點；方向為7的有2、6共2個點。

5 鏈式編碼轉換成二叉樹

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

表1 概率表

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

表2 編碼過程

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

圖2 霍夫曼編碼樹

通過霍夫曼編碼樹，可以將鏈式編碼的方向矢量轉換為可用來運算的編碼。

6 總結

根據霍夫曼編碼和二叉樹的原理將鏈式編碼中的方向矢量轉換為可以運算的編碼，由于鏈式編碼方式中的每個節(jié)點是依據行、列以及單位矢量的方向表示，所以當鏈式編碼被轉換成霍夫曼編碼樹時，每個節(jié)點都由唯一的霍夫曼編碼表示，從而克服鏈式編碼方式對于疊置運算無法實現(xiàn)以及相鄰區(qū)域的邊界被重復存儲而產生冗余。

參考文獻:

[1]閆浩文.計算機地圖制圖原理與算法基礎[M].北京：科學出版社,2007.

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

[3]付先平. 多媒體技術及應用[M]. 北京：清華大學出版社，2007.

[4]艾自興,龍 毅.計算機地圖制圖[M].武漢:武漢大學出版社,2005.