第3章+GIS的數(shù)據結構

1、http:/www.esrichina- 有位置，無方向、寬度和長度；有位置，無方向、寬度和長度； 抽象的點抽象的點美國佛羅里達洲地震監(jiān)測站2002年9月該洲可能的500個地震位置 有長度，但無寬度和高度有長度，但無寬度和高度 用來描述線狀實體，通常在網絡分析中使用較多用來描述線狀實體，通常在網絡分析中使用較多 度量實體距離度量實體距離香港城市道路網分布香港城市道路網分布 具有長和寬的目標具有長和寬的目標 通常用來表示自然或人工的封閉多邊形通常用來表示自然或人工的封閉多邊形 一般分為連續(xù)面和不連續(xù)面一般分為連續(xù)面和不連續(xù)面中國土地利用分布圖（不連續(xù)面）中國土地利用分布圖（不連續(xù)面）連續(xù)變化曲面

2、連續(xù)變化曲面：如地形：如地形起伏，整個曲面在空間起伏，整個曲面在空間上曲率變化連續(xù)。上曲率變化連續(xù)。不連續(xù)變化曲面不連續(xù)變化曲面：如土壤、：如土壤、森林、草原、土地利用等，森林、草原、土地利用等，屬性變化發(fā)生在邊界上，屬性變化發(fā)生在邊界上，面的內部是同質的。面的內部是同質的。有長、寬、高的目標有長、寬、高的目標通常用來表示人工或自然的三維目標，如通常用來表示人工或自然的三維目標，如建筑、礦體等三維目標建筑、礦體等三維目標香港理工大學校園建筑香港理工大學校園建筑 來源于地形等高線圖的數(shù)字化，已建立的數(shù)來源于地形等高線圖的數(shù)字化，已建立的數(shù)字高程模型字高程模型(DEM)和其他實測的地形數(shù)據等。和其

3、他實測的地形數(shù)據等。 來源于由各類純數(shù)據通過調查、推理、分析來源于由各類純數(shù)據通過調查、推理、分析和總結得到的和總結得到的有關數(shù)據的數(shù)據有關數(shù)據的數(shù)據，例如數(shù)據來源、，例如數(shù)據來源、數(shù)據權屬、數(shù)據產生的時間、數(shù)據精度、數(shù)據數(shù)據權屬、數(shù)據產生的時間、數(shù)據精度、數(shù)據分辨率、源數(shù)據比例尺、數(shù)據轉換方法等。分辨率、源數(shù)據比例尺、數(shù)據轉換方法等。類型數(shù)據類型數(shù)據：居民點、交通線、土地類型分布等：居民點、交通線、土地類型分布等面域數(shù)據面域數(shù)據：多邊形中心點、行政區(qū)域界限和行政單元：多邊形中心點、行政區(qū)域界限和行政單元網絡數(shù)據網絡數(shù)據：道路交叉點、街道和街區(qū)等：道路交叉點、街道和街區(qū)等樣本數(shù)據樣本數(shù)據：氣象

4、站、航線和野外樣方的分布區(qū)等：氣象站、航線和野外樣方的分布區(qū)等曲面數(shù)據曲面數(shù)據 ：高程點、等高線和等值區(qū)域：高程點、等高線和等值區(qū)域文本數(shù)據文本數(shù)據：如地名、河流名和區(qū)域名稱：如地名、河流名和區(qū)域名稱符號數(shù)據符號數(shù)據：點狀符號、線狀符號和面狀符號等：點狀符號、線狀符號和面狀符號等圖象數(shù)據圖象數(shù)據：航空、航天圖象，野外攝影照片等：航空、航天圖象，野外攝影照片等多媒體數(shù)據多媒體數(shù)據：音頻數(shù)據、視頻數(shù)據：音頻數(shù)據、視頻數(shù)據拓撲鄰接拓撲鄰接： 元素之間的拓撲關系。元素之間的拓撲關系。拓撲關聯(lián)拓撲關聯(lián)： 元素之間的拓撲關系元素之間的拓撲關系。拓撲包含拓撲包含： 元素之間的拓撲關系。元素之間的拓撲關系。不

5、不 同同 類類同同 類類同類不同級同類不同級基本的拓撲關系基本的拓撲關系N11256473P1P3P2P4N4N3N5N2拓撲鄰接拓撲鄰接：N1/ /N2 , ,N1/ /N3 , ,N1/ /N4 ; ;P1/ /P3 ; ;P2/ /P3拓撲關聯(lián)拓撲關聯(lián)：N1/ /1、3 、6 ；P1/ /1、5 、6 拓撲包含拓撲包含：P3與與P4相鄰相鄰相交相交重合相離相離包含包含點點點點點點線線點點面面線線面面面面面面線線線線復雜的拓撲關系復雜的拓撲關系（1）確定地理實體間的相對空間位置，無需坐）確定地理實體間的相對空間位置，無需坐標和距離標和距離（2）利于空間要素查詢）利于空間要素查詢（3）重建地

