【文章內(nèi)容簡介】 將柵格數(shù)據(jù)（線狀地物面域邊界）表示為 矢量鏈 的記錄 鏈式編碼表 a a a a a a a b 屬性碼 起點行 起點列 鏈碼 a 1 4 556656 b 3 7 576654323… 優(yōu)點 ：鏈碼可有效地存貯壓縮柵格數(shù)據(jù)，便于面積、長度、轉(zhuǎn)折方向和邊界、線段凹凸度的計算。 缺點 ：不易做邊界合并，插入操作、編輯較困難（對局部修改將改變整體結(jié)構(gòu)）。區(qū)域空間分析困難，相鄰區(qū)域邊界被重復(fù)存儲。 四叉樹編碼 地理信息系統(tǒng)原理 GIS 五、四叉樹編碼 167。 23 柵格數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 返回 基本思想 ： 將 2n 2n象元組成的圖像 (不足的用背景補上 ) 按四個象限進行遞歸分割， 并判斷屬性是否單一， 單一：不分。 不單一：遞歸分割。 最后得到一顆四分叉的倒向樹。 四叉樹的樹形表示 ： 用一倒立樹表示這種分割和分割結(jié)果。 根 ：整個區(qū)域 高 ：深度、分幾級，幾次分割 葉 ：不能再分割的塊 樹叉 ：還需分割的塊 每個樹叉均有 4個分叉，叫四叉樹。 （一）四叉樹概述 ： 一種 可變分率 的 非均勻網(wǎng)格 系統(tǒng)。 是最有效的柵格數(shù)據(jù)壓縮編碼方法之一 A A A A A B B B A A B B A A B B 0 1 2 3 地理信息系統(tǒng)原理 GIS 編碼方法 167。 23 柵格數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 返回 1） 常規(guī)四叉樹 記錄這棵樹的葉結(jié)點外 ， 中間結(jié)點 ， 結(jié)點之間的聯(lián)系用指針聯(lián)系 ， 每個結(jié)點需要 6個變量： 父結(jié)點指針 、 四個子結(jié)點的指針和本結(jié)點的屬性值 。 指針不僅 增加了數(shù)據(jù)的存儲量 ，還增加了操作的 復(fù)雜性 ：如層次數(shù)（分割次數(shù)）由從父結(jié)點移到根結(jié)點的次數(shù)來確定，結(jié)點所代表的圖像塊的位置需要從根節(jié)點開始逐步推算下來。所以， 常規(guī)四叉樹并不廣泛用于存儲數(shù)據(jù) ，其價值在于建立索引文件，進行數(shù)據(jù)檢索。 地理信息系統(tǒng)原理 GIS 2）線性四叉樹 167。 23 柵格數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 返回 記錄葉結(jié)點的 位置，深度 （幾次分割）和屬性。 地址碼（定位碼、 Morton碼） 四進制、十進制 優(yōu)點 ： 存貯量小，只對葉結(jié)點編碼，節(jié)省了大量中間結(jié)點的存儲，地址碼隱含著結(jié)點的分割路徑和分割次數(shù)。 線性四叉樹可直接尋址，通過其坐標值直接計算其Morton碼，而不用建立四叉樹。 定位碼容易存儲和執(zhí)行實現(xiàn)集合相加等組合操作。 地理信息系統(tǒng)原理 GIS （二）四進制的 Morton碼 167。 23 柵格數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 返回 方法 1： 四叉樹從上而下 （ 形成 ） （ 從整體開始 ） 由葉結(jié)點找 Morton碼 。 A、 分割一次 ， 增加一位數(shù)字 ， 大分割在前 ， 小分割在后 。 所以 ， 碼的位數(shù)表示分割的次數(shù) 。 B、 每一個位均是不大于 3的四進制數(shù) ， 表達位置 。 由 Morton找出四叉樹葉結(jié)點的具體位置 。 0 1 2 3 A A A A A B B B A A B B A A A B B 03 B A 地理信息系統(tǒng)原理 GIS 方法 2：四叉樹自下而上合并的方法 167。 23 柵格數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 返回 1） 計算每個柵格對應(yīng)的 MQ MQ=2*Ib+Jb I,J化為二進制 Ib,Jb 看最大的 I,J,不足在前補零 。 其 始行列號從 0計 。 2) 按碼的升序排成線性表 ， 放在連續(xù)的內(nèi)存塊中 。 3） 依次檢查每四個相鄰的 MQ對應(yīng)的屬性值 ， 相同合并 （ 不同碼位去掉 ） ， 不同則存盤 ,直到?jīng)]有能夠合并的子塊為止 。 A A A A A B B B A A B B A A B B 地理信息系統(tǒng)原理 GIS （三）十進制的 Morton碼 MD 167。 23 柵格數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 返回 一種按位操作的方法 ： 如行為 列為 3的柵格的 MD 步驟： (1)行 、 列號為二進制 Ib= 1 0 Jb= 1 1 (2)I行 J列交叉 1 1 0 1 = 13 (3)再化為十進制 . 實質(zhì)上是按左上 、 右上 、 左下 、 右下的順序 ， 從零開始對每個柵格進行自然編碼 。 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 四進制 Morton碼直觀上切合四叉樹分割，但許多語言不支持四進制變量，需用十進制表示 Morton碼 . 地理信息系統(tǒng)原理 GIS 把一幅 2n 2n的圖像壓縮成線性四叉樹的過程 167。 23 柵格數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 返回 1176。 、按 Morton碼把圖象讀入一維數(shù)組。 2176。 、相鄰的四個象元比較，一致的合并，只記錄第一個象元的 Morton碼。循環(huán)比較所形成的大塊，相同的再合并，直到不能合并為止。 3176。 、進一步用游程長度編碼壓縮。壓縮時只記錄第一個象元的 Morton碼。 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 右圖的壓縮處理過程為： 1176。 、按 Morton Morton碼： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 象 元 值： A A A B A B B B A A A A B B B B 2176。 、四相鄰象元合并，只記錄第一個象元的 Morton碼。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B 3176。 、 由于不能進一步合并 ， 則用游程長度編碼壓縮 。 0 3 4 6 8 12 A B A B A B 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 地理信息系統(tǒng)原理 GIS （四）四叉樹優(yōu)缺點 167。 23 柵格數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 優(yōu)點 ： 1） 對于團塊圖像 ， 四叉樹表示法占用空間比網(wǎng)絡(luò)法要少得多 ， 四叉樹表示法基本上是一種 非冗余表示法 。 2） 四叉樹具有可變率或多重分辯率的特點使得它有很好的應(yīng)用前景 ，適用于處理凝聚性或呈塊狀分布的空間數(shù)據(jù) ， 特別適用于處理分布不均勻的塊狀空間數(shù)據(jù) ， 但不適用于連續(xù)表面 （ 如地形 ） 或線狀地物 。 此外 ， 目前應(yīng)用四叉樹還存下列 問題 ： 1) 矢 /柵正反變換還不理想 。 2) 建立四叉樹耗費機時很多 。 3) 四叉樹雖可修改 ， 但很費事 （ 具體的數(shù)據(jù)結(jié)構(gòu)中會提到 ） 地理信息系統(tǒng)原理 GIS 4) 四叉樹 未能直接 表示物體間的拓撲關(guān)系。 167。 23 柵格數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 返回 5) 與非樹表示法比較 ， 四叉樹表示法的缺點在于轉(zhuǎn)換的不穩(wěn)定性或叫 滑動變異 例如 ， 兩個圖像的差異僅由于平移 ， 就會構(gòu)成極為不同的四叉樹 ， 因而很難根據(jù)四叉樹來判斷這兩個圖像是否全同 ， 故不利于做形狀分析和模式識別 ， 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òu)成四叉樹時會被分割到若干個象限中，使它失去了內(nèi)在的相關(guān)性 。 A A A A A B B B A A B B A A B B 地理信息系統(tǒng)原理 GIS 167。 22 矢量 數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 一、圖形表示 返回 摘自 張超 地理信息系統(tǒng)原理 GIS 二、矢量數(shù)據(jù)的獲取方式 167。 22 矢量數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 1) 由外業(yè)測量獲得 可利用測量儀器自動記錄測量成果 (常稱為電子手薄 )，然后轉(zhuǎn)到地理數(shù)據(jù)庫中。 2)由柵格數(shù)據(jù)轉(zhuǎn)換獲得 利用柵格數(shù)據(jù)矢量化技術(shù)，把柵格數(shù)據(jù)轉(zhuǎn)換為矢量數(shù)據(jù)。 3)跟蹤數(shù)字化 用跟蹤數(shù)字化的方法，把地圖變成離散的矢量數(shù)據(jù)。 返回 地理信息系統(tǒng)原理 GIS 三、矢量數(shù)據(jù)組織 167。 22 矢量數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 點：坐標對 （ x,y） +識別符 線：坐標對系列 (x1,y1)..(xn,yn) 及 有關(guān)屬性 、 其它屬性 面：首尾相同的坐標串 關(guān)系表 幾何位置坐標文件 連接 矢量數(shù)據(jù)表示時 應(yīng)考慮以下問題 ： 矢量數(shù)據(jù)自身的存貯和處理。 與屬性數(shù)據(jù)的聯(lián)系。 矢量數(shù)據(jù)之間的空間關(guān)系 (拓撲關(guān)系 )。 地理信息系統(tǒng)原理 GIS 以點為例： 167。 22 矢量數(shù)據(jù)結(jié)構(gòu) 第二章 GIS 數(shù)據(jù)結(jié)構(gòu) 坐標 識別符 若是簡單點要素如獨立樹、電線竿、三角點，符號、 有關(guān)屬性 中包括 比例尺、方向 若是注記點，記錄有關(guān)字符的大小、方向、字體、排列等 若是結(jié)點 Vertex：符號：指針、與線相交的角度。 其它屬性 : 三角點設(shè)立年代、材料等 線（符號、方