空間數據結構2023-04-141第1頁，共64頁，2023年，2月20日，星期一GIS基本功能的實現過程文件圖表數據獲取原始數據存儲檢索空間查詢空間分析數據編輯投影變換數據輸出制圖、表格交互展示

GIS數據空間數據庫2023-04-142第2頁，共64頁，2023年，2月20日，星期一第三章空間數據結構數據結構是指數據組織的形式，是適合于計算機存儲、管理和處理的數據邏輯結構；對空間數據而言則是地理實體的空間排列方式和相互關系的抽象描述，是對數據的一種理解和解釋。不說明數據結構的數據是毫無用處的，不僅用戶無法理解，計算機程序也不能正確處理。第一節柵格數據結構第二節矢量數據結構第三節兩種數據結構的比較和轉換第四節其他數據結構2023-04-143第3頁，共64頁，2023年，2月20日，星期一第一節柵格數據結構柵格數據:柵格數據結構，又稱為網格結構或像元結構。實際就是像元陣列，每個像元由行列確定它的位置。由于柵格結構是按一定的規則排列的，所表示的實體位置很容易隱含在數據文件的存儲結構中，且行列坐標可以很容易地轉為其它坐標系下的坐標。每個像元包含一個代碼，代碼本身明確地代表了實體的屬性類型或量值，或僅僅包含指向其屬性記錄的指針。

2023-04-144第4頁，共64頁，2023年，2月20日，星期一點線面點：為一個像元線：在一定方向上連接成串的相鄰像元集合。面：聚集在一起的相鄰像元集合。B,B,B,B,B,R,B,B,E,E,B,E,H,B,R,B,B,B,E,E,B,E,B,B,R,P,P,B,E,B,

E,B,B,B,R,P,P,B,B,B,B,B,B,R,P,P,B,B,B,B,B,B,B,R,B,B,B,B,B,B,B,B,B,R,B,B,B,B,B,B,B,B,R,B,B,B,B,B,H,B,B,B,R,B,B,B,B,B,B,B,B,R,R,B,B,B,B,B,B,B返回2023-04-145第5頁，共64頁，2023年，2月20日，星期一獲得柵格結構數據的途徑目讀法：在地圖上均勻劃分網格，逐個網格地確定其代碼；矢量數字化法：用數字化儀得到矢量數據結構后，再轉換成柵格結構；掃描數字化：逐點掃描地圖，將掃描數據進行重采樣和再編碼；分類影像輸入：將經過分類解譯的遙感影像數據直接或重采樣后輸入系統。2023-04-146第6頁，共64頁，2023年，2月20日，星期一柵格數據結構特點離散的量化柵格值表示空間對象。位置隱含，屬性明顯。數據結構簡單，易于擴充、修改，特別易于與遙感數據結合，但數據量大。適合于高級語言作文件或矩陣處理。存在幾何和屬性誤差。2023-04-147第7頁，共64頁，2023年，2月20日，星期一柵格數據的幾何誤差

在下圖中，ac的距離應為5，但在柵格結構中，如以像元邊線計算則為7，以像元為單位則為4。三角形abc的面積應為6個平方單位，而在柵格結構中則為7個平方單位，這種誤差隨像元的增大而增加。abc345abcac距離:7(5)abc面積:72023-04-148第8頁，共64頁，2023年，2月20日，星期一柵格數據的屬性誤差在一個柵格的地表范圍內，可能存在具有不同屬性的地理實體，如可能存在多于一種的地物，而表示在相應的柵格結構中常常只能是一個代碼，因此出現屬性誤差。2023-04-149第9頁，共64頁，2023年，2月20日，星期一柵格數據單元屬性值確定CAB百分比法面積占優重要性中心點法A連續分布地理要素C具有特殊意義的較小地物A分類較細、地物斑塊較小AB為了逼近原始數據精度，除了采用這幾種取值方法外，還可以采用縮小單個柵格單元的面積，增加柵格單元總數的方法。2023-04-1410第10頁，共64頁，2023年，2月20日，星期一柵格數據壓縮存儲的編碼方法（1）