6、理實體）重建地理實體面域與弧段的拓撲關系面面 域域弧弧 段段P P1 1a, b, c, -ga, b, c, -gP P2 2b, d, fb, d, fP P3 3c, f, ec, f, eP P4 4g g結點與弧段的拓撲關系結點與弧段的拓撲關系結結 點點弧弧 段段A Aa, c, ea, c, eB Ba, d, ba, d, bC Cd, e, fd, e, fD Db, f, cb, f, cE Eg g 弧段與結點的拓撲關系弧段與結點的拓撲關系弧弧 段段結結 點點a aA , BA , Bb bB , DB , Dc cD , AD , Ad dB , CB , Ce eC ,

7、 AC , Af fC , DC , Dg gE , EE , E弧段與面域的拓撲關系弧段與面域的拓撲關系弧段弧段 左鄰面左鄰面 右鄰面右鄰面b bP2P2 P1 P1c cP3P3 P1 P1d dP0P0 P2 P2e eP0P0 P3 P3f fP3P3 P2 P2g gP1P1abcdefgACBDEP4P1P2P3- disjoint- inside- touch- equals- covers- overlapAA A BABABABABABABABABABAI, A的內部和的內部和B的內部的交，記作的內部的交，記作BA A的內部和的內部和B的邊界的交，記作的邊界的交，記作BA A

8、的內部和的內部和B的的外部外部的交，記作的交，記作BA A的邊界和的邊界和B的內部的交，記作的內部的交，記作 BA A的邊界和的邊界和B的邊界的交，記作的邊界的交，記作BA A的邊界和的邊界和B的的外部外部的交，記作的交，記作BA A的外部和的外部和B的內部的交，記作的內部的交，記作 BA A的外部和的外部和B的邊界的交，記作的邊界的交，記作BA A的外部和的外部和B的外部的交，記作的外部的交，記作BA 111100100111111111100100111100010001111011001111001001100110111111110100面與面面與面間有效間有效的拓撲的拓撲關系共關系共

9、有有8個個111100100101110100111110100100111100111101100101111100111111100100110101100100111100110111100111101100101111100111111111101101101111101111111101101101111111101111101111111線與面線與面間有效間有效的拓撲的拓撲關系共關系共有有19個個1111001001111001011011001101111001101001001111011001111111001111110011001110010011110011011010

10、01110111001110101001111111001111111101100111101101101101110111101110101101111111101111101010100線與線線與線間有效間有效的拓撲的拓撲關系共關系共有有33個，個，這里只這里只給出了給出了21個個 九交模型的缺點：九交模型的缺點： 九交模型中的外部太大。對于一個面積有限九交模型中的外部太大。對于一個面積有限的空間目標而言，它的外部是無限的。這導致的空間目標而言，它的外部是無限的。這導致任意兩個目標的外部的交總是非空。任意兩個目標的外部的交總是非空。ABABBA11110010011110010011110

11、0100C 外部的無限性，導致目標的外部與邊界和內外部的無限性，導致目標的外部與邊界和內部是線性相關的，使得外部在九交模型中的作部是線性相關的，使得外部在九交模型中的作用不是很明顯。用不是很明顯。 只能描述簡單目標（不帶洞而單一的實體）只能描述簡單目標（不帶洞而單一的實體）間的拓撲關系，而不能描述復雜目標（帶洞或間的拓撲關系，而不能描述復雜目標（帶洞或由幾個分離目標組成的目標）間的拓撲關系。由幾個分離目標組成的目標）間的拓撲關系。 空間數(shù)據的拓撲關系比較復雜，通過分析知道空間數(shù)據的拓撲關系比較復雜，通過分析知道，在這些拓撲關系中，在這些拓撲關系中有些關系要存儲，有些關系有些關系要存儲，有些關系

12、不必要存儲不必要存儲，而是在應用時，通過實時操作運算，而是在應用時，通過實時操作運算求解出來。求解出來。但通過操作運算求解拓撲關系所要計但通過操作運算求解拓撲關系所要計算工作量較大。算工作量較大。 歐幾里德距離歐幾里德距離 曼哈頓距離曼哈頓距離 時間距離時間距離 在相對較小的地理空間中，采用笛卡兒坐標系，定義地理在相對較小的地理空間中，采用笛卡兒坐標系，定義地理空間中所有點的集合，組成笛卡兒平面，記為空間中所有點的集合，組成笛卡兒平面，記為R2。在。在R2中，任中，任意兩點（意兩點（i i,i i）和（）和（j j,j j）間的）間的歐幾里德距離歐幾里德距離d（i，j）如下：如下： 地理空間中

