gis數(shù)據(jù)結(jié)構(gòu)作業(yè)ppt課件(編輯修改稿)
2025-02-10 03:23 本頁(yè)面
【文章內(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 線(xiàn)性四叉樹(shù) 2022 2022 線(xiàn)性四叉樹(shù)進(jìn)行四進(jìn)制編碼葉結(jié)點(diǎn)位置采用基于四進(jìn)制的 Morton碼表示，這種編碼由加拿大學(xué)者 Morton于 1966年提出，稱(chēng) Morton碼或 Peano鍵，四進(jìn)制的 Morton碼又稱(chēng)為 MQ碼。 ? MQ碼是一串?dāng)?shù)字組成，每分割一次增加一位數(shù)，其中每位數(shù)字都是不大于 3的四進(jìn)制數(shù)。 ? 以行為序，以左下角為起點(diǎn)，按從左到右，從下到上的順序進(jìn)行編碼 四進(jìn)制 線(xiàn)性四叉樹(shù)編碼 (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： 四叉樹(shù) 從上而下 （ 形成 ） （ 從整體開(kāi)始 ） 由葉結(jié)點(diǎn)找 Morton碼 。 A、 分割一次 ， 增加一位數(shù)字 ， 大分割在前 ， 小分割在后 。所以 ， 碼的位數(shù)表示分割的次數(shù) 。 B、 每一個(gè)位均是不大于 3的四進(jìn)制數(shù) ， 表達(dá)位置 。 由 Morton找出四叉樹(shù)葉結(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)制 線(xiàn)性四叉樹(shù)編碼 (MQ碼 ) 2022 2022 四進(jìn)制 線(xiàn)性四叉樹(shù)編碼 (MQ碼 ) MQ編碼計(jì)算方法２ :四叉樹(shù)自下而上合并的方法 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)的屬性值， 相同合并（不同碼位去掉），不同則存盤(pán) ,直到?jīng)]有能夠合并的子塊為止。 然后進(jìn)行排序歸并得到圖 (b) MQ碼。最后再寫(xiě)成四進(jìn)制線(xiàn)性四叉樹(shù)。 四進(jìn)制 線(xiàn)性四叉樹(shù)編碼 (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)制 線(xiàn)性四叉樹(shù) 2022 2022 時(shí)間 圖像 1 64＊ 64 圖像 2 128＊ 128 圖像 3 256＊ 256 自下而上方法 自上而下方法 方法 圖像大小 兩種建立四叉樹(shù)方法效率的比較 常規(guī)四叉樹(shù)：自上而下方法 線(xiàn)性四叉樹(shù)：自下而上方法 2022 2022 ?四進(jìn)制 Morton碼直觀(guān)上切合四叉樹(shù)分割，但許多語(yǔ)言不支持四進(jìn)制變量，需用十進(jìn)制表示 Morton碼。 ?線(xiàn)性四叉樹(shù)的十進(jìn)制編碼簡(jiǎn)稱(chēng) MD編碼，它同線(xiàn)性四叉樹(shù)的四進(jìn)制編碼主要不同在于編碼值是十進(jìn)制自然數(shù)，其合并過(guò)程可直接按自然數(shù)順序進(jìn)行。 十進(jìn)制 線(xiàn)性四叉樹(shù)編碼 (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)，按 從左到右，從下到上 的順序掃描。 ? 掃描柵格單元的順序代碼稱(chēng)為十進(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)制 線(xiàn)性四叉樹(shù)編碼 (MＤ碼 ) 2022 2022 十進(jìn)制 線(xiàn)性四叉樹(shù)編碼 (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 線(xiàn)性四叉樹(shù)編碼的優(yōu)點(diǎn) (1)只存儲(chǔ)三個(gè)值，比常規(guī)四叉樹(shù)節(jié)省存儲(chǔ)空間； (2)由于記錄節(jié)點(diǎn)地址，既能直接找到其在四叉樹(shù)中的走向路徑，又 可以換算出它在整個(gè)柵格區(qū)域內(nèi)的行列位置； (3)壓縮和解壓縮比較方便，各部分的 分辨率可不同 ，既可精確地表 示圖形結(jié)構(gòu)，又可減少存儲(chǔ)量，易于進(jìn)行大部分圖形操作和運(yùn)算。 2022 2022 １ .寫(xiě)出下圖的四叉樹(shù)結(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