柵格數(shù)據(jù)結(jié)構(gòu)PPT學習教案

1、會計學1柵格數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu)GISGIS空間數(shù)據(jù)結(jié)構(gòu)分類示意圖空間數(shù)據(jù)結(jié)構(gòu)分類示意圖隨著隨著GISGIS技術(shù)的發(fā)展，空間數(shù)據(jù)結(jié)構(gòu)有了新的內(nèi)容技術(shù)的發(fā)展，空間數(shù)據(jù)結(jié)構(gòu)有了新的內(nèi)容( (張張超超) )返回返回休息休息第1頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)本節(jié)重點：本節(jié)重點： 柵格數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點及各種數(shù)據(jù)編碼的特點柵格數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點及各種數(shù)據(jù)編碼的特點。 四叉樹數(shù)據(jù)結(jié)構(gòu)的編碼方法。四叉樹數(shù)據(jù)結(jié)構(gòu)的編碼方法。 (P(P102-113102-113) )本節(jié)難點：本節(jié)難點： 四叉樹數(shù)據(jù)結(jié)構(gòu)的編碼方法。四叉樹數(shù)據(jù)結(jié)構(gòu)的編碼方法。返回返回休息休息第2頁

2、/共51頁第3頁/共51頁ABBBAABBBAABBBAA第4頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)(P(P9292) )返回返回休息休息 基于柵格模型的數(shù)據(jù)結(jié)構(gòu)簡稱為柵格數(shù)據(jù)結(jié)構(gòu),指將空間分割成有規(guī)則的網(wǎng)格,在各個網(wǎng)格上給出相應的屬性值來表示地理實體的一種數(shù)據(jù)組織形式。第5頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第6頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)三、空間目標的分層表示方法三、空間目標的分層表示方法(P(P9393) ) 在柵格文件中，每個柵

3、格只能賦予唯一的值，在柵格文件中，每個柵格只能賦予唯一的值，因此，某一個柵格若有不同的值，則要分別存因此，某一個柵格若有不同的值，則要分別存貯于不同的文件。例如，對于某個區(qū)域來說，貯于不同的文件。例如，對于某個區(qū)域來說，其土壤和森林覆蓋類型就要分別存貯為土壤和其土壤和森林覆蓋類型就要分別存貯為土壤和森林數(shù)據(jù)文件。森林數(shù)據(jù)文件。返回返回休息休息第7頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)三、空間目標的分層表示方法三、空間目標的分層表示方法 可以有三種可能的數(shù)據(jù)組織方法：可以有三種可能的數(shù)據(jù)組織方法： a a、以象元為記錄的序列。不同層上同一象、以象元為記

4、錄的序列。不同層上同一象元位置上的不同屬性值表示為一個列數(shù)組；元位置上的不同屬性值表示為一個列數(shù)組； b b、以層為基礎，每一層又以象元為序記錄、以層為基礎，每一層又以象元為序記錄它的坐標和屬性值，每一層記錄后再記錄下一它的坐標和屬性值，每一層記錄后再記錄下一層；層； c c、以層為基礎，但每一層則以多邊形為序、以層為基礎，但每一層則以多邊形為序記錄多邊形的屬性值和充滿多邊形的各象元的記錄多邊形的屬性值和充滿多邊形的各象元的坐標。坐標。 返回返回休息休息第8頁/共51頁地理信息系統(tǒng)原理三、空間目標的分層表示方法三、空間目標的分層表示方法 第9頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù)

5、 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)三、空間目標的分層表示方法三、空間目標的分層表示方法 上述三種方法中：上述三種方法中：節(jié)省了許多存儲空間節(jié)省了許多存儲空間，因為，因為N N層實際上只存儲了一層的象元坐標；方層實際上只存儲了一層的象元坐標；方法節(jié)省了許多用于存儲屬性值的空間，同一法節(jié)省了許多用于存儲屬性值的空間，同一屬性的制圖單元的幾個象元排列在一起，使地屬性的制圖單元的幾個象元排列在一起，使地圖分析和制圖處理較為方便；方法每層每個圖分析和制圖處理較為方便；方法每層每個象元一一記錄，它的形式最為簡單。象元一一記錄，它的形式最為簡單。 返回返回休息休息第10頁/共51頁 4 - 5 4 - 5 柵

6、格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu) 在柵格單元中每個代碼本身明確地代表了實在柵格單元中每個代碼本身明確地代表了實體的屬性或?qū)傩缘木幋a。體的屬性或?qū)傩缘木幋a。四、特點四、特點 返回返回休息休息第11頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)五、決定柵格單元代碼的方法五、決定柵格單元代碼的方法 通常在一個柵格單元上會對應幾種不同的屬通常在一個柵格單元上會對應幾種不同的屬性值，而每一個單元只能取一個值，為了盡量保性值，而每一個單元只能取一個值，為了盡量保持地表的真實性，保證最大的信息容量。在這種持地表的真實性，保證最大的信息容量。在這種情況下有不同的取值

