1、第二章 空間數據結構1第二章 空間數據結構 空間數據結構就是指空間數據的編排方式和組織關系，是指空間數據適合于計算機存儲、管理、處理的邏輯結構。換句話說，是指空間數據以什么形式在計算機中存儲和處理。 空間數據編碼是空間數據結構的實現，目的是將不同的空間實體按一定的數據結構轉換為適用于計算機存儲和處理的過程，不同的對象，其數據結構相差很大，同一對象，也可以用許多方式來組織數據，按不同的數據結構去處理，會得到截然不同的內容。2一種高效的數據結構應具備幾方面的要求：1、組織的數據能夠表示要素之間的層次關系，便于不同數據聯接和覆蓋；2、正確反映地理實體的空間排列方式和各實體間相互關系；3、便于存取和檢

2、索；4、節省存儲空間，減少數據冗余；5、存取速度快，在運算速度較慢的微機上要達到快速響應；6、具有足夠的靈活性，數據組織應具有插入新的數據、刪除或修改部分數據的基本功能。第二章 空間數據結構31、現實世界的認知過程一、空間認知模型現實世界數字世界觀察、抽象綜合取舍定義、編碼模型化概念世界以實體表達第二章 空間數據結構42、空間實體（地理實體）的概念一、空間認知模型 指自然界現象和社會經濟事件中不能再分割的單元，它是一個具體的、有概括性，復雜性，相對意義的概念。是一種在現實世界中不能再劃分為同類現象的現象。 如：城市、湖泊、道路，甚至是某種現象的度量結果，如高溫區，干旱區等。（1）定義第二章 空

3、間數據結構52、空間實體（地理實體）的概念一、空間認知模型 地理實體類別及實體內容的確定是從具體需要出發的，例如，在全國地圖上由于比例尺很小，武漢就是一個點，這個點不能再分割，可以把武漢定為一個空間實體，而在大比例尺的武漢市地圖上，武漢的許多房屋，街道都要表達出來，所以武漢必須再分割，不能作為一個空間實體，應將房屋，街道等作為研究的地理實體，由此可見，GIS中的空間實體是一個概括，復雜，相對的概念。（2）理解第二章 空間數據結構63、空間實體（地理實體）的描述空間數據一、空間認知模型 屬性特征（非定位數據）：用以描述事物或現象的特性，即用來說明“是什么”，如事物或現象的類別、等級、數量、名稱等

4、。屬性數據（非幾何數據）（1）基本特征第二章 空間數據結構73、空間實體（地理實體）的描述空間數據一、空間認知模型 空間特征（定位數據）：用以描述事物或現象的地理位置以及空間相互關系，又稱為幾何特征和拓撲特征，前者如界樁的經緯度，后者如中國、印度接壤。位置數據、定位數據（幾何數據），如用X,Y坐標來表示。 關系數據，如空間實體的鄰接、關聯、包含等，主要是指拓撲關系。（1）基本特征第二章 空間數據結構83、空間實體（地理實體）的描述空間數據一、空間認知模型 時間特征（時間尺度）：用以描述事物或現象隨時間的變化，例如人口數的逐年變化。時態數據（1）基本特征第二章 空間數據結構93、空間實體（地理實

5、體）的描述空間數據一、空間認知模型（2）實體類型5、復雜實體1、點狀實體2、線狀實體3、面狀實體4、體狀實體第二章 空間數據結構103、空間實體（地理實體）的描述空間數據一、空間認知模型（2）實體類型4）角點、節點Vertex：表示線段和弧段上的連接點。 1）實體點：用來代表一個實體。2）注記點：用于定位注記。3）內點：用于負載多邊形的屬性，存在于多邊形內。點實體 表示有特定位置的0維空間實體。第二章 空間數據結構11線狀實體包括：線段，邊界、鏈、弧段、網絡等。3、空間實體（地理實體）的描述空間數據一、空間認知模型（2）實體類型線實體 表示1維空間實體，具有相同屬性的點的軌跡，線或折線，由一系

6、列的有序坐標表示，并有如下特性：1）實體長度：從起點到終點的總長2）彎曲度：用于表示像道路拐彎時彎曲的程度。3）方向性：如：水流方向，上游下游， 公路，單、雙向之分。第二章 空間數據結構123、空間實體（地理實體）的描述空間數據一、空間認知模型（2）實體類型面實體 表示2維空間實體，表示平面區域大范圍連續分布的特征，是對湖泊、島嶼、地塊等一類現象的描述。在數據庫中由一封閉曲線加內點來表示。特征：1）面積范圍 2）周長3）獨立性或與其它地物相鄰如中國及其周邊國家4）內島嶼或鋸齒狀外形：如島嶼的海岸線封閉所圍成的區域。5）重疊性與非重疊性：如學校的分區，菜市場的服務范圍等都有可能出現交叉重疊現象，

7、而一個城市的各個城區一般說來不會出現重疊。 第二章 空間數據結構133、空間實體（地理實體）的描述空間數據一、空間認知模型（2）實體類型體實體 立體狀實體用于描述三維空間中的現象與物體，它具有長度、寬度及高度等屬性，立體狀實體一般具有以下一些空間特征：1）體積，如工程開控和填充的土方量。2）每個二維平面的面積。3）周長。4）內島。5）含有弧立塊或相鄰塊。6）斷面圖與剖面圖。第二章 空間數據結構143、空間實體（地理實體）的描述空間數據一、空間認知模型（2）實體類型維數實體類型代表地物零維點水井、污染源等。一維線、弧、鏈道路、公共設施網等。二維面、多邊形土壤、植被、巖石分類區、行政區劃等。三維體