13、所有點間的歐幾里德距離函數(shù)組成度量空間地理空間中所有點間的歐幾里德距離函數(shù)組成度量空間s。度量空間具有如下特點：度量空間具有如下特點： （1）如）如i和和j代表不同的點，則，代表不同的點，則，d(i，j)0的條件在歐幾里的條件在歐幾里德空間中總得到滿足。德空間中總得到滿足。 （2）對稱性，即，）對稱性，即，d(i，j) =d(j，i)。 （3）三角不等性，即，給定）三角不等性，即，給定s中的任意中的任意3個距離個距離m，n，l，則，則存在如下關系式：存在如下關系式： mnl22),(jijiyyxxjid 曼哈頓距離曼哈頓距離是指兩點在南北方向上的距是指兩點在南北方向上的距離加上在東西方向上的

14、距離，即：離加上在東西方向上的距離，即： 曼哈頓距離又稱為出租車距離。曼哈頓曼哈頓距離又稱為出租車距離。曼哈頓距離的度量性質與歐氏距離的性質相同，保距離的度量性質與歐氏距離的性質相同，保持對稱性和三角不等式成立。持對稱性和三角不等式成立。 曼哈頓距離只適用于討論具有規(guī)則布局曼哈頓距離只適用于討論具有規(guī)則布局的城市街道的相關問題。的城市街道的相關問題。jijiyyxxjid),( 時間距離時間距離（旅行時間距離）是根據從空間中一（旅行時間距離）是根據從空間中一點到達另一點所需時間進行度量的。時間距離不具點到達另一點所需時間進行度量的。時間距離不具有前述歐幾里德距離和曼哈頓距離的度量空間性質，有前

15、述歐幾里德距離和曼哈頓距離的度量空間性質，即其對稱性，三角形不等式不一定成立。即其對稱性，三角形不等式不一定成立。 矢量和柵格結構矢量和柵格結構是計算機描述空間實體的兩種是計算機描述空間實體的兩種最基本的方式。最基本的方式。 Yijx1 y1x2 y2xi yixn yn定位明顯，屬性隱含定位明顯，屬性隱含 點 （點 （ P o i n t ） ： 又 稱 為 元 素又 稱 為 元 素（Element），是一個數(shù)據點，具有），是一個數(shù)據點，具有一對（一對（x、y）坐標和至少一個屬性。）坐標和至少一個屬性。 線（線（Line）：是具有相同屬性的點的是具有相同屬性的點的軌跡，由一個坐標對序列表示，

16、坐標軌跡，由一個坐標對序列表示，坐標對順序與線的開頭有關，線上每個點對順序與線的開頭有關，線上每個點有不多于二個鄰點。有不多于二個鄰點。 面（面（Area）：是具有相同屬性的點的是具有相同屬性的點的軌跡，以（軌跡，以（x、y）坐標對的集合表示，）坐標對的集合表示，起點坐標與終點坐標相同，面內點具起點坐標與終點坐標相同，面內點具有至少一個相同屬性。有至少一個相同屬性。 區(qū)域（區(qū)域（Region）：空間上相鄰或重疊空間上相鄰或重疊的點、線、面要素可以按一定的地理的點、線、面要素可以按一定的地理意義組成區(qū)域。意義組成區(qū)域。(X,Y)(X2,Y2)(X3,Y3)(X4,Y4)(X5,Y5)LinePo

17、int(X5,Y5)(X,Y)(X2,Y2)(X4,Y4)(X3,Y3)Polygon(X,Y)p 點目標點目標（x,y) p 線目標線目標 (x1y1,x2y2,.xnyn) p 面目標面目標 (x1y1,x2y2,.xnyn,x1y1)優(yōu)點：優(yōu)點：（1）數(shù)據結構簡單，直觀，便于用戶接受；）數(shù)據結構簡單，直觀，便于用戶接受；（2）便于系統(tǒng)的維護和更新。）便于系統(tǒng)的維護和更新。缺點：缺點：（1）數(shù)據冗余度大，如多邊形公共邊重復存儲，但）數(shù)據冗余度大，如多邊形公共邊重復存儲，但沒有存儲多邊形之間的關系。相鄰多邊形易產生偽沒有存儲多邊形之間的關系。相鄰多邊形易產生偽多邊形。解決的辦法是建立多邊形邊