7、方法：情況下有不同的取值方法：中心點法、面積占優(yōu)中心點法、面積占優(yōu)法、重要性法、百分比法法、重要性法、百分比法。 返回返回休息休息第12頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)五、決定柵格單元代碼的方法五、決定柵格單元代碼的方法 返回返回休息休息第13頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)五、決定柵格單元代碼的方法五、決定柵格單元代碼的方法 返回返回休息休息第14頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)五、決定柵格單元代碼的方法五、決定柵格單元代碼的方法 返回返回休息

8、休息第15頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)五、決定柵格單元代碼的方法五、決定柵格單元代碼的方法 返回返回休息休息第16頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第17頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第18頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第19頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第20頁/共51頁 4

9、 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)分辨率與存儲單元示意圖分辨率與存儲單元示意圖 (1) (1)在高分辨率的情況下將占據(jù)更多的像元或存儲在高分辨率的情況下將占據(jù)更多的像元或存儲單元；單元；(2)(2)柵格模型是通過同樣顏色或灰度像元來表達柵格模型是通過同樣顏色或灰度像元來表達具有相同屬性的面狀區(qū)域的。因此有許多柵格單元或像具有相同屬性的面狀區(qū)域的。因此有許多柵格單元或像元與其鄰近的若干像元都具有相同的屬性值。為了節(jié)省元與其鄰近的若干像元都具有相同的屬性值。為了節(jié)省存儲空間，對柵格數(shù)據(jù)進行壓縮。下面，將介紹四種常存儲空間，對柵格數(shù)據(jù)進行壓縮。下面，將介紹四種常用的數(shù)

10、據(jù)壓縮方法。用的數(shù)據(jù)壓縮方法。 返回返回休息休息第21頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第22頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第23頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第24頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第25頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第26頁/共51頁 4 - 5

11、4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu) 對下一圖像的塊狀編碼如下 ：(1,1,1,0)，(1,2,2,4)，(1,4,1,7)返回返回休息休息第27頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第28頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)返回返回休息休息第29頁/共51頁第30頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)常規(guī)四叉樹編碼常規(guī)四叉樹編碼常規(guī)四叉樹的生成方法有兩種：常規(guī)四叉樹的生成方法有兩種：(1)(1)自頂向下自頂向下(top-do

12、wn)(top-down)的分割方法的分割方法: :先檢查全先檢查全區(qū)域，內(nèi)容不完全相同再四分割，往下逐次遞區(qū)域，內(nèi)容不完全相同再四分割，往下逐次遞歸。歸。(2)(2)從底向上從底向上(down-top)(down-top)的合并方法：首先對的合并方法：首先對柵格數(shù)據(jù)按一定的順序檢查四個相鄰柵格單元柵格數(shù)據(jù)按一定的順序檢查四個相鄰柵格單元的屬性值，如果相同，則進行合并，逐次往上的屬性值，如果相同，則進行合并，逐次往上遞歸。遞歸。 返回返回休息休息第31頁/共51頁常規(guī)四叉樹編碼的過程常規(guī)四叉樹編碼的過程返回返回休息休息第32頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù)

13、 據(jù) 結(jié) 構(gòu)常規(guī)四叉樹編碼常規(guī)四叉樹編碼常規(guī)四叉樹的特點如下：常規(guī)四叉樹的特點如下：(1)(1)運算量較大。因為，大量數(shù)據(jù)需要重復檢查才能確定劃分；（如運算量較大。因為，大量數(shù)據(jù)需要重復檢查才能確定劃分；（如7 7、8 8、9 9、1010等格網(wǎng)需要檢查等格網(wǎng)需要檢查4 4次）次）(2)(2)占用的存儲空間較大。每個結(jié)點需要占用的存儲空間較大。每個結(jié)點需要六個變量六個變量才能加以表達：一個變量表示父結(jié)點指針，四個變量代表四個子結(jié)點指針，一個變量代表本結(jié)點的灰度或?qū)傩灾?。才能加以表達：一個變量表示父結(jié)點指針，四個變量代表四個子結(jié)點指針，一個變量代表本結(jié)點的灰度或?qū)傩灾?。返回返回休息休息?3頁/

14、共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)線性四叉樹編碼：線性四叉樹編碼： 為了克服常規(guī)四叉樹占用存儲空間大的缺點為了克服常規(guī)四叉樹占用存儲空間大的缺點，人們提出了線性四叉樹的算法。線性四叉樹只，人們提出了線性四叉樹的算法。線性四叉樹只存儲最后葉結(jié)點的信息，即結(jié)點的存儲最后葉結(jié)點的信息，即結(jié)點的位置、大小和位置、大小和灰度灰度。葉結(jié)點位置采用基于四進制或十進制的。葉結(jié)點位置采用基于四進制或十進制的MortonMorton碼表示（加拿大學者碼表示（加拿大學者MortonMorton于于19661966年提出年提出）；葉結(jié)點的大小用結(jié)點的深度或?qū)哟伪硎?。）；葉結(jié)