8、地形，溫度第二章 空間數據結構153、空間實體（地理實體）的描述空間數據一、空間認知模型（2）實體類型實體類型組合 線-面：1、區域包含線：計算區域內線的密度，某省的水系分布情況。2、線通過區域：公路上否通過某縣。3、線環繞區域：區域邊界，搜索左右區域名稱，中國與哪些國家接壤。4、線與區域分離：距離。 第二章 空間數據結構163、空間實體（地理實體）的描述空間數據一、空間認知模型（2）實體類型實體類型組合 面-面：1、 包含：島,某省的湖泊分布。2、 相合：重疊，學校服務范圍與菜場服務范圍重疊區。3、 相交：劃分子區。4、 相鄰：計算相鄰邊界性質和長度，公共連接邊界。分離：計算距離。 FeCu

9、第二章 空間數據結構173、空間實體（地理實體）的描述空間數據一、空間認知模型（3）空間關系 空間關系的類型1）拓撲空間關系： 2）順序空間關系： （方向空間關系） 用上下左右、前后、東南西北等方向性名稱來描述空間實體的順序關系，算法復雜，至今沒有很好的解決方法。第二章 空間數據結構183、空間實體（地理實體）的描述空間數據一、空間認知模型（3）空間關系 空間關系的類型3）度量空間關系，主要指實體間的距離關系，遠近。 在地理空間中兩點間的距離有兩種度量方法。a、沿真實的地球表面進行,除與兩點的地理坐標有關外，還與所通過路徑的地形起伏有關，復雜,引入第二種。b、沿地球旋轉橢球體的距離量算。 距離

10、類別：歐氏距離（笛卡爾坐標系）、曼哈頓（出租車）距離、時間距離（緯度差）、大地測量距離（大地線）（沿地球大圓經過兩個城市中心的距離）。 第二章 空間數據結構193、空間實體（地理實體）的描述空間數據一、空間認知模型（3）空間關系 拓撲關系1）定義：指圖形保持連續狀態下變形，但圖形關系不變的性質。將橡皮任意拉伸，壓縮，但不能扭轉或折疊。 拓撲變換（橡皮變換）第二章 空間數據結構203、空間實體（地理實體）的描述空間數據一、空間認知模型（3）空間關系 拓撲關系第二章 空間數據結構非拓撲屬性（幾何）拓撲屬性（沒發生變化的屬性）兩點間距離一點指向另一點的方向弧段長度、區域周長、面積 等一個點在一條弧段

11、的端點一條弧是一簡單弧段（自身不相交）一個點在一個區域的邊界上一個點在一個區域的內部/外部一個點在一個環的內/外部一個面是一個簡單面一個面的連通性 面內任兩點從一點可在面的內部走向另一點213、空間實體（地理實體）的描述空間數據一、空間認知模型（3）空間關系 拓撲關系2）種類：第二章 空間數據結構a）關聯性： （不同類要素之間）結點與弧段：如V9與L5,L6,L3多邊形與弧段：P2與L3,L5,L2b）鄰接性： (同類元素之間)多邊形之間、結點之間。鄰接矩陣 重疊：- 鄰接：1 不鄰接：0223、空間實體（地理實體）的描述空間數據一、空間認知模型（3）空間關系 拓撲關系2）種類：第二章 空間數

12、據結構c）連通性：與鄰接性相類似，指對弧段連接的判別，如用于網絡分析中確定路徑、 街道是否相通。連通矩陣：重疊：- 連通：1不連通：0 233、空間實體（地理實體）的描述空間數據一、空間認知模型（3）空間關系 拓撲關系2）種類：第二章 空間數據結構d）方向性：一條弧段的起點、終點確定了弧段的方向。用于表達現實中的有向弧段，如城市道路單向，河流的流向等。e）包含性：指面狀實體包含了哪些線、點或面狀實體。f）區域定義：多邊形由一組封閉的線來定義。g）層次關系：相同元素之間的等級關系，武漢市有各個區組成。主要的拓撲關系：拓撲鄰接、拓撲關聯、拓撲包含。243、空間實體（地理實體）的描述空間數據一、空間

13、認知模型（3）空間關系 拓撲關系3）表達：第二章 空間數據結構拓撲關系具體可由4個關系表來表示：（1）面-鏈關系： 面 構成面的弧段（2）鏈-結點關系：鏈 鏈兩端的結點（3）結點-鏈關系：結點 通過該結點的鏈（4）鏈面關系：鏈 左面 右面253、空間實體（地理實體）的描述空間數據一、空間認知模型（3）空間關系 拓撲關系4）意義：第二章 空間數據結構對于數據處理和GIS空間分析具有重要的意義，因為：1）拓撲關系能清楚地反映實體之間的邏輯結構關系，它比幾何關系具有更大的穩定性，不隨地圖投影而變化。2）有助于空間要素的查詢，利用拓撲關系可以解決許多實際問題。如某縣的鄰接縣，-面面相鄰問題。又如供水管

14、網系統中某段水管破裂找關閉它的閥門，就需要查詢該線（管道）與哪些點（閥門）關聯。3）根據拓撲關系可重建地理實體。263、空間實體（地理實體）的描述空間數據一、空間認知模型第二章 空間數據結構1、描述的內容 3、數據類型 4、數據結構幾何數據（空間數據、圖形數據） 關系數據實體間的鄰接、關聯包含等相互關系 屬性數據各種屬性特征和時間元數據 矢量、柵格、TIN（專用于地表或特殊造型） RDBMS屬性表-采用MIS較成熟 空間元數據位置、形狀、尺寸 、關系識別碼（名稱）實體的角色、功能、行為、實體的衍生信息時間測量方法、編碼方法、空間參考系等 空間特征：地理位置和空間關系屬性特征名稱、等級、類別等時

