gis數(shù)據(jù)結(jié)構(gòu)作業(yè)ppt課件(編輯修改稿)
2025-02-10 03:23 本頁面
【文章內(nèi)容簡(jiǎn)介】 ze Value 0 0 4*4 1 24 12 2*2 1 49 301 1*1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 線性四叉樹 2022 2022 線性四叉樹進(jìn)行四進(jìn)制編碼葉結(jié)點(diǎn)位置采用基于四進(jìn)制的 Morton碼表示，這種編碼由加拿大學(xué)者 Morton于 1966年提出，稱 Morton碼或 Peano鍵，四進(jìn)制的 Morton碼又稱為 MQ碼。 ? MQ碼是一串?dāng)?shù)字組成，每分割一次增加一位數(shù)，其中每位數(shù)字都是不大于 3的四進(jìn)制數(shù)。 ? 以行為序，以左下角為起點(diǎn)，按從左到右，從下到上的順序進(jìn)行編碼 四進(jìn)制 線性四叉樹編碼 (MQ碼 ) 7 6 5 4 3 2 1 0 ？ ？ 200 300 022 023 032 033 020 021 030 031 002 003 012 013 102 103 000 001 010 011 100 101 MQ 000 001 010 011 100 101 110 111 編碼表 2022 2022 MQ編碼計(jì)算方法 1： 四叉樹 從上而下 （ 形成 ） （ 從整體開始 ） 由葉結(jié)點(diǎn)找 Morton碼 。 A、 分割一次 ， 增加一位數(shù)字 ， 大分割在前 ， 小分割在后 。所以 ， 碼的位數(shù)表示分割的次數(shù) 。 B、 每一個(gè)位均是不大于 3的四進(jìn)制數(shù) ， 表達(dá)位置 。 由 Morton找出四叉樹葉結(jié)點(diǎn)的具體位置 。 2 3 0 1 A A A A A B B B A A B B A A A B B ２１ B A 四進(jìn)制 線性四叉樹編碼 (MQ碼 ) 2022 2022 四進(jìn)制 線性四叉樹編碼 (MQ碼 ) MQ編碼計(jì)算方法２ :四叉樹自下而上合并的方法 MQ = 2 IB+JB （ IB、 JB分別為柵格單元行列號(hào)的二進(jìn)制數(shù)， 其始行列號(hào)從 0計(jì) 。 P55圖 218） 如：已知十進(jìn)制 第一行、第五列 的柵格單元，求它的 MQ碼。 首先將十進(jìn)制第一行、第五列轉(zhuǎn)成二進(jìn)制形式，得到 行 Ib =(001) 列 Jb =(101) 其地址碼為 : MQ = 2 Ib+Jb = 2 1+101 = 103 例 :求 256*256第 20行，第 200列的Ｍ Ｑ ? 11021200表示．．．．．．．．．．．． ？ ？ 200 300 022 023 032 033 020 021 030 031 002 003 012 013 102 103 000 001 010 011 100 101 2022 2022 圖 (a)所示為 8 8列圖，即柵格單元 23 23，其位置碼的最長(zhǎng)位數(shù)是 3位。 現(xiàn)對(duì)圖 (a)按 MQ碼的編碼表，依次檢查每四個(gè)相鄰的 MQ對(duì)應(yīng)的屬性值， 相同合并（不同碼位去掉），不同則存盤 ,直到?jīng)]有能夠合并的子塊為止。 然后進(jìn)行排序歸并得到圖 (b) MQ碼。最后再寫成四進(jìn)制線性四叉樹。 四進(jìn)制 線性四叉樹編碼 (MQ碼 ) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 2 32 33 302 303 31 300 301 0 12 13 10 11 MQ碼 MQ Size Value 0 4*4 1 12 2*2 1 301 1*1 1 四進(jìn)制 線性四叉樹 2022 2022 時(shí)間 圖像 1 64＊ 64 圖像 2 128＊ 128 圖像 3 256＊ 256 自下而上方法 自上而下方法 方法 圖像大小 兩種建立四叉樹方法效率的比較 常規(guī)四叉樹：自上而下方法 線性四叉樹：自下而上方法 2022 2022 ?四進(jìn)制 Morton碼直觀上切合四叉樹分割，但許多語言不支持四進(jìn)制變量，需用十進(jìn)制表示 Morton碼。 ?線性四叉樹的十進(jìn)制編碼簡(jiǎn)稱 MD編碼，它同線性四叉樹的四進(jìn)制編碼主要不同在于編碼值是十進(jìn)制自然數(shù)，其合并過程可直接按自然數(shù)順序進(jìn)行。 十進(jìn)制 線性四叉樹編碼 (MＤ 碼 ) A 10 A 11 A 14 A 15 A 8 B 9 B 12 B 13 A 2 A 3 B 6 B 7 A 0 A 1 B 4 B 5 42 43 46 47 58 59 62 63 40 41 44 45 56 57 60 61 34 35 38 39 50 51 54 55 32 33 36 37 48 49 52 53 10 11 14 15 26 27 30 31 8 9 12 13 24 25 28 29 2 3 6 7 18 19 22 23 0 1 4 5 16 17 20 21 2022 2022 ? 像元順序以行為序，以 左 下 角 為起點(diǎn)，按 從左到右，從下到上 的順序掃描。 ? 掃描柵格單元的順序代碼稱為十進(jìn)制莫頓碼 (Morton碼 )或 Peano鍵。 完全柵格結(jié)構(gòu)掃描順序示意圖 （圖 2－ 21） SW 0 SE 1 NE 3 NW 2 42 43 46 47 58 59 62 63 40 41 44 45 56 57 60 61 34 35 38 39 50 51 54 55 32 33 36 37 48 49 52 53 10 11 14 15 26 27 30 31 8 9 12 13 24 25 28 29 2 3 6 7 18 19 22 23 0 1 4 5 16 17 20 21 十進(jìn)制 線性四叉樹編碼 (MＤ碼 ) 2022 2022 十進(jìn)制 線性四叉樹編碼 (MＤ 碼 ) 方法２：按位操作的方法 如行為 列為 3的柵格的 MD步驟： (1)行 、 列號(hào)為二進(jìn)制： IB= 1 0 JB= 1 1 (2)I行 J列交叉 ： 1 1 0 1 = 13 (3)再化為十進(jìn)制 . 例 :求 256*256第 20行，第 200列的Ｍ D? 如行為 列為 200的柵格的 MD步驟： (1)行 、 列號(hào)為二進(jìn)制： IB= 10100 JB= 11001000 二進(jìn)制計(jì)算 (2)I行 J列交叉 ： 0101001001100000 = 21088 附件計(jì)算器 (3)再化為十進(jìn)制 . 10 11 14 15 8 9 12 13 2 3 6 7 0 1 4 5 2022 2022 MＤ 與 MQ MD MQ Size Value 0 0 4*4 1 24 12 2*2 1 49 301 1*1 1 301 022 023 032 033 020 021 030 031 120 002 003 012 013 000 001 010 011 42 43 46 47 58 59 62 63 40 41 44 45 56 57 60 61 34 35 38 39 50 51 54 55 32 33 36 37 48 49 52 53 10 11 14 15 26 27 30 31 8 9 12 13 24 25 28 29 2 3 6 7 18 19 22 23 0 1 4 5 16 17 20 21 2022 2022 線性四叉樹編碼的優(yōu)點(diǎn) (1)只存儲(chǔ)三個(gè)值，比常規(guī)四叉樹節(jié)省存儲(chǔ)空間； (2)由于記錄節(jié)點(diǎn)地址，既能直接找到其在四叉樹中的走向路徑，又 可以換算出它在整個(gè)柵格區(qū)域內(nèi)的行列位置； (3)壓縮和解壓縮比較方便，各部分的 分辨率可不同 ，既可精確地表 示圖形結(jié)構(gòu)，又可減少存儲(chǔ)量，易于進(jìn)行大部分圖形操作和運(yùn)算。 2022 2022 １ .寫出下圖的四叉樹結(jié)構(gòu)文件 （Ｐ 57圖 220） 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1