——鏈式編碼(ChainCodes)又稱為弗里曼鏈碼(Freeman)或邊界鏈碼。該方法將線狀地物和面狀地物的邊界表示為：由某一起點開始并按某些基本方向確定的單位矢量鏈。鏈式編碼的前兩位數字表示起點的行、列數，從第三個數字開始表示單位矢量的方向。如果右圖中面狀地物的起點為像元(10，1)，則其邊界按順時針方向的鏈式編碼為：

10，1，7，0，1，0，7，1，7，0，0，2，3，2，2，1，0，7，0，0，0，0，2，4，3，4，4，3，4，4，5，4，5，4，5，4，5，4，6，6。012345672023-04-1411第11頁，共64頁，2023年，2月20日，星期一柵格數據壓縮存儲的編碼方法（2）

——游程長度編碼(Run—LengthCodes)

對左圖進行的游程長度編碼是（9，4），（0，4），（9，3），（0，5），（0，1），（9，2），（0，1），（7，2），（0，2），（0，4），（7，2），（0，2），（0，4），（7，4），（0，4），（7，4），（0，4），（7，4），（0，4），（7，4）。游程長度編碼只在各行（或列）數據的代碼發生變化時依次記錄該代碼以及相同代碼重復的個數。2023-04-1412第12頁，共64頁，2023年，2月20日，星期一柵格數據壓縮存儲的編碼方法（3）

——塊式編碼(BlockCodes)

塊式編碼是將游程長度編碼擴大到二維的情況，把多邊形范圍劃分成由像元組成的正方形，然后對各個正方形進行編碼。如圖：塊式編碼的數據結構由初始位置(行號，列號)和邊長，再加上記錄單元的代碼組成。根據這一編碼原則，上述多邊形只需12個單位正方形。5個4單位的正方形和2個16單位的正方形就能完整表示，總共要41個數據，其中19對坐標，3個塊的半徑。具體編碼如下（1，1，2，9），（1，3，1，9），（1，4，1，9），（1，5，2，0），（1，7，2，0），（2，3，1，9）……2023-04-1413第13頁，共64頁，2023年，2月20日，星期一柵格數據壓縮存儲的編碼方法（4）

——四叉樹編碼(QuadtreeEncoding)

四叉樹編碼又稱為四分樹、四元樹編碼，是一種更有效地壓編數據的方法。它將×像元陣列連續進行4等分，如果某正方形的所有格網值相同，則該正方形就不再繼續分割，否則還要把它再分割成四個正方形，如下圖。也可采用從下而上的方法建立，對柵格數據按如下的順序進行檢測：如果每相鄰四個格網值相同則進行合并，逐次向上遞歸合并，直到符合四叉樹的原則為止。后者與前者相比，運算速度較快。父結點、本結點、葉（子）結點2023-04-1414第14頁，共64頁，2023年，2月20日，星期一按其編碼方法的不同四叉樹數據結構又分為常規四叉樹和線性四叉樹。NW0NE1SW3SE2NSEW“A”點數據結果：（NE131,

A）1）常規四叉樹常規四叉樹除了記錄葉結點之外，還要記錄中間結點。2023-04-1415第15頁，共64頁，2023年，2月20日，星期一四叉樹數據結構十進制四叉樹編碼：

“A”點數據結果：（A30）2）線性四叉樹基本思想：不需記錄中間結點和實用指針，僅記錄葉結點，并用地址碼表示葉結點位置。分類：四進制和十進制。十進制四叉樹的地址碼又稱為Morton碼。2023-04-1416第16頁，共64頁，2023年，2月20日，星期一線性四叉樹地址碼具體思路：首先將二維柵格數據的行列號分別轉化為二進制數，交叉排列后再轉化為十進制數，即為線性四叉樹地址碼Morton碼。例如：對于第5行、第7列的Morton碼為：行數=5（0101），列數=7（0111）Morton碼=00110111=552023-04-1417第17頁，共64頁，2023年，2月20日，星期一Morton碼與行列號（i,j）間存在有函數關系,如果找到這種函數關系，則可使二維地址碼變為一維，可進行簡單的排序、快速掃描?？蓪⒕W格代碼值直接賦給以Morton碼為下標的數組單元。解碼時，由Morton碼找出對應的行列號，將代碼填回網格。完成代碼的存儲和回放。2023-04-1418第18頁，共64頁，2023年，2月20日，星期一2023-04-1419第19頁，共64頁，2023年，2月20日，星期一2023-04-1420第20頁，共64頁，2023年，2月20日，星期一二維行程編碼