18、界表；多邊形。解決的辦法是建立多邊形邊界表；（2）缺乏拓撲信息，如鄰域信息等，不便于拓撲分）缺乏拓撲信息，如鄰域信息等，不便于拓撲分析（臨時建立拓撲關系）；析（臨時建立拓撲關系）；（3）對島處理能力差，無法建立外多邊形的關系。）對島處理能力差，無法建立外多邊形的關系。起點起點終點終點中間點中間點弧段弧段1弧段弧段3弧段弧段2弧段弧段4點點:面面:弧弧: 雙重獨立地圖編碼，雙重獨立地圖編碼，簡稱簡稱DIME結構（結構（Dual Independent Map Encoding）。它是由美國人口調查局。它是由美國人口調查局建立起來的為人口調查目的而設計的一種拓撲編碼方法，是建立起來的為人口調查目的

19、而設計的一種拓撲編碼方法，是一種把幾何量度信息（直角坐標）與拓撲邏輯信息結合起來一種把幾何量度信息（直角坐標）與拓撲邏輯信息結合起來的系統(tǒng)。也可用于土地利用等多種信息系統(tǒng)的編輯和分析，的系統(tǒng)。也可用于土地利用等多種信息系統(tǒng)的編輯和分析，是是GIS發(fā)展早期使用的一種拓撲編碼方式。發(fā)展早期使用的一種拓撲編碼方式。 DIME文件的基本元素是連接兩個端點（結點）的一條文件的基本元素是連接兩個端點（結點）的一條線段（街段）、線段始結點和終結點標識符、這兩個結點的線段（街段）、線段始結點和終結點標識符、這兩個結點的坐標及線段兩側的區(qū)域代碼（左區(qū)號和右區(qū)號）坐標及線段兩側的區(qū)域代碼（左區(qū)號和右區(qū)號）。在這種

20、結在這種結構中，線段通常被認為是直線型的，復雜的曲線由一系列逼構中，線段通常被認為是直線型的，復雜的曲線由一系列逼近曲線的直線段來表示。結點與結點或者面域與面域之間為近曲線的直線段來表示。結點與結點或者面域與面域之間為鄰接關系，而結點與線段或面域與線段之間為關聯(lián)關系，利鄰接關系，而結點與線段或面域與線段之間為關聯(lián)關系，利用這種拓撲關系來組織數(shù)據，可以有效地進行數(shù)據存儲正確用這種拓撲關系來組織數(shù)據，可以有效地進行數(shù)據存儲正確性檢查，同時便于對數(shù)據進行更新和檢索。性檢查，同時便于對數(shù)據進行更新和檢索。 曲面是指連續(xù)分布現(xiàn)象的覆蓋表面，曲面是指連續(xù)分布現(xiàn)象的覆蓋表面，具有這種覆蓋具有這種覆蓋表面的要

21、素有地形、降水量、溫度、磁場等。表面的要素有地形、降水量、溫度、磁場等。表示和存表示和存儲這些要素的基本要求是必須便于連續(xù)現(xiàn)象在任一點的儲這些要素的基本要求是必須便于連續(xù)現(xiàn)象在任一點的內插計算，因此常采用不規(guī)則三角網來擬合連續(xù)分布現(xiàn)內插計算，因此常采用不規(guī)則三角網來擬合連續(xù)分布現(xiàn)象的覆蓋表面，稱為象的覆蓋表面，稱為TIN(Triangulated Irregular Network)數(shù)據結構數(shù)據結構。 這種基于這種基于TIN的曲面數(shù)據結構，通常用于數(shù)字地形的的曲面數(shù)據結構，通常用于數(shù)字地形的表示，或者按照曲面要素的實測點分布，將它們連成三表示，或者按照曲面要素的實測點分布，將它們連成三角網，角

22、網，三角網中的每個三角形要求盡量接近等邊形狀，三角網中的每個三角形要求盡量接近等邊形狀，并保證由最臨近的點構成的三角形，即三角形的邊長之并保證由最臨近的點構成的三角形，即三角形的邊長之和最小。和最小。在所有可能的三角網中，狄洛尼在所有可能的三角網中，狄洛尼(Delaunay)三三角網在地形擬合方面表現(xiàn)最為出色，因此常用于角網在地形擬合方面表現(xiàn)最為出色，因此常用于TIN的生的生成。成。泰森多邊形（泰森多邊形（Thiessen polygon）泰森多邊形是荷蘭氣候學家泰森多邊形是荷蘭氣候學家A.H.Thiessen提出的提出的一種計算區(qū)域降雨量的方法。在某個區(qū)域內雨量觀一種計算區(qū)域降雨量的方法。在