15、間特征2、基本特征 274、空間認知三層模型一、空間認知模型第二章 空間數據結構空間概念模型空間邏輯模型物理模型現實世界矢量數據模型柵格數據模型矢-柵一體化數據模型層次模型網絡模型關系模型面向對象模型物理表示組織空間數據存取關于實體和實體間聯系的抽象概念集。表達概念模型中數據實體（或記錄）及其間的關系。描述數據在計算機中的物理組織、存儲路徑和數據庫結構。281、柵格數據的基本概念二、柵格數據結構第二章 空間數據結構柵格結構用密集正方形（或三角形，多邊形）將地理區域劃分為網格陣列（像元陣列）。位置由行，列號定義，屬性為柵格單元的值。點：由單個柵格表達。線：由沿線走向有相同屬性取值的一組相鄰柵格表

16、達。面：由沿線走向有相同屬性取值的一片柵格表達。 柵格數據表示的是二維表面上的地理數據的離散化數值。在柵格數據中，地表被分割為相互鄰接、規則排列的地塊，每個地塊與一個象元相對應。因此，柵格數據的比例尺就是柵格(象元)的大小與地表相應單元的大小之比，當象元所表示的面積較大時，對長度、面積等的量測有較大影響。每個象元的屬性是地表相應區域內地理數據的近似值，因而有可能產生屬性方面的偏差。291、柵格數據的基本概念二、柵格數據結構第二章 空間數據結構將工作區域的平面表象按一定分解力作行和列的規則劃分，形成許多格網，每個網格單元稱為象素(pixel)。根據所表示實體的表象信息差異，各象元可用不同的“灰度