在生成的線性四叉樹表中，仍存在前后葉結點的值相同的情況，因而可以采取進一步的壓縮表達，即將格網值相同的前后結點合并成一個值，形成二維行程編碼（TwoDimen-sionalRunEncoding，簡稱2DRE）表。在這種二維行程編碼中，前后兩個地址碼之差表達了該行程段的格網數，它可以表示該子塊的大小。2023-04-1421第21頁，共64頁，2023年，2月20日，星期一柵格數據的各種壓縮編碼方式的比較壓縮編碼方式特點鏈式編碼對線狀和面狀地理實體的表示有很強的壓縮能力；具有一定的運算功能；探測邊界急彎和凹進部分等比較容易；類似矢量數據結構，比較適合存儲圖形數據。對疊置運算很難實施；對局部修改將改變整體結構；效率較低；相鄰多邊形的邊界被重復存儲從而產生冗余。游程長度編碼在柵格加密時，數據量沒有明顯增加，壓縮效率較高，易于進行檢索、疊加、合并等操作，運算簡單。塊狀編碼對大而簡單的多邊形更有效；在合并、插入、檢查延伸性、計算面積等操作有明顯的優勢。四叉樹編碼能容易而有效地計算多邊形的數量特征；陣列各部分的分辨率是可變的，既精確表示圖形結構又可減少存儲量；與簡單柵格的相互轉換比較容易；多邊形中嵌套小多邊形比較方便。具有轉換的不確定性，不利于形狀分析和模式識別。2023-04-1422第22頁，共64頁，2023年，2月20日，星期一第二節矢量數據結構矢量數據結構是通過記錄坐標的方式，盡可能地將點、線、面地理實體表現得精確無誤。其坐標空間假定為連續空間，不必象柵格數據結構那樣進行量化處理。因此矢量數據能更精確地定義位置、長度和大小。由于以下原因，不可能得到絕對精確的值：表示坐標的計算機字長有限；所有矢量輸出設備，盡管分辨率比柵格設備高，也有一定的步長；矢量法輸入時選取的點不可能太多；人工輸圖時存在不可避免的定位誤差。2023-04-1423第23頁，共64頁，2023年，2月20日，星期一矢量數據結構編碼的基本內容矢量數據結構通過記錄空間對象的坐標及空間關系來表達空間對象的位置。點：空間的一個坐標點；線：多個點組成的弧段；面：多個弧段組成的封閉多邊形。2023-04-1424第24頁，共64頁，2023年，2月20日，星期一矢量數據結構編碼的方式（1）

—面條結構（實體式）構成多邊形邊界的各個線段，以多邊形為單位進行組織，只記錄空間對象的位置坐標和屬性信息，不記錄拓撲關系。多邊形 數據項 A (x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5),(x6,y6),(x7,y7),(x8,y8),(x9,y9),(x1,y1) B (x1,y1),(x9,y9),(x8,y8),(x17,y17),(x16,y16),(x15,y15),(x14,y14),(x13,y13),(x12,y12),(x11,y11),(x10,y10),(x1,y1) C (x24,y24),(x25,y25),(x26,y26),(x27,y27),(x28,y28),(x29,y29),(x30,y30),(x31,y31),(x24,y24) D (x19,y19),(x20,y20),(x21,y21),(x22,y22),(x23,y23),(x15,y15),(x16,y16),(x19,y19) E (x5,y5),(x18,y18),(x19,y19),(x16,y16),(x17,y17),(x8,y8),(x7,y7),(x6,y6),(x5,y5)2023-04-1425第25頁，共64頁，2023年，2月20日，星期一矢量數據結構編碼的方式（1）