15、點的大小用結(jié)點的深度或?qū)哟伪硎?。MortonMorton碼又稱為碼又稱為M M碼。碼。 返回返回休息休息第34頁/共51頁第35頁/共51頁（一）基于四進制的（一）基于四進制的MortonMorton碼碼步驟步驟: 1): 1)將十進制的行列號轉(zhuǎn)換成二進制數(shù)將十進制的行列號轉(zhuǎn)換成二進制數(shù) 2)2)按按M MQ Q碼的計算公式碼的計算公式 M MQ Q= = 計算對應計算對應的的M MQ Q碼碼 分別為柵格單元行列號的二進制數(shù)。下分別為柵格單元行列號的二進制數(shù)。下表為表為8 8行行8 8列研究區(qū)域的基于四進制的列研究區(qū)域的基于四進制的M MQ Q碼計算成果碼計算成果。bbJI 2bbJI ,返回

16、返回休息休息第36頁/共51頁 3311112,113,113210210qbbMJI 21,011,102210210qbbMJI第37頁/共51頁線性四叉樹編碼線性四叉樹編碼在在M MQ Q碼的基礎上生成線性四叉樹的方法有兩種：碼的基礎上生成線性四叉樹的方法有兩種：(1)(1)自頂向下自頂向下(top-down)(top-down)的分割方法的分割方法: :按常規(guī)四叉樹按常規(guī)四叉樹的方法進行，并直接生成的方法進行，并直接生成M M碼；碼；(2)(2)從底向上從底向上(down-top)(down-top)的合并方法：首先按的合并方法：首先按M MQ Q碼的碼的升序排列方式依次檢查四個相鄰升

17、序排列方式依次檢查四個相鄰M M碼對應的屬性值，碼對應的屬性值，如果相同，則合并為一個大塊，否則，存儲四個格如果相同，則合并為一個大塊，否則，存儲四個格網(wǎng)的參數(shù)值（網(wǎng)的參數(shù)值（ M MQ Q碼、深度、屬性值）。第一輪合并碼、深度、屬性值）。第一輪合并完成后，再依次檢查四個大塊的值（此時，僅需檢完成后，再依次檢查四個大塊的值（此時，僅需檢查每個大塊中的第一個值），若其中有一個值不同查每個大塊中的第一個值），若其中有一個值不同或某子塊已存儲，則不作合并而記盤。通過上述方或某子塊已存儲，則不作合并而記盤。通過上述方法，直到?jīng)]有能夠合并的子塊為止。法，直到?jīng)]有能夠合并的子塊為止。返回返回休息休息第38

18、頁/共51頁自上而下的線性四叉樹編碼過程自上而下的線性四叉樹編碼過程返回返回休息休息第39頁/共51頁（二）基于十進制的（二）基于十進制的MortonMorton碼碼 方法方法1: 將四進制的將四進制的MQ碼轉(zhuǎn)換成十進制的碼轉(zhuǎn)換成十進制的MD例如：例如： 1001415434333dM 100149414221dM第40頁/共51頁（二）基于十進制的（二）基于十進制的MortonMorton碼碼 方法方法2: 按位操作按位操作 步驟步驟: 1)將十進制的行列號轉(zhuǎn)換成二進制數(shù)將十進制的行列號轉(zhuǎn)換成二進制數(shù) 2)行列交叉得到二進制的行列交叉得到二進制的Morton碼碼 3)將二進制的將二進制的Mo

19、rton碼轉(zhuǎn)換成十進制的碼轉(zhuǎn)換成十進制的Morton碼碼第41頁/共51頁（二）基于十進制的（二）基于十進制的MortonMorton碼碼 2102101117,1015JI例如：已知行列號例如：已知行列號I=5,J=7，求，求十進制的十進制的MortonMorton碼碼 10012345255212121202121110111dM第42頁/共51頁 4 - 5 4 - 5 柵 格 數(shù) 據(jù) 結(jié) 構(gòu)柵 格 數(shù) 據(jù) 結(jié) 構(gòu)四叉樹編碼的優(yōu)點：四叉樹編碼的優(yōu)點：1 1）陣列各部分的）陣列各部分的分辯率是可變的分辯率是可變的，邊界復雜部分四叉樹較高即分級多，分辯率也高，而不需表示許多細節(jié)的部分則分級少，分辯率低，因而既可精確表示圖形結(jié)構(gòu)又可減少存貯量；，邊界復雜部分四叉樹較高即分級多，分辯率也高，而不需表示許多細節(jié)的部分則分級少，分辯率低，因而既可精確表示圖形