17、值”來表示 。若每個象元規定N比特，則其灰度值范圍可在0到2N1之間；把白灰色黑的連續變化量化成8比特（bit），其灰度值范圍就允許在0255之間；若每個象元只規定1比特，則灰度值僅為0和1，這就是所謂二值圖像。點實體在柵格數據中表示為一個像元；線實體則表示為在一定方向上連接成串的相鄰像元集合；面實體由聚集在一起的相鄰像元集合表示。柵格數據結構實際上就是象元陣列，即象元按矩陣形式的集合(二維數組），柵格中的每個象元是柵格數據中最基本的信息存儲單元，其坐標位置可以用行號和列號確定。301、柵格數據的基本概念二、柵格數據結構第二章 空間數據結構點實體面實體線實體點實體線實體線實體面實體面實體312

18、、柵格數據層的概念二、柵格數據結構第二章 空間數據結構在柵格數據結構中，物體的空間位置就用其在笛卡爾平面網格中的行號和列號坐標表示，物體的屬性用像元的取值表示，每個像元在一個網格中只能取值一次，同一像元要表示多重屬性的事物就要用多個笛卡爾平面網格，每個笛卡爾平面網格表示一種屬性或同一屬性的不同特征。要表示多種專題屬性，必須分層存儲屬性數據柵格數據層323、柵格數據的組織方法二、柵格數據結構第二章 空間數據結構方法c：以層為基礎，每層內以多邊形為序記錄多邊形的屬性值和多邊形內各象元的坐標。節約用于存儲屬性的空間。將同一屬性的制圖單元的n個象元的屬性只記錄一次，便于地圖分析和制圖處理。 方法a：以

19、象元為記錄序列，不同層上同一象元位置上的各屬性值表示為一個列數組。N層中只記錄一層的象元位置，節約大量存儲空間，柵格個數很多。方法b：每層每個象元的位置、屬性一一記錄，結構最簡單，但浪費存儲。假設：每層的每個像元在數據庫中都是獨立單元，即數據值、像元和位置之間存在一對一的關系。334、柵格數據的獲取二、柵格數據結構第二章 空間數據結構（1）獲取方式1、手工獲取，專題圖上劃分均勻網格，逐個決定其網格代碼。2、掃描儀掃描專題圖的圖像數據行、列、顏色（灰度），定義顏色與屬性對應表，用相應屬性代替相應顏色，得到（行、列、屬性）再進行柵格編碼、存貯，即得該專題圖的柵格數據。3、由矢量數據轉換而來。4、遙

20、感影像數據，對地面景象的輻射和反射能量的掃描抽樣，并按不同的光譜段量化后，以數字形式記錄下來的象素值序列。5、格網DEM數據，當屬性值為地面高程，則為格網DEM，通過DEM內插得到。344、柵格數據的獲取二、柵格數據結構第二章 空間數據結構（2）柵格系統的確定 坐標系統的確定 表示具有空間分布特征的地理要素，不論采用什么編碼系統，什么數據結構(矢、柵)都應在統一的坐標系統下，而坐標系的確定實質是坐標系原點和坐標軸的確定。 由于柵格編碼一般用于區域性GIS，原點的選擇常具有局部性質，但為了便于區域的拼接，柵格系統的起始坐標應與國家基本比例尺地形圖公里網的交點相一致，并分別采用公里網的縱橫坐標軸作

21、為柵格系統的坐標軸。354、柵格數據的獲取二、柵格數據結構第二章 空間數據結構（2）柵格系統的確定 柵格單元的尺寸分辯率（resolution）Resolution is dependent on the grid cell size. Changing the resolution affects classification, area, perimeter, accuracy , etc. 12331122112311333332Real world Very Fine gridMedium grid Coarse grid364、柵格數據的獲取二、柵格數據結構第二章 空間數據結構（2）

22、柵格系統的確定 柵格單元的尺寸1）原則：應能有效地逼近空間對象的分布特征，又減少數據的冗余度。格網太大，忽略較小圖斑，信息丟失。一般講實體特征愈復雜，柵格尺寸越小，分辨率愈高，然而柵格數據量愈大（按分辨率的平方指數增加）計算機成本就越高，處理速度越慢。2）方法：用保證最小多邊形的精度標準來確定尺寸經驗公式： h為柵格單元邊長，Ai為區域所有多邊形的面積。374、柵格數據的獲取二、柵格數據結構第二章 空間數據結構（3）柵格代碼（屬性值）的確定中心歸屬法：每個柵格單元的值以網格中心點對應的面域屬性值確定。面積占優法：每個柵格單元的值以在該網格單元中占據最大面積的屬性384、柵格數據的獲取二、柵格數

23、據結構第二章 空間數據結構（3）柵格代碼（屬性值）的確定長度占優法：每個柵格單元的值以網格中線的大部分長度所對應的面域的屬性值來確定。重要性法：根據柵格內不同地物的重要性程度，選取特別重要的空間實體決定對應的柵格單元值。395、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（1）直接柵格編碼直接柵格編碼是最簡單最直觀而又非常重要的一種柵格結構編碼方法，通常稱這種編碼為圖像文件或柵格文件。直接編碼就是將柵格數據看作一個數據矩陣，逐行（或逐列）逐個記錄代碼。11112221113111222211331122222233312224444333122244443331222244443311

24、11224443311112221113111222211331122222233312224444333122244443331222244443311112244433405、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（1）直接柵格編碼 直接柵格編碼也可以奇數行從左到右而偶數行由右向左記錄，為了特定目的還可以采用其他特殊的順序。 特點：（1）最直觀、最基本的網格存貯結構，數據存儲簡單，沒有進行任何壓縮數據處理。（2）數據存儲量大，如果每個像元用一個字節表示，存儲空間為：m(行) n(列) 1(字節)。 415、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（1）直接柵格編碼

25、柵格數據量大，格網數多，由于地理數據往往有較強的相關性，即相鄰象元的值往往是相同的。所以，出現了各種柵格數據壓縮方法。數據壓縮是將數據表示成更緊湊的格式以減少存儲空間的一項技術。分為： 無損壓縮：在編碼過程中信息沒有丟失，經過解碼可恢復原有的信息-信息保持編碼。 有損壓縮：為最大限度壓縮數據，在編碼中損失一些認為不太重要的信息，解碼后，這部分信息無法恢復。-信息不保持編碼。 無壓縮編碼425、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼鏈式編碼行程編碼塊式編碼四叉樹編碼壓縮編碼435、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 鏈式編碼弗里曼鏈碼（

26、Freeman鏈碼）、邊界鏈碼將柵格數據（線狀地物面域邊界）表示為矢量鏈的記錄。1）首先定義一個3x3窗口，中間柵格的走向有8種可能，并將這8種可能0 7進行編碼。2）記下地物屬性碼和起點行、列后，進行追蹤，得到矢量鏈.445、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 鏈式編碼弗里曼鏈碼（Freeman鏈碼）、邊界鏈碼將柵格數據（線狀地物面域邊界）表示為矢量鏈的記錄。aaaaaaba鏈式編碼表屬性碼起點行起點列鏈碼a14556656b37576654323455、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 鏈式編碼弗里曼鏈碼（Freeman鏈碼

27、）、邊界鏈碼將柵格數據（線狀地物面域邊界）表示為矢量鏈的記錄。 優點：鏈碼可有效地存貯壓縮柵格數據，便于面積、長度、轉折方向和邊界、線段凹凸度的計算。 缺點：不易做邊界合并，插入操作、編輯較困難（對局部修改將改變整體結構）。區域空間分析困難，相鄰區域邊界被重復存儲。 465、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 行程編碼有相同屬性值的鄰近像元被合并在一起稱為一個行程，行程用一對數字表達：1）屬性碼，長度 (A,5),(B,3),(A,2),(B,2),(A,2),(B,2)2）屬性碼，點位 (A,1,1),(B,2,2),(A,3,1),(B,3,3),(A,4,

28、1),(B,4,3) A A A A A B B B A A B B A A B B 475、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 行程編碼按行（或列）記錄相同代碼的始末象元的列號（或行號）和相應的代碼，即按（起位、止位、屬性值）編碼，下圖可沿行方向進行行程編碼：156485、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 行程編碼只在各行（或列）數據的代碼發生變化時依次記錄該代碼以及相同代碼重重的個數。即按（屬性值和重復個數）編碼。53495、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 行程編碼逐個記錄各行（或列）代碼

29、發生變化的位置和相應的代碼，即按（位置，屬性值）編碼。505、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 行程編碼特點： 對于行程長度編碼，區域越大，數據的相關性越強，則壓縮越大，適用于類型區域面積較大的專題圖，而不適合于類型連續變化或類別區域分散的分類圖（壓縮比與圖的復雜程度成反比）。 這種編碼在柵格加密時，數據量不會明顯增加，壓縮率高，并最大限度地保留原始柵格結構，編碼解碼運算簡單，且易于檢索，疊加，合并等操作，這種編碼應用廣泛。515、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 塊式編碼行程編碼向二維擴展把多邊形范圍劃分成由象元組成的正方形

30、，然后對各個正方形進行編碼。塊式編碼數據結構中包括3個數字：塊的初始位置（行、列號）和塊的大小（塊包括的象元數），再加上記錄單元的代碼組成。 采用正方形區域作為記錄單元，每個記錄單元包括相鄰的若干柵格。 數據對組成：（初始行、列，半徑/大小，屬性值）525、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 塊式編碼行程編碼向二維擴展 1 2 3 4 5 6 7 8 1 0 4 4 7 7 7 7 72 4 4 4 4 4 7 7 73 4 4 4 4 8 8 7 7 4 0 0 4 8 8 8 7 75 0 0 8 8 8 8 7 86 0 0 0 8 8 8 8 87 0

31、0 0 0 8 8 8 88 0 0 0 0 0 8 8 8如：（1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7)依次掃描，編過的不重復。特點： 具有可變分辨率，即當屬性變化小時圖塊大，對于大塊圖斑記錄單元大，分辨率低，壓縮比高。 小塊圖斑記錄單元小，分辨率高，壓縮比低，所以，與行程編碼類似，隨圖形復雜程度的提高而提高分辨率。535、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼一種可變分辨率的非均勻網格系統。是最有效的柵格數據壓縮編碼方法之一 。1）基本思想：將2n2n象元組成的圖像(不足的用背景補上) 按四個象限進行遞歸分割，并判