—面條結構（實體式）存儲：獨立存儲：空間對象位置直接跟隨空間對象；點位字典：點坐標獨立存儲，線、面由點號組成特征無拓撲關系，主要用于顯示、輸出及一般查詢公共邊重復存儲，存在數據冗余，難以保證數據獨立性和一致性多邊形分解和合并不易進行，鄰域處理較復雜；處理嵌套多邊形比較麻煩適用范圍：制圖及一般查詢，不適合復雜的空間分析2023-04-1426第26頁，共64頁，2023年，2月20日，星期一矢量數據結構編碼的方式（2）

—索引式

線與多邊形之間的樹狀索引

點與線之間的樹狀索引

2023-04-1427第27頁，共64頁，2023年，2月20日，星期一矢量數據結構編碼的方式（3）

——雙重獨立式DIME(DualIndependentMapEncoding)

線號左多邊形右多邊形起點終點aOA18bOA21cOB32dOB43eOB54fOC65gOC76hOC87iCA89jCB95kCD1210lCD1112mCD1011nBA92對任何一條線段，用其兩端的節點及相鄰面域來表示；利用這種拓撲關系來組織數據，可以有效地進行數據存儲正確性檢查，同時便于對數據進行更新和檢索(P44表3-3)。

2023-04-1428第28頁，共64頁，2023年，2月20日，星期一矢量數據結構編碼的方式（4）

——鏈狀雙重獨立式

鏈狀雙重獨立式數據結構是DIME數據結構的一種改進。在DIME中，一條邊只能用直線兩端點的序號及相鄰的面域來表示，而在鏈狀數據結構中，將若干直線段合為一個弧段（或鏈段），每個弧段可以有許多中間點。在鏈狀雙重獨立數據結構中，主要有四個文件：多邊形文件、弧段文件、弧段坐標文件、結點文件。2023-04-1429第29頁，共64頁，2023年，2月20日，星期一弧段文件弧段號 起始點 終結點 左多邊形 右多邊形 a 5 1 O Ab 8 5 E Ac 16 8 E Bd 19 5 O Ee 15 19 O Df 15 16 D Bg 1 15 O Bh 8 1 A Bi 16 19 D Ej 31 31 B C 弧段坐標文件弧段號 點號 a 5,4,3,2,1 b 8,7,6,5 c 16,17,8 d 19,18,5 e 15,23,22,21,20,19 f 15,16, g 1,10,11,12,13,14,15 h 8,9,1 i 16,19 j 31,30,29,28,27,26,25,24,31

鏈狀雙重獨立式多邊形文件多邊形號 弧段號 周長面積中心點坐標 A h,b,a B g,f,c,h,-j C j D e,i,f E e,i,d,b 2023-04-1430第30頁，共64頁，2023年，2月20日，星期一矢量數據結構的屬性數據表達屬性特征類型類別特征：是什么說明信息：同類目標的不同特征屬性特征表達類別特征：類型編碼說明信息：屬性數據結構和表格圖形數據和屬性數據的連接通過目標識別符或內部記錄號實現。2023-04-1431第31頁，共64頁，2023年，2月20日，星期一矢量數據結構的屬性數據表達點狀對象目標標識目標標識地物編碼坐標關聯的線目標精度控制點等級測量單位測量年限線狀對象目標標識目標標識地物編碼坐標串起點、終點、左面、右面路面材料等級修建時間寬度管養單位…………面狀對象目標標識目標標識地物編碼邊界目標號建筑日期所有者建筑面積建筑單位結構……空間對象地物編碼地物名稱制圖顏色幾何類型制圖符號編碼屬性表明地物類型特征與制圖屬性2023-04-1432第32頁，共64頁，2023年，2月20日，星期一矢量數據結構的特點用離散的點描述空間對象與特征，定位明顯，屬性隱含。用拓撲關系描述空間對象之間的關系。面向目標操作，精度高，數據冗余度小。與遙感等圖象數據難以結合。輸出圖形質量好，精度高。2023-04-1433第33頁，共64頁，2023年，2月20日，星期一第三節兩種數據結構的比較與轉換矢量數據優點：表示地理數據的精度較高嚴密的數據結構，數據量小完整的描述空間關系圖形輸出精確美觀圖形數據和屬性數據的恢復、更新、綜合都能實現面向目標，不僅能表達屬性，而且能方便的記錄每個目標的具體屬性信息缺點：數據結構復雜矢量疊置較為復雜數學模擬比較困難技術復雜，特別是軟硬件柵格數據優點：數據結構簡單空間數據的疊置和組合方便各類空間分析很易于進行數學模擬方便缺點：圖形數據量大用大像元減少數據量時，精度和信息量受損地圖輸出不美觀難以建立網絡連接關系投影變換比較費時2023-04-1434第34頁，共64頁，2023年，2月20日，星期一數據結構選擇原則要素還是位置？可獲取的數據定位要素的必要精度需要什么類型的要素需要什么類型的拓撲關聯所需空間分析類型生產地圖類型2023-04-1435第35頁，共64頁，2023年，2月20日，星期一矢量數據向柵格數據轉換