23、某個區(qū)域內雨量觀測站總是以孤立點散布的，測站總是以孤立點散布的，在地圖上作所有相鄰觀在地圖上作所有相鄰觀測點連線的垂直平分線，由這些平分線構成的包圍測點連線的垂直平分線，由這些平分線構成的包圍每個觀測點的多邊形就是所謂的泰森多邊形。每個觀測點的多邊形就是所謂的泰森多邊形。在泰在泰森多邊形的邊界上任取一點，到相鄰兩個觀測點的森多邊形的邊界上任取一點，到相鄰兩個觀測點的距離是相同的，距離是相同的，而多邊形內的任意點到該多邊形內而多邊形內的任意點到該多邊形內的觀測點距離最近。的觀測點距離最近。阜陽春運：車站吸引區(qū)劃分阜陽春運：車站吸引區(qū)劃分 基于基于Voronoi圖的九交模型圖的九交模型 每一個空間

24、對象的每一個空間對象的Voronoi圖都可以被分成三部分，即圖都可以被分成三部分，即Voronoi區(qū)域，空間對象的邊界，空間對象的內部。區(qū)域，空間對象的邊界，空間對象的內部。 V9I模模型用對象的型用對象的Voronoi區(qū)域代替九交模型中的外部，而對象的區(qū)域代替九交模型中的外部，而對象的邊界和內部與九交模型保持一致。邊界和內部與九交模型保持一致。V9I定義：定義： VVVVVVBABABABABABABABABA 若兩個空間對象相鄰時，若兩個空間對象相鄰時， 非空；若被其它目標隔開，非空；若被其它目標隔開，則則 為空，因而空為空，因而空V9I模型用可以區(qū)分相鄰和相離兩種模型用可以區(qū)分相鄰和相離

25、兩種拓撲關系，而拓撲關系，而9交模型把二者均描述為相離。交模型把二者均描述為相離。VVBA VVBA Real worldGridPointLineAreaValue=0=1=2=3RowColumnTrianglesHexagons點點線線面面柵格數(shù)據結構：坐標系與描述參數(shù)柵格數(shù)據結構：坐標系與描述參數(shù)Y：列：列X：行：行西南角格網坐標西南角格網坐標（XWS，YWS）格網分辨率格網分辨率 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 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 0 0

26、 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 （a）點）點 （b）線）線 （c）面）

27、面SPOT XS 20m*20m 牡丹水庫牡丹水庫band G, R, IRA.OBC中心點中心點法法重要性重要性法法長度占優(yōu)法長度占優(yōu)法面積占優(yōu)面積占優(yōu)法法柵格結構數(shù)據中混合像元的處理柵格結構數(shù)據中混合像元的處理方案方案二二方案方案一一：縮小柵格單元的面積縮小柵格單元的面積0 1 2 3 colrow32100150 1 2 3 colrow32100150 1 2 3 colrow32100150150 1 2 3 colrow32100150 1 2 3 colrow32100150 1 2 3 col015row32100 1 2 3 col015row3210RowRow prime

28、SpiralPeanoGrayHilbertCantor/DiagonalSierpinski/Triangle0000444022288882222888824228888244288882440488804404488040044440直接柵格編碼直接柵格編碼鏈碼鏈碼(chain Encoding)游程長編碼游程長編碼(Run_length Encoding)四叉樹編碼四叉樹編碼(quad_tree Encoding) 直接編碼就是將柵格數(shù)據看作一個數(shù)據矩陣，逐行直接編碼就是將柵格數(shù)據看作一個數(shù)據矩陣，逐行（或逐列）逐個記錄代碼，可以每行從左到右逐像元記錄，（或逐列）逐個記錄代碼，可以每行

29、從左到右逐像元記錄，也可奇數(shù)行從左到右而偶數(shù)行由右向左記錄，為了特定的也可奇數(shù)行從左到右而偶數(shù)行由右向左記錄，為了特定的目的還可采用其他特殊的順序。目的還可采用其他特殊的順序。 0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 30，2，2，5，5，5，5，5；2，2，2，2，2，5，5，5；2，2，2，2，3，3，5，5；0，0，2，3，3，3，5，5；0，0，3，3，3，3，5，3；0，0，0，3，3，3

30、，3，3；0，0，0，0，3，3，3，3；0，0，0，0，0，3，3，3。由由起點位置起點位置和和一系列在基本方向的單位矢量一系列在基本方向的單位矢量給出每給出每個后續(xù)點相對其前繼點的可能的個后續(xù)點相對其前繼點的可能的8 8個基本方向之一表個基本方向之一表示。示。8 8個基本方向自個基本方向自0 0開始按逆時針方向代碼分別開始按逆時針方向代碼分別為為0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7。單位矢量的長度默認。單位矢量的長度默認為一個柵格單元。為一個柵格單元。12345076001 0 767 01 1 0 0鏈碼編碼鏈碼編碼： 2，2 ，6 ，7，6，0，6，51234