32、斷屬性是否單一，單一：不分。 不單一：遞歸分割。AAABABBBAABBAABB0123545、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼2）四叉樹的樹形表示：用一棵倒立樹表示這種分割和分割結果。樹根結點：代表整個區域；葉結點（葉）：樹的每個結點有四棵子樹，為空的結點為葉結點，對應于區域分割時數值單調的子象限，即不能再分割的塊，圖斑大小取決于它在樹中的層數；結點（樹叉）：對應于區域分割時數值不單調的子象限。 每個樹叉均有4個分叉，叫四叉樹。555、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼16234511121378910

33、162345111312781097第3層第2層第1層第0層根結點葉結點結點（a）順序分解表示（b）樹形結構表示565、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼3）建立四叉樹結構的方式 自上而下方式(top-down) 從頂層開始，即先檢測全區域，其值不單一時再四劃分，直到數值或內容單一為止。 自下而上方式(bottom-up) 從底層開始，即以像元大小為結點，每記錄四個結點時，即生成父結點。575、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼4）四叉樹結構類型根據四叉樹存儲結構的不同，可以將四叉樹結構類型分為: 指針四叉

34、樹 線性四叉樹585、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼5）編碼方法：a、常規四叉樹（指針四叉樹）記錄這棵樹的葉結點外，中間結點，結點之間的聯系用指針聯系，每個結點需要6個變量：父結點指針、四個子結點的指針和本結點的屬性值。595、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼5）編碼方法a、常規四叉樹（指針四叉樹）SW2SE3NE1NW0根結點結點葉結點012310111213120121122123指針四叉樹的分解過程及編碼88023112110111213605、柵格數據編碼方法二、柵格數據結構第二章 空間數據結

35、構（2）壓縮編碼 四叉樹編碼5）編碼方法：a、常規四叉樹（指針四叉樹）特點：指針不僅增加了數據的存儲量，還增加了操作的復雜性：如層次數（分割次數）由從父結點移到根結點的次數來確定，結點所代表的圖像塊的位置需要從根節點開始逐步推算下來。所以，常規四叉樹并不廣泛用于存儲數據，其價值在于建立索引文件，進行數據檢索。615、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼5）編碼方法：b、線性四叉樹線性四叉樹編碼為美國馬里蘭大學地理信息系統中采用的編碼方式，具有四叉樹的形式，用指針四叉樹方式組織數據，但不用指針四叉樹方式存儲數據。基本思想：它不記錄中間節點和使用指針，僅記

36、錄葉節點，并用地址碼表示葉節點的位置。因此，其編碼包括葉節點的地址碼和本節點的屬性或灰度值，并且地址碼隱含了葉節點的位置和深度信息。625、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼5）編碼方法：b、線性四叉樹最常見的地址碼是四進制或十進制的Morton碼。基于深度和層次的線性四叉樹編碼：記錄每個葉節點的地址和屬性值。其中地址包括兩部分，以32位二進制數表示： 0 0 0 00 0 0 1 0 0 1 0 0 0 1 1深度（4位）路徑（28位）從葉節點到根節點的路徑0231路徑：011SE 000SW 102NW深度：00113第三層635、柵格數據編碼方

37、法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼5）編碼方法：b、線性四叉樹四進制地址碼(MQ碼) MQ碼是一串數字組成，每分割一次增加一位數，其中每位數字都是不大于3的四進制數。 A、分割一次，增加一位數字，大分割在前，小分割在后。所以，碼的位數表示分割的次數。 B、每一個位均是不大于3的四進制數，表達位置。0123AAAAA BBBAABBA AABB03BA645、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼5）編碼方法：b、線性四叉樹四進制地址碼(MQ碼)320？1320自上而下655、柵格數據編碼方法二、柵格數據結構第二章 空間數據結