——點的變換

2023-04-1436第36頁，共64頁，2023年，2月20日，星期一矢量數據向柵格數據轉換

——矢量線段的變換如下圖：先標出兩端點的行數i為3和10；然后分別確定直線經過的4，5，6，7，8，9六行中的哪一列與直線相交；以第7行為例，找到第7行（i=7)中心的y值是多少，就可求出相應的j值；同法計算其它行的j值；用本直線的屬性值填充直線經過的網格。2211(x,y)(x,y)(x,y)2023-04-1437第37頁，共64頁，2023年，2月20日，星期一矢量數據向柵格數據轉換

——多邊形數據的轉換從多邊形的起點依次記錄每一點左邊面域值；對多邊形的每一條邊轉換成柵格形式；進行節點處理，使節點的柵格值唯一而準確；從第一行起逐行按列的先后順序排序，使得到的數據結構等同于柵格數據壓縮編碼的數據結構形式展開為全柵格數據結構。2023-04-1438第38頁，共64頁，2023年，2月20日，星期一柵格數據向矢量數據轉換（1）

——基于掃描圖像的矢量化二值化：在最大與最小灰階之間定義一個閾值T，大于或等于T的柵格值記為1，小于T的柵格值記為0。2023-04-1439第39頁，共64頁，2023年，2月20日，星期一柵格數據向矢量數據轉換（1）

——基于掃描圖像的矢量化細化：消除線劃橫斷面柵格數的差異，使每一條線只保留代表其軸線或周圍輪廓線位置的單個柵格的寬度。剝皮法：從曲線的邊緣開始，每次剝掉等于一個柵格寬度的一層，直到最后留下彼此連通的由單個柵格點組成的圖形；不允許剝去會導致曲線不連通的柵格。將經細化處理后應保留的柵格系列寫入數據文件。2023-04-1440第40頁，共64頁，2023年，2月20日，星期一柵格數據向矢量數據轉換（1）

——基于掃描圖像的矢量化跟蹤：目的是將寫入數據文件的細化處理后的柵格數據，整理為從結點出發的線段或閉合的線條，并以矢量形式存儲于特征柵格點中心的坐標從圖幅西北角開始，按一定方向，從起始點開始，根據8個鄰域進行搜索，依次跟蹤相鄰點，并記錄結點坐標，然后搜索閉曲線，直到完成全部柵格數據的矢量化，寫入矢量數據庫。2023-04-1441第41頁，共64頁，2023年，2月20日，星期一矢柵一體化數據結構不規則鑲嵌數據結構三維數據結構第四節其他數據結構