31、50760 5 0 0 0 0 0 00 0 5 0 0 0 0 00 0 0 0 0 0 0 00 5 0 0 0 0 0 00 0 5 5 0 0 0 00 0 0 5 0 0 0 00 0 5 0 0 0 0 00 0 0 0 0 0 0 0鏈碼編碼示例鏈碼編碼示例(1)只在各行（或列）數(shù)據的只在各行（或列）數(shù)據的屬性屬性發(fā)生變化時依次發(fā)生變化時依次記錄該記錄該屬性屬性以及相同以及相同屬性重復的個數(shù)（游程編碼）屬性重復的個數(shù)（游程編碼）；0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50

32、 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3沿沿行行方向進行編碼方向進行編碼：( 0，1），），（2，2），（），（5，5）；（）；（2，5），），（5，3）；（）；（2，4），（），（3，2），），（5，2）；（）；（0，2），（），（2，1），），（3，3），（），（5，2）；（）；（0，2），），（3，4），（），（5，1），（），（3，1）；）；（0，3），（），（3，5）；（）；（0，4），），（3，4）；（）；（0，5），（），（3，3）。）。（2）逐個記錄各行（或列）逐個記錄各行（或列）屬性屬性發(fā)生變化的位置和發(fā)生變化的位置和相應相應屬

33、性屬性。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3沿列方向進行編碼沿列方向進行編碼：( 1，0），），（2，2），（），（4，0）；（）；（1，2），），（4，0）；（）；（1，2），（），（5，3），），（6，0）；（）；（1，5），（），（2，2），），（4，3），（），（7，0）；（）；（1，5），），（2，2），（），（3，3），（），（8，0）；）；（1，5），（），（3，3）；（）；（1

34、，5），），（6，3）；（）；（1，5），（），（5，3）。）。 采用方形區(qū)域作為記錄單元，數(shù)據編碼由采用方形區(qū)域作為記錄單元，數(shù)據編碼由初始位初始位置行列號加上半徑置行列號加上半徑，再加上記錄單元的，再加上記錄單元的屬性屬性組成。組成。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3（1 1，1 1，1 1，0 0），（），（1 1，2 2，2 2，2 2），），（1 1，4 4，1 1，5 5），（）

35、，（1 1，5 5，1 1，5 5），），（1 1，6 6，2 2，5 5），（），（1 1，8 8，1 1，5 5）；）；（2 2，1 1，1 1，2 2），（），（2 2，4 4，1 1，2 2），），（2 2，5 5，1 1，2 2），（），（2 2，8 8，1 1，5 5）；）；（3 3，3 3，1 1，2 2），（），（3 3，4 4，1 1，2 2），），（3 3，5 5，2 2，3 3），（），（3 3，7 7，2 2，5 5）；）；（4 4，1 1，2 2，0 0），（），（4 4，3 3，1 1，2 2），），（4 4，4 4，1 1，3 3）；（）；（5 5，3 3，1 1

36、，3 3），），（5 5，4 4，2 2，3 3），（），（5 5，6 6，1 1，3 3），），（5 5，7 7，1 1，5 5），（），（5 5，8 8，1 1，3 3）；）；（6 6，1 1，3 3，0 0），（），（6 6，6 6，3 3，3 3）；）；（7 7，4 4，1 1，0 0），（），（7 7，5 5，1 1，3 3）；）；（8 8，4 4，1 1，0 0），（），（8 8，5 5，1 1，0 0）。）。 是根據柵格數(shù)據二維空間分布的特點，將空間區(qū)域是根據柵格數(shù)據二維空間分布的特點，將空間區(qū)域按照按照4個象限進行遞歸分割（個象限進行遞歸分割（2n2n，且，且n1），直），直到

37、子象限的數(shù)值單調為止，最后得到一棵四分叉的倒向到子象限的數(shù)值單調為止，最后得到一棵四分叉的倒向樹。四叉樹分解，各子象限大小不完全一樣，但都是同樹。四叉樹分解，各子象限大小不完全一樣，但都是同屬性屬性柵格單元組成的子塊，其中最上面的一個結點叫做柵格單元組成的子塊，其中最上面的一個結點叫做根結點根結點，它對應于整個圖形。不能再分的結點稱為，它對應于整個圖形。不能再分的結點稱為葉子葉子結點結點，可能落在不同的層上，該結點代表子象限單一的，可能落在不同的層上，該結點代表子象限單一的代碼，所有葉子結點所代表的方形區(qū)域覆蓋了整個圖形。代碼，所有葉子結點所代表的方形區(qū)域覆蓋了整個圖形。從上到下，從左到右為葉

38、子結點編號，最下面的一排數(shù)從上到下，從左到右為葉子結點編號，最下面的一排數(shù)字表示各子區(qū)的代碼。字表示各子區(qū)的代碼。 為了保證四叉樹分解能不斷的進行下去，要求圖形為了保證四叉樹分解能不斷的進行下去，要求圖形必須為必須為2n2n的柵格陣列。的柵格陣列。n 為極限分割次數(shù)，為極限分割次數(shù)，n1是四叉樹最大層數(shù)或最大高度。是四叉樹最大層數(shù)或最大高度。四叉樹編碼具有四叉樹編碼具有可變的分辨率可變的分辨率，并且有，并且有區(qū)域性質區(qū)域性質，壓縮數(shù)據靈活，許多運算可以在編碼數(shù)據上直接實壓縮數(shù)據靈活，許多運算可以在編碼數(shù)據上直接實現(xiàn)，大大地提高了運算效率，是優(yōu)秀的柵格壓縮編現(xiàn)，大大地提高了運算效率，是優(yōu)秀的柵格

39、壓縮編碼之一。碼之一。一幅一幅2n x 2n 柵格陣列的圖用四叉樹分割時，具有柵格陣列的圖用四叉樹分割時，具有的最大深度為的最大深度為n，即可分為，即可分為 0, 1 ,2 , 3 n 層層 四叉樹的特點四叉樹的特點例：一幅例：一幅23 23 的柵格陣列，它具有的最大深度的柵格陣列，它具有的最大深度為為3，可能層次分別為，可能層次分別為0，1，2，3。其中：第其中：第0層邊長上的最大柵格數(shù)為層邊長上的最大柵格數(shù)為2(3-0)8 第第1層邊長上的最大柵格數(shù)為層邊長上的最大柵格數(shù)為2(3-1)4 第第2層邊長上的最大柵格數(shù)為層邊長上的最大柵格數(shù)為2(3-2)2 第第3層邊長上的最大柵格數(shù)為層邊長上

40、的最大柵格數(shù)為2(3-3)10層1層2層3層（1）（2）（3）（4）（5）（6） （7）（8）（9） （10） （11） （12）（13）（14） （15） （16）（17） （18） （19）從上到下從上到下遞遞歸分割歸分割 ； 常規(guī)四叉樹除了記錄葉結點之外，還要記錄中間結常規(guī)四叉樹除了記錄葉結點之外，還要記錄中間結點。結點之間借助點。結點之間借助指針聯(lián)系指針聯(lián)系，每個結點需要用六個，每個結點需要用六個量表達，即四個葉結點指針、一個父結點指針和一量表達，即四個葉結點指針、一個父結點指針和一個結點的屬性或灰度值。這些指針不僅增加了數(shù)據個結點的屬性或灰度值。這些指針不僅增加了數(shù)據儲存量，而且增加

41、了操作的復雜性。儲存量，而且增加了操作的復雜性。在在GIS和圖象處理中不用常規(guī)四叉樹，而用線性四叉和圖象處理中不用常規(guī)四叉樹，而用線性四叉樹。樹。0 2 2 5 5 5 5 52 2 2 2 2 5 5 50 0 0 0 0 3 3 32 2 2 2 3 3 5 50 0 2 3 3 3 5 50 0 3 3 3 3 5 30 0 0 3 3 3 3 30 0 0 0 3 3 3 3 1112131415161718192021222324252627282930313233363738393435400 0 00 3 3 3 0 3 3 33 3 5 3 0 0 2 2 2 3 2 2 2

42、2 0 22 2 2 5 2 5 5 53 33 5 5西南東南西北東北 l線性四叉樹同常規(guī)四叉樹不同線性四叉樹同常規(guī)四叉樹不同線性四叉樹同常規(guī)四叉樹不同在于存儲方式不同。線性四叉樹同常規(guī)四叉樹不同在于存儲方式不同。在線性四叉樹中只記錄葉結點信息，如葉結點的在線性四叉樹中只記錄葉結點信息，如葉結點的位置、大小、格網值，不存儲中間結點。位置、大小、格網值，不存儲中間結點。線性四叉樹中僅對葉結點信息進行編碼，這種編線性四叉樹中僅對葉結點信息進行編碼，這種編碼號稱地址碼碼號稱地址碼(位置碼），以表示它所處的位置。位置碼），以表示它所處的位置。地址碼隱含了葉結點的位置和深度信息。地址碼隱含了葉結點的位

43、置和深度信息。0層1層2層3層（1）（2）（3）（4）（5）（6） （7）（8）（9） （10） （11） （12）（13）（14） （15） （16）（17） （18） （19）morton碼的求解方法碼的求解方法設十進制表示的行、列號在計算機內部的二進設十進制表示的行、列號在計算機內部的二進制數(shù)分別為制數(shù)分別為112211jijijijiMnnnn則十進制的則十進制的morton碼實際上是碼實際上是II、JJ的二進制的二進制交叉結合的結果，即交叉結合的結果，即)(),(121121jjjjJJiiiiIInnnn將得到的二進制數(shù)將得到的二進制數(shù)M轉換為十進制數(shù)就可以得轉換為十進制數(shù)就可以得

44、到相應的到相應的morton碼了。碼了。 I = 5 = 0 1 0 1 J = 7 = 0 1 1 1 Morton = 0 0 1 1 0 1 1 1 = (55)10MD碼的計算實例碼的計算實例例如，某柵格單元的行號例如，某柵格單元的行號 I=5，列號，列號 J=7， Morton碼的計算如下圖所示：碼的計算如下圖所示： （2）四叉樹的十進制編碼四叉樹的十進制編碼屬性值屬性值0 040 81120130141151160321361400440481490500510520560600位置碼位置碼000 001 010 011 100 101 110 111002 003 012 013

45、 102 103 112 113020 021 030 031 120 121 130 131022 023 032 033 122 123 132 133200 201 210 211 300 301 310 311202 203 212 213 302 303 312 313220 221 230 231 320 321 330 331222 223 232 233 322 323 332 333444454554 555541405505515400415 500510044054040 041 050 051 140 141 150 151004 005 014 015 104 105

46、 004 0050 12 374 5012345671234567I（X）K（Z）J（Y）直接柵格編碼直接柵格編碼：簡單直觀，是壓縮編碼方法的邏輯原簡單直觀，是壓縮編碼方法的邏輯原型（柵格文件）；型（柵格文件）；鏈碼鏈碼：壓縮效率較高，已接近矢量結構，對邊界的運壓縮效率較高，已接近矢量結構，對邊界的運算比較方便，但不具有區(qū)域性質，區(qū)域運算較難；算比較方便，但不具有區(qū)域性質，區(qū)域運算較難；游程長度編碼游程長度編碼：在很大程度上壓縮數(shù)據，又最大限度在很大程度上壓縮數(shù)據，又最大限度的保留了原始柵格結構，編碼解碼十分容易，十分適的保留了原始柵格結構，編碼解碼十分容易，十分適合于微機地理信息系統(tǒng)采用；合

47、于微機地理信息系統(tǒng)采用；塊碼和四叉樹編碼塊碼和四叉樹編碼：具有區(qū)域性質，又具有可變的分具有區(qū)域性質，又具有可變的分辨率，有較高的壓縮效率，四叉樹編碼可以直接進行辨率，有較高的壓縮效率，四叉樹編碼可以直接進行大量圖形圖象運算，效率較高，是很有前途的編碼方大量圖形圖象運算，效率較高，是很有前途的編碼方法。法。1.數(shù)據存儲量小數(shù)據存儲量小2.空間位置精度高空間位置精度高3.空間關系描述全面，對線空間關系描述全面，對線狀、網絡狀事物的分析方便狀、網絡狀事物的分析方便4.空間和屬性數(shù)據綜合查詢空間和屬性數(shù)據綜合查詢與更新方便與更新方便5.普通地圖可直接手工數(shù)字普通地圖可直接手工數(shù)字化化1.數(shù)據結構簡單數(shù)

48、據結構簡單2.多種地圖疊合分析方便多種地圖疊合分析方便3.容易描述邊界復雜、模糊容易描述邊界復雜、模糊的事物，便于處理三維連續(xù)的事物，便于處理三維連續(xù)表面表面4.能直接處理數(shù)字圖象信息能直接處理數(shù)字圖象信息5.能直接用柵格狀設備輸出能直接用柵格狀設備輸出圖形圖形缺點缺點缺點缺點1.數(shù)據儲存量大數(shù)據儲存量大2.空間位置精度低空間位置精度低3.難以表達線狀、網絡難以表達線狀、網絡狀的事物狀的事物4.輸出地圖不美觀輸出地圖不美觀5.普通地圖須按矢量方普通地圖須按矢量方式數(shù)字化式數(shù)字化1.數(shù)據結構復雜數(shù)據結構復雜2.多種地圖疊合分析較多種地圖疊合分析較困難困難3.邊界復雜模糊的事物邊界復雜模糊的事物難以描述難以描述4.不能直接處理數(shù)字圖不能直接處理數(shù)字圖象信息象信息根據用戶需求，確定數(shù)據項目根據用戶需求，確定數(shù)據項目根據數(shù)據項目，確定數(shù)據源根據數(shù)據項目，確定數(shù)據源數(shù)據分類和編碼數(shù)據分類和編碼確定數(shù)據模型和數(shù)據結構類型確定數(shù)據模型和數(shù)據結構類型數(shù)據輸入與編輯操作數(shù)據輸入與編輯操作地圖分層地圖分層1) 什么是