38、構（2）壓縮編碼 四叉樹編碼5）編碼方法：b、線性四叉樹四進制地址碼(MQ碼)MQ碼計算公式：MQ = 2Ib+Jb 公式中Ib、Jb分別為柵格單元行列號的二進制數， Ib、Jb位數看即編碼的位數，要看分割的次數，不足的前面補0.66(a)區域柵格表示5、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼5）編碼方法：b、線性四叉樹四進制地址碼(MQ碼)MQ編碼過程：圖(a)所示為88列圖，即柵格單元2323，其位置碼的最長位數是3位（即分割三次）。現對圖 (a)按MQ碼的計算公式進行編碼，得到圖 (b)所示編碼表，最后進行排序歸并得到圖 (c) MQ碼。(b)編碼

39、表(c)MQ碼自下而上675、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼5）編碼方法：b、線性四叉樹十進制地址碼(MD碼) 四進制Morton碼直觀上切合四叉樹分割，但許多語言不支持四進制變量，需用十進制表示Morton碼。線性四叉樹的十進制編碼簡稱MD編碼，它同線性四叉樹的四進制編碼主要不同在于編碼值是十進制自然數，其合并過程可直接按自然數順序進行。685、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼5）編碼方法：b、線性四叉樹十進制地址碼(MD碼)A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B

40、13A 10A 11B 14B 15如行為2、列為3的柵格的MD步驟：(1)行、列號為二進制 Ib= 1 0 Jb= 1 1(2)I行J列交叉 1 1 0 1 = 13(3)再化為十進制. 實質上是按左上、右上、左下、右下的順序，從零開始對每個柵格進行自然編碼。 695、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼(a)區域柵格表示705、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼MQ編碼例證1：第一行、第五列的柵格單元，求它的MQ碼首先將十進制第一行、第五列轉成二進制形式，得到 行Ib =(001) 列Jb =(101)其

41、地址碼為: MQ = 2Ib+Jb = 21+101 = 103？提示：MQ = 2Ib+Jb715、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼MQ編碼例證2：求四叉樹中四進制位置碼的解碼，即已知MQ碼為103，求其行列號。算法如下：？ 若該位編碼值為0，1，對行號貢獻值為0 若該位編碼值為2，3，對行號貢獻值為1 若該位編碼值為0，2，對列號貢獻值為0 若該位編碼值為1，3，對列號貢獻值為l MQ 1 0 3 表示MQ碼為103的單元 二進制行值 0 0 1 表示第一行 二進制列值 1 0 1 表示第五列725、柵格數據編碼方法二、柵格數據結構第二章 空間

42、數據結構（2）壓縮編碼 四叉樹編碼 MQ 1 0 3 表示MQ碼為103的單元 二進制行值 0 0 1 表示第一行 二進制列值 1 0 1 表示第五列 這表示MQ碼為103的單元處于第一行、第五列。最后，線性四叉樹的每個葉接點可用三元組的線性表來表示。 三元組結構為 (M，D，V) 其中M為葉結點的地址碼；D為葉結點的深度；V為葉結點的格網屬性.735、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼MD編碼例證：把一幅2n2n的圖像壓縮成線性四叉樹的過程 1按Morton碼把圖象讀入一維數組。 2相鄰的四個象元比較，一致的合并，只記錄第一個象元的Morton碼。

43、循環比較所形成的大塊，相同的再合并，直到不能合并為止。 3進一步用游程長度編碼壓縮。壓縮時只記錄第一個象元的Morton碼。745、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼MD編碼例證：把一幅2n2n的圖像壓縮成線性四叉樹的過程A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15處理過程為：1按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 B2四相鄰象元

44、合并，只記錄第一個象元的Morton碼。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B3由于不能進一步合并，可用行程長度編碼壓縮。 0 3 4 6 8 12 A B A B A B 755、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼優缺點（1）易于計算多邊形的數量特征；（2）四叉樹表示法基本上是一種非冗余表示法，可用較少的存儲量精確的表示復雜的圖形；（3）四叉樹具有可變率或多重分辯率的特點使得它有很好的應用前景，適用于處理凝聚性或呈塊狀分布的空間數據，特別適用于處理分布不均勻的塊狀空間數據，但不適用于連續表面（如地形）或線

45、狀地物。（3）柵格到四叉樹及四叉樹到簡單柵格結構的轉換比其他壓縮方法容易 。（4）便于在多邊形中嵌套多邊形，如表示“島” 。優點765、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼優缺點（1）矢/柵正反變換還不理想。（2）建立四叉樹耗費機時很多。（3）四叉樹雖可修改，但很費事（具體的數據結構中會提到）。（4）未能表示物體間的拓撲關系。（5）數據結構復雜，當同時提供多種四叉樹結構時，不利于分析。缺點775、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼優缺點（6）與非樹表示法比較，四叉樹表示法的缺點在于轉換的不穩定性或叫滑動變異。

46、例如，兩個圖像的差異僅由于平移，就會構成極為不同的四叉樹，因而很難根據四叉樹來判斷這兩個圖像是否全同，故不利于做形狀分析和模式識別。缺點785、柵格數據編碼方法二、柵格數據結構第二章 空間數據結構（2）壓縮編碼 四叉樹編碼優缺點（7）一個物體的圖像在構成四叉樹時會被分割到若干個象限中，使它失去了內在的相關性。缺點A 0A 1A 4A 5A 2 B 3B 6B 7A 8A 9B 12B 13A 10A 11B 14B 15796、柵格數據的優缺點二、柵格數據結構第二章 空間數據結構柵格數據的優點 地理要素表達比較直觀，直接記錄空間實體的屬性值，數據存儲結構簡單，并容易實現疊加分析、數據統計等操作