2023-04-1442第42頁，共64頁，2023年，2月20日，星期一矢柵一體化結構這種數據結構中，同時具有矢量實體的概念，又具有柵格覆蓋的思想。其理論基礎是：多級格網方法、三個基本約定和線性四叉樹編碼。2023-04-1443第43頁，共64頁，2023年，2月20日，星期一多級格網方法將柵格劃分成多級格網：粗格網、基本格網和細分格網。粗格網用于建立空間索引，基本格網的大小與通常柵格劃分的原則基本一致，即基本柵格的大小。由于基本柵格的分辨率較低，難以滿足精度要求，所以在基本格網的基礎上又細分為256×256或16×16個格網，以增加柵格的空間分辨率，從而提高點、線的表達精度。粗格網、基本格網和細分格網都采用線性四叉樹編碼的方法，用三個Morton碼（M0、M1、M2）表示，其中M0表示點或線所通過的粗格網的Morton碼，是研究區的整體編碼；M1表示點或線所通過的基本格網的Morton碼，也是研究區的整體編碼；M2表示點或線所通過的細分格網的Morton碼，是基本柵格內的局部編碼。2023-04-1444第44頁，共64頁，2023年，2月20日，星期一三個基本約定（1）點狀地物僅有空間位置而無形狀和面積，在計算機中僅有一個坐標數據；（2）線狀地物有形狀但無面積，在計算機中需要組織一組元子（即柵格單元）填滿的路徑表達；（3）面狀地物有形狀和面積，在計算機中有一組元子表達的填滿路徑的邊界線和內部（空洞外均填滿）的區域組成。2023-04-1445第45頁，共64頁，2023年，2月20日，星期一點、線、面的矢柵一體化2023-04-1446第46頁，共64頁，2023年，2月20日，星期一矢柵一體化數據結構特點點狀地物、線狀地物和面狀地物不僅具有如同矢量數據結構的位置“坐標”，而且還可以有類型編碼、屬性值和拓撲關系，因而具有完全的矢量特性。與此同時，由于用柵格元子表達了點、填充了線性目標、多邊形邊界及其內部（空洞除外），實際是進行了柵格化，因而可以進行各種柵格操作。2023-04-1447第47頁，共64頁，2023年，2月20日，星期一4.2不規則鑲嵌數據結構不規則三角網TIN（TriangulatedIrregularNetwork

）2023-04-1448第48頁，共64頁，2023年，2月20日，星期一Dirichlet（1850年）和Voronoi（1908年）最早討論空間散點的關系問題。Voronoi圖的定義Voronoi圖把平面分成N個區，每一個區包括一個點，該點所在的區域是距離該點最近的點的集合。1934年Delaunay提出了Voronoi圖的對稱圖，即Delaunay三角網（用直線段連接兩個相鄰多邊形內的離散點而生成的三角網）。Delaunay三角網2023-04-1449第49頁，共64頁，2023年，2月20日，星期一不規則三角網模型中，基本的結構元素有三角形頂點、邊、面，它們之間存在點與線、點與面、線與面、面與面等拓撲關系2e1e3e4e5e6e7e10e8e92023-04-1450第50頁，共64頁，2023年，2月20日，星期一不規則三角網數據結構不規則三角網需要保存的信息：每個頂點的高程，三角形頂點的平面坐標、頂點之間的連接關系和相鄰三角形等拓撲關系。理論上，這種結構只需要三角形頂點坐標文件和組成三角形的三頂點文件即可（拓撲關系隱含）?；炬湵斫Y構坐標表三角形表2023-04-1451第51頁，共64頁，2023年，2月20日，星期一不規則三角網數據結構圍繞三角形的拓撲關系描述，產生了多種TIN的數據結構：TIN的面結構、TIN的點結構、

TIN的點面結構、TIN的邊結構、TIN的邊面結構。1、TIN的面結構在基本鏈表結構的基礎上增加了用于描述三角形之間拓撲關系的數據。TIN的面結構由三個表組成，即坐標表、三角形頂點表、相鄰三角形表。2023-04-1452第52頁，共64頁，2023年，2月20日，星期一TIN的面存儲結構坐標表三角形表相鄰三角形表V表示組成三角形的各個頂點，T表示相鄰三角形2023-04-1453第53頁，共64頁，2023年，2月20日，星期一2、TIN的點結構TIN的點結構由坐標文件和三角形頂點的鄰接指針鏈組成；三角形頂點的鄰接指針鏈點是指該頂點的所有三角形其余兩頂點的不重復頂點的集合，可以按順時針或逆時針方向組成。坐標表鄰接指針鏈2023-04-1454第54頁，共64頁，2023年，2月20日，星期一3、TIN的點面結構在點結構的基礎上，增加組成三角形頂點的數表。坐標表鄰接指針鏈三角形表2023-04-1455第55頁，共64頁，2023年，2月20日，星期一4、TIN的邊結構TIN的邊結構由兩個頂點以及與之關聯的兩條邊組成。關聯邊滿足的條件：1）分布在當前邊的兩側；

2）關聯邊與當前邊的夾角最小；