【文章內(nèi)容簡介】 1 5 1 9 5 0 0 1 1 0 0 1 1 0 0 4 1 3 0 0 0 1 0 0 0 1 0 0 0 3 6 6 0 0 1 0 0 0 0 1 0 0 2 2 0 0 1 0 0 0 0 0 0 0 1 十進(jìn)制碼 二進(jìn)制碼 葉結(jié)點(diǎn)號(hào) （ 2）基于四進(jìn)制的線性四叉樹編碼 對(duì)每個(gè)柵格進(jìn)行編碼得表 a。檢查相鄰 4個(gè) m碼的屬性值，如相同進(jìn)行合并，除去最低值。經(jīng)過一次檢測(cè)后，再檢測(cè)上層相鄰四個(gè)塊編碼的屬性值，如相同再合并。循環(huán)到?jīng)]有能合并的子塊為止，得表 b。 首先將柵格陣列的行列值分別轉(zhuǎn)換成二進(jìn)制碼，得二進(jìn)制行號(hào) Ib ,列號(hào) Jb，然后求出四進(jìn)制四叉樹碼 MQ=2* Ib + Jb 2）線性四叉樹及編碼 333 332 323 322 233 232 223 222 111 331 330 321 320 231 230 221 220 110 313 312 303 302 213 212 203 202 101 311 310 301 300 211 210 201 200 100 133 132 123 122 033 032 023 022 011 131 130 121 120 031 030 021 020 010 113 112 103 102 013 012 003 002 001 111 110 101 100 011 010 001 000 000 111 110 101 100 011 010 001 000 列號(hào) 行號(hào) 表 a 33 32 23 22 303 302 31 301 300 21 20 033 032 031 030 02 1 01 00 表 b 0 0 0 0 0 0 1 0 0 屬性值 1 1 0 1 1 0 0 1 0 0 屬性值 21 20 1 033 032 031 030 02 01 00 四進(jìn)制碼 19 18 17 16 15 14 13 12 11 葉結(jié)點(diǎn)號(hào) 10 33 9 32 8 31 7 303 6 302 5 301 4 300 3 23 2 22 1 四進(jìn)制碼 葉結(jié)點(diǎn)號(hào) 四進(jìn)制的線性四叉樹編碼 四進(jìn)制線性四叉樹編碼的特點(diǎn)： 優(yōu)點(diǎn)是便于實(shí)現(xiàn)行列值及其編碼之間的轉(zhuǎn)換； 缺點(diǎn)是存儲(chǔ)開銷大，且一般軟件都不支持四進(jìn)制 。 （ 2）基于四進(jìn)制的線性四叉樹編碼 2）線性四叉樹及編碼 （ 3）基于十進(jìn)制的線性四叉樹編碼 編碼： 將二進(jìn)制的行列號(hào)按位交錯(cuò)排列，可得到四叉樹葉結(jié)點(diǎn)的二進(jìn)制地址碼，進(jìn)而將二進(jìn)制碼轉(zhuǎn)成十進(jìn)制碼，得到四叉樹編碼。 0 0 1 1 1 0 行號(hào) =011 MD=14 2）線性四叉樹及編碼 表 a經(jīng) 自下而上 歸并得表 b。依次檢查表 a中四個(gè)相鄰葉結(jié)點(diǎn)的屬性代碼是否相同。若相同則歸并成一個(gè)父結(jié)點(diǎn)， 記下地址及代碼。 否則不予歸并。然后再歸并更高一層父結(jié)點(diǎn)，如此循環(huán)，直到不能歸并為止。 （ 3)基于十進(jìn)制的線性四叉樹編碼 2）線性四叉樹及編碼 63 62 59 58 47 46 43 42 111 61 60 57 56 45 44 41 40 110 55 54 51 50 39 38 35 34 101 53 52 49 48 37 36 33 32 100 31 30 27 26 15 14 11 10 011 29 28 25 24 13 12 9 8 010 23 22 19 18 7 6 3 2 001 21 20 17 16 5 4 1 0 000 111 110 101 100 011 010 001 000 60 56 44 40 51 50 52 49 48 36 32 15 14 13 12 8 16 4 0 表 a 表 b 0 60 0 56 0 52 0 51 0 50 0 49 1 48 0 44 0 40 1 36 1 32 0 16 1 15 1 14 0 13 0 12 1 8 0 4 0 0 屬性值 MD碼值 屬性值 MD碼值 0 49 1 48 0 40 1 32 0 16 1 14 0 12 1 8 0 0 四叉樹游程編碼 特點(diǎn)： 比四進(jìn)制節(jié)省儲(chǔ)存空間，且 前后兩個(gè) MD碼之間差代表了葉結(jié)點(diǎn)的大小 ，還可進(jìn)一步利用游程編碼對(duì)數(shù)據(jù)進(jìn)行壓縮。 優(yōu)點(diǎn)： 具有可變分辨率，能精確表示圖形的細(xì)節(jié)部分，編碼效率高；具有區(qū)域性質(zhì)，適合于圖形圖像的分析運(yùn)算；便于島的分析。 (3)基于十進(jìn)制的線性四叉樹編碼 2）線性四叉樹及編碼 （三）四叉樹優(yōu)缺點(diǎn) 優(yōu)點(diǎn) ： 1） 對(duì)于團(tuán)塊圖像 ， 四叉樹表示法占用空間比網(wǎng)絡(luò)法要少得多 ， 四叉樹表示法基本上是一種 非冗余表示法 。 2） 四叉樹具有可變率或多重分辯率的特點(diǎn)使得它有很好的應(yīng)用前景 ， 適用于處理凝聚性或呈塊狀分布的空間數(shù)據(jù) ， 特別適用于處理分布不均勻的塊狀空間數(shù)據(jù) ， 但不適用于連續(xù)表面 （ 如地形 ） 或線狀地物 。 此外 ， 目前應(yīng)用四叉樹還存下列 問題 ： 1) 矢 /柵正反變換還不理想 。 2) 建立四叉樹耗費(fèi)機(jī)時(shí)很多 。 3) 四叉樹雖可修改 ， 但很費(fèi)事 （ 具體的數(shù)據(jù)結(jié)構(gòu)中會(huì)提到 ） （三）四叉樹優(yōu)缺點(diǎn) 4) 四叉樹未能直接表示物體間的拓?fù)潢P(guān)系 。 5) 與非樹表示法比較 ， 四叉樹表示法的缺點(diǎn)在于轉(zhuǎn)換的不穩(wěn)定性或叫 滑動(dòng)變異 例如 ， 兩個(gè)圖像的差異僅由于平移 ， 就會(huì)構(gòu)成極為不同的四叉樹 ， 因而很難根據(jù)四叉樹來判斷這兩個(gè)圖像是否全同 ， 故不利于做形狀分析和模式識(shí)別 ， A 0 A 1 A 4 A 5 A 2 B 3 B 6 B 7 A 8 A 9 B 12 B 13 A 10 A 11 B 14 B 15 A A A A A B B B A A B B A A B B 6) 一個(gè) 物體 的圖像 在構(gòu)成四叉樹時(shí)會(huì)被分割到若干個(gè)象限中，使它失去了內(nèi)在的相關(guān)性 。 A A A A A B B B A A B B A A B B 二、矢量數(shù)據(jù)結(jié)構(gòu) 概念 （一）概念 矢量結(jié)構(gòu)是表達(dá)空間數(shù)據(jù)的另一種常見 數(shù)據(jù)結(jié)構(gòu)，通過記錄坐標(biāo)的方式盡可能精 確地表示點(diǎn)、線、多邊形等地理實(shí)體 。 二、矢量數(shù)據(jù)結(jié)構(gòu) （二）基本特征 ?點(diǎn)無大小、地理空間連續(xù)。 ?屬性特征隱性表示。 幾何位置、屬性數(shù)據(jù)、拓?fù)潢P(guān)系分別存儲(chǔ)。 ?指向地物、感覺宏觀 幾何實(shí)體無論大小，每個(gè)實(shí)體均勻一條數(shù)據(jù)記錄存儲(chǔ)， 一條記錄指向一個(gè)地物。 二、矢量數(shù)據(jù)結(jié)構(gòu) （三）編碼內(nèi)容 ? 唯一標(biāo)識(shí)符 ? 空間位置 ：（ x, y）坐標(biāo)對(duì) ? 拓?fù)潢P(guān)系 ? 屬性特征 ? 時(shí)間特征 二、矢量數(shù)據(jù)結(jié)構(gòu) （三）編碼內(nèi)容 （ ）點(diǎn)實(shí)體編碼內(nèi)容 ? 點(diǎn)實(shí)體包括單獨(dú)一對(duì)（ x,y）坐標(biāo)定位的一切地 理或制圖實(shí)體。 ? 點(diǎn)是空間上不能再分的地理實(shí)體，可以是具體 的或抽象的 。 二、矢量數(shù)據(jù)結(jié)構(gòu) （三）編碼內(nèi)容 （ ）點(diǎn)實(shí)體 二、矢量數(shù)據(jù)結(jié)構(gòu) （三）編碼內(nèi)容 （ ）線實(shí)體 ? 由直線元素構(gòu)成的各種線性要素。 ? 線實(shí)體主要用來表示線狀地物符號(hào)線和多邊形邊界，有時(shí)也稱為“弧”、“鏈”、“串”等 。 線實(shí)體編碼基本內(nèi)容 二、矢量數(shù)據(jù)結(jié)構(gòu) （三）編碼內(nèi)容 （ ）多邊形 ? 區(qū)域?qū)嶓w中，具有名稱屬性和分類屬性，多用多邊形表示 。 ? 多邊形矢量編碼不但要表示位置和屬性，更為重要的是要能表達(dá)區(qū)域的拓?fù)湫再|(zhì) 。 二、矢量數(shù)據(jù)結(jié)構(gòu) （四）矢量數(shù)據(jù)結(jié)構(gòu)編碼 編碼方法： ? 無拓?fù)潢P(guān)系的編碼方法：僅記錄空間目標(biāo)的位置和屬性信息，而不記錄拓?fù)潢P(guān)系。 ? 拓?fù)潢P(guān)系的編碼方法：不僅記錄空間目標(biāo)的位置和屬性信息， 而且記錄拓?fù)潢P(guān)系。 二、矢量數(shù)據(jù)結(jié)構(gòu) （四）矢量數(shù)據(jù)結(jié)構(gòu)編碼 （ ）坐標(biāo)序列法 以多邊形為單元進(jìn)行組織。由多邊形邊界的 x, y坐標(biāo)對(duì)集合組成。 邊界坐標(biāo)數(shù)據(jù)與多邊形單元實(shí)體一一對(duì)應(yīng)，各個(gè)多邊形的邊界都有單獨(dú)編碼和數(shù)字化。 二、矢量數(shù)據(jù)結(jié)構(gòu) （四）矢量數(shù)據(jù)結(jié)構(gòu)編碼 （ ）坐標(biāo)序列法 10： x1,y1； x2,y2； x3,y3； x4,y4； x5,y5； x6,y6； x7,y7；x8,y8； x9,y9； x10,y10； x11,y11； 20： x1,y1； x12,y12； x13,y13； x14,y14； x15,y15； x16,y16； x17,y17； x18,y18； x19,y19； x20,y20； x21,y21；x22,y22； x23,y23； x8,y8； x9,y9； x10,y10； x11,y11； 30： x33,y33； x34,y34； x35,y35； x36,y36； x37,y37；x38,y38； x39,y39； x40,y40； 40： x19,y19； x20,y20； x21,y21； x28,y28； x29,y29；x30,y30； x31,y31； x32,y32； 50： x21,y21； x22,y22； x23,y23； x8,y8； x7,y7； x6,y6；x24,y24； x25,y25； x26,y26； x27,y27； x28,y28； 二、矢量數(shù)據(jù)結(jié)構(gòu) （四）矢量數(shù)據(jù)結(jié)構(gòu)編碼 （ ）坐標(biāo)序列法 ? 優(yōu)點(diǎn)： 編碼容易、數(shù)字化操作簡單、數(shù)據(jù)編排直觀。 ? 缺點(diǎn) ： ? 多邊形之間公共邊界數(shù)字化兩遍，數(shù)據(jù)冗余存儲(chǔ)，多邊形邊界容易出現(xiàn)間隙或重疊。 ? 缺少的多邊形的鄰域信息和圖形的拓?fù)潢P(guān)系。 ? 島作為一個(gè)單獨(dú)的圖形，沒有建立與外界多邊形的聯(lián)系。 二、矢量數(shù)據(jù)結(jié)構(gòu) （四）矢量數(shù)據(jù)結(jié)構(gòu)編碼 （ ）樹狀索引結(jié)構(gòu)編碼 采用樹狀索引，以減少數(shù)據(jù)冗余并間接增加鄰域信息。 具體方法： 對(duì)所有邊界點(diǎn)進(jìn)行數(shù)字化，將坐標(biāo)對(duì)以順序方式存儲(chǔ)，由點(diǎn)索引與邊界號(hào)相聯(lián)系，以線索引與各多邊形相聯(lián)系，形成樹狀索引結(jié)構(gòu) 。 二、矢量數(shù)據(jù)結(jié)構(gòu) （四）矢量數(shù)據(jù)結(jié)構(gòu)編碼 （ ）樹狀索引結(jié)構(gòu)編碼 數(shù)據(jù)記錄形式： 多邊形文件 多邊形與線索引文件 線文件 邊界線與點(diǎn)索引文件 點(diǎn)文件 點(diǎn)文件： 點(diǎn)號(hào) — x,y坐標(biāo) 線文件： 線號(hào) — 起點(diǎn) — 終點(diǎn) — 點(diǎn)號(hào)序列 多邊形文件： 多邊形號(hào) — 邊界線號(hào)序列 例： P148P149 索引式 B C D E a b c f g h e f i b c i j 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 線與多邊形之間的樹狀索引 點(diǎn)與邊界線之間的樹狀索引 二、矢量數(shù)據(jù)結(jié)構(gòu) （四）矢量數(shù)據(jù)結(jié)構(gòu)編碼 （ ）樹狀索引結(jié)構(gòu)編碼 ? 優(yōu)點(diǎn)： 數(shù)據(jù)冗余小、編排直觀、鄰域信息和島狀信息 可以得到一定處理。 ? 缺點(diǎn) ： ? 運(yùn)算繁瑣。