47、柵格數據的缺點數據冗余度大，造成存儲空間的浪費像元大小的變化，對長度、面積等的度量有較大影響不宜進行某些空間查詢和網絡分析？80三、矢量數據結構第二章 空間數據結構 矢量是具有一定大小和方向的量。 線段長度表示大小，線段端點的順序表示方向。 有向線段用一系列有序特征點表示，矢量數據就是代表地圖圖形的各離散點平面坐標（x,y）的有序集合。 矢量數據結構主要用于表示地圖圖形元素幾何數據之間及其與屬性數據之間的相互關系。矢量數據結構是通過坐標值來精確地表示點、線、面等地理實體的。81三、矢量數據結構第二章 空間數據結構1、圖形表示822、矢量數據的獲取方式三、矢量數據結構第二章 空間數據結構1) 由

48、外業測量獲得 可利用測量儀器自動記錄測量成果(常稱為電子手薄)，然后轉到地理數據庫中。2) 由柵格數據轉換獲得 利用柵格數據矢量化技術，把柵格數據轉換為矢量數據。3) 跟蹤數字化 用跟蹤數字化的方法，把地圖變成離散的矢量數據。833、矢量數據組織三、矢量數據結構第二章 空間數據結構矢量數據表示時應考慮以下問題：矢量數據自身的存貯和處理。與屬性數據的聯系。矢量數據之間的空間關系(拓撲關系)。點：坐標對（x,y） +識別符線：坐標對系列(x1,y1).(xn,yn) 及有關屬性、其它屬性面：首尾相同的坐標串關系表幾何位置坐標文件連接84第二章 空間數據結構標識碼屬性碼空間對象編碼唯一連接空間和屬性

49、數據數據庫獨立編碼點: ( x ,y )線: ( x1 , y1 ) , (x2 , y2 ) , , ( xn , yn )面: ( x1 , y1 ) , (x2 , y2 ) , , ( x1 , y1 )點位字典點: 點號文件線: 點號串面: 點號串點號XY1112223344n5566存儲方法854、矢量數據編碼方式三、矢量數據結構第二章 空間數據結構（1）實體式（spaghetti）- 面條模型:以實體為單位記錄其坐標。 點實體 線實體 面實體86方向字體排列指針與線相交的角度如果是簡單點符號符號字符大小簡單點文字說明結點唯一識別符比例尺方向x，y 坐標其它有關的屬性點實體類型序列

50、號有關的屬性如果是文字說明如果是結點點實體87線實體唯一標識碼線標識碼起始點終止點坐標對序列顯示信息非幾何屬性線實體 與線表非常相似，但它的最后一個結點坐標值與第一個結點坐標值相同。 對于多邊形中的“島”，處理方法是在每個多邊形頭記錄中增加一條“島”的屬性來表示優先級，低優先級的多邊形先繪置先充填，高優先級的多邊形后繪置，這樣島多邊形就覆蓋了原先的多邊形。面實體884、矢量數據編碼方式三、矢量數據結構第二章 空間數據結構（1）實體式 優點 結構簡單、直觀、易實現以實體為單位的運算和顯示。 缺點 1、相鄰多邊形的公共邊界被數字化并存儲兩次，造成數據冗余和碎屑多邊形數據不一致，浪費空間，導致雙重邊

51、界不能精確匹配。 2、自成體系，缺少多邊形的鄰接信息，無拓撲關系，難以進行鄰域處理，如消除多邊形公共邊界，合并多邊形。 3、島作為一個單個圖形，沒有與外界多邊形聯系。不易檢查拓撲錯誤。 所以，這種結構只用于簡單的制圖系統中，顯示圖形。894、矢量數據編碼方式三、矢量數據結構第二章 空間數據結構（2）索引式對所有點的坐標按順序建坐標文件，再建點與邊（線）、線與多邊形的索引文件。1234567891011 1213 1415PPPMap1）點文件：點號坐標1x1,y1索引文件：面號弧段號P1A,B,C3）面文件：2）弧段文件:弧段號起點終點點號A527,8,9,10904、矢量數據編碼方式三、矢量

52、數據結構第二章 空間數據結構（2）索引式與實體式相比：優點：用建索引的方法消除多邊形數據的冗余和不一致，鄰接信息、島信息可在多邊形文件中通過是否公共弧段號的方式查詢。缺點：表達拓撲關系較繁瑣，給相鄰運算、消除無用邊、處理島信息、檢索拓撲關系等帶來困難，以人工方式建立編碼表，工作量大，易出錯。914、矢量數據編碼方式三、矢量數據結構第二章 空間數據結構（3）雙重獨立式編碼1234567891011 1213 1415PPPMap簡稱DIME(Dual Independent Map Encoding)，是美國人口統計系統采用的一種編碼方式，是一種拓撲編碼結構。1）點文件：點號坐標1x1,y12）

53、線文件:線文件是以線段為記錄單位 線號左多邊形 右多邊形 起點終點L210P1P2210關聯鄰接關聯連通拓撲關系明確924、矢量數據編碼方式三、矢量數據結構第二章 空間數據結構（3）雙重獨立式編碼1234567891011 1213 1415PPPMap簡稱DIME(Dual Independent Map Encoding)，是美國人口統計系統采用的一種編碼方式，是一種拓撲編碼結構。3）面文件面號線號P1L210,L109在DIME中做如下改進： 將以線段為記錄單位改為以弧段為單位鏈狀雙重獨立式編碼934、矢量數據編碼方式三、矢量數據結構第二章 空間數據結構（4）鏈式雙重獨立式編碼拓撲數據結

54、構1234567891011 1213 1415PPPMap1）弧段坐標文件：弧段號坐標系列（串)Ax2,y2,X10,y102）弧段文件：鏈面，鏈結點關系 弧段號 左多邊形 右多邊形 起點終點AP1P2253）面文件面號弧段號 P1A,B,-C944、矢量數據編碼方式三、矢量數據結構第二章 空間數據結構（4）鏈式雙重獨立式編碼拓撲數據結構1234567891011 1213 1415PPPMap4）點拓撲文件： 結點鏈關系 點號 弧段號 2A,B,D在拓撲結構中，多邊形（面）的邊界被分割成一系列的線（弧、鏈、邊）和點（結點）等拓撲要素，點、線、面之間的拓撲關系在屬性表中定義，多邊形邊界不重復

55、。 954、矢量數據編碼方式三、矢量數據結構第二章 空間數據結構（4）鏈式雙重獨立式編碼拓撲數據結構特點：拓撲關系明確，也能表達島信息，而且以弧段為記錄單位，滿足實際應用需要。因為一般數字化一條街道時，必然有許多中間點，但我們在做空間分析是卻沒有必要以這些中間點所組成的折線為研究對象，而應以整條弧段（某條街道）為研究對象. 被一些成熟的商品化軟件采用，如ARC/INFO軟件。例：ARC文件：二進制文件: 弧段號 點數 坐標串 在GIS數據輸入中，建拓撲是指給圖形數據（點、線、面）增加拓撲結構， INFO：屬性表如AAT（Arc Attribute Table）用戶標識碼，表明地物類型當圖形數據

56、修改、刪除、增加點、線、面要素后，其拓撲關系也發生改變，所以，需重新建拓撲。弧段號USER_IDLPOLYRPOLYFROM_NODETO_NODE其它屬性:（名稱)96三、矢量與柵格數據結構的比較第二章 空間數據結構97第二章 空間數據結構98第二章 空間數據結構99第二章 空間數據結構100四、矢量、柵格數據結構的選擇第二章 空間數據結構 在GIS建立過程中，應根據應用目的和應用特點、可能獲得的數據精度以及地理信息系統軟件和硬件配置情況，選擇合適的數據結構。 柵格結構:大范圍小比例尺的自然資源、環境、農林業等區域問題的研究。是一種影像數據結構，適用于遙感圖像的處理。 矢量結構：城市分區或詳

57、細規劃、土地管理、公用事業管理等方面的應用，便于網絡分析、制圖應用。101五、矢量、柵格數據一體化第二章 空間數據結構1、基本概念 將矢量面對目標的方法和柵格元子充填的方法結合起來，具體采用填滿線狀目標路徑和充填面狀目標空間的方法作為一體化數據結構的基礎。 線狀地物：除記錄原始取樣點外，還記錄路徑所通過的柵格。 面狀地物：除記錄它的多邊形周邊以外，還包括中間的面域柵格。102五、矢量、柵格數據一體化第二章 空間數據結構1、基本概念 一方面，它保留了矢量的全部性質，以目標為單元直接聚集所有的位置信息，并能建立拓撲關系； 另一方面，它建立了柵格與地物的關系，即路徑上的任一點都直接與目標建立了聯系。

58、從原理上說，這是一種以矢量的方式來組織柵格數據的數據結構。103五、矢量、柵格數據一體化第二章 空間數據結構2、三個約定為了便于組織數據，首先作如下約定；（1）地面上的點狀地物是地球表面上的點，它僅有空間位置，沒有形狀和面積。在計算機內部只需要表示該點的一個位置數據及與結點關聯的弧段信息。（2）地面上的線狀地物是地球表面的空間曲線，它有形狀但沒有面積，它在平面上的投影是一連續不間斷的直線或曲線。在計算機內部需要用一組元子填滿整個路徑，并表示該弧段相關的拓撲信息。 （3）地面上的面狀地物是地球表面的空間曲面，并具有形狀和面積，它在平面上的投影是由邊界包圍的緊致空間和一組填滿路徑的元子表達的邊界組

59、成。在計算機內部需表示由元子填滿路徑的一組邊界和由邊界組成的空間。104五、矢量、柵格數據一體化第二章 空間數據結構3、細分格網法 由于柵格數據結構的精度低,通常用細分格網的方法來提高點、線、面狀目標邊界線數據的表達精度，即在有點、線目標通過的基本格網內，再細分成16 16或256 256 個細格網，以提高精度。 將一對X,Y坐標用兩個Morton碼代替：前一M1表示該點（采樣點或附加的交叉點）所在基本格網的地址碼，后者M2 表示該點對應的細分格網的Morton碼，既顧全整體定位，又保證精度。 x,yM1 M2105五、矢量、柵格數據一體化第二章 空間數據結構4、一體化數據結構設計 線性四叉樹

60、(Morton)是基本數據格式，三個約定設計點、線、面數據結構的基本依據，細分格網法保證足夠精度。（1）點狀地物和結點的數據結構約定1，點僅有位置、沒有形狀和面積，只要將點的坐標轉化為地址碼M1和M2 ,結構簡單靈活，便于點的插入和刪除，還能處理一個柵格內包含多個點狀目標的情況。點狀目標及其數據結構結點及其數據結構坐標點的地址碼106五、矢量、柵格數據一體化第二章 空間數據結構4、一體化數據結構設計（2）線狀地物和弧段的數據結構約定2，線狀地物有形狀但沒有面積，沒有面積意味著只要用一串數據表達每個線狀地物的路徑即可，將該線狀地物經過的所有柵格的地址全部記錄下來。仿照矢量數據組織的鏈狀雙重獨立式