6.4空間數據索引空間索引的層次結構無縫圖層工作區索引目標索引窗坐標、BSP、KDB樹、R樹和R+樹、CELL樹11、空間數據索引的必要性在GIS中需要根據空間位置進行查詢，例如，“找出通過某個區域的所有公路”，“檢索在某個區域內的所有湖泊”等等。為了處理這類空間查詢，數據庫需要檢查每一個可能滿足條件的空間要素的記錄，看它是否與查詢區域相交或是在查詢區域內，這種空間相交運算需要先讀出空間要素幾何形狀的邊界坐標，然后再與空間區域進行空間關系運算。由于傳統數據庫的這種窮盡式搜索方法花費的磁盤訪問時間和空間運算時間都很長，往往達到令人無法忍受的程度，故必須建立空間數據索引機制。22、空間索引的層次33、無縫圖層現實世界的地區、城市均是連續的。對較小的區域可以將數據物理連接，生成物理無縫圖層。對無法生成物理無縫圖層的地區，可以建立邏輯無縫圖層。邏輯無縫圖層建立了地物的連接描述。44、工作區索引對海量數據而言，必須建立多個工作區，將數據按工作區存放于存儲器建立索引文件在開窗操作時，系統根據窗口坐標，按索引文件迅速調入所涉及的工作區55、目標索引窗坐標索引機制格網型空間索引BSP索引機制KDB樹R樹和R+樹CELL樹66、窗坐標

索引

機制建立每個實體的最小包容矩形，記錄其對角坐標。單點檢索可判斷是否在包容矩形內；范圍檢索可判斷每個實體的最小包容矩形和范圍的關系：內、外、相交。對所有空間實體的外接矩形最大最小坐標進行落入判別，其中空間實體B、C完全落入查詢窗，從空間數據庫中提取B和C的相應數據。

A 查詢窗口 B

CE F D

77、格網型空間索引將區域用橫豎線條劃分大小相等和不等的格網，記錄每一個格網所包含的空間實體。進行空間查詢時，首先計算出查詢對象所在格網，然后再在該網格中快速查詢所選空間實體。8一條河流、一個湖泊和一條省界，它們的關鍵字分別為5，11和23。河流穿過的柵格為2，34，35，67，68；湖泊覆蓋的柵格為68，69，100，101；省界所通過的柵格為5，37，36，35，67，99，98，97。98、BSP索引機制是一種二叉樹，它將空間逐級進行一分為二的劃分。BSP樹能很好地與空間數據庫中空間對象的分布情況相適應，但對一般情況而言，BSP樹深度較大，對各種操作均有不利影響。109、KDB樹KDB樹是B樹向多維空間的一種發展。它對于多維空間中的點進行索引具有較好的動態特性，刪除和增加空間點對象也可以很方便地實現；其缺點是不直接支持占據一定空間范圍的地物要素，如二維空間中的線和面。該缺點可以通過空間映射或變換的方法部分地得到解決。1110、R樹示意圖上圖表示了三組多邊形（矩形，用實線畫出）及對應于這三組多邊形的R樹中結點的外包絡矩形（用虛線畫出），右圖為R樹本身。1211、R+樹結構示意圖

R+樹的數據結構與R樹的相同，但是，對于被分割的下層虛擬矩形或實體外接矩形，還要增加關系表達：原矩形標識符，分割后矩形1的標識符，分割后矩形2的標識符1312、R樹和R+樹比較由于R樹兄弟結點對應的空間區域可以重疊，因此，R樹可以較容易地進行插入和刪除操作；但正因為區域之間有重疊，空間索引可能要對多條路徑進行搜索后才能得到最后的結果，因此，其空間搜索的效率較低。在R+樹中，兄弟結點對應的空間區域沒有重疊，而沒有重疊的區域劃分可以使空間索引搜索的速度大大提高；但由于在插入和刪除空間對象時要保證兄弟結點對應的空間區域不重疊，而使插入和刪除操作的效率降低。1413、CELL樹R樹和R+在插入、刪除和空間搜索效率兩方面難于兼顧，故CELL樹應運而生。它在采用凸多邊形來作為劃分的基本單位，與BSP樹有類似之處，子空間不再相互覆蓋。故CELL樹是比較優秀的空間索引方法。156.5空間數據模型三種傳統模型層次、網絡、關系面向對象模型二維矢量模型柵格數據模型三維空間模型矢量、柵格16一、三種傳統模型層次網絡關系171、層次模型層次模型是一種樹結構模型，它把數據按自然的層次關系組織起來，以反映數據之間的隸屬關系。一棵樹有且僅有一個無雙親結點的稱為根的結點；其余結點有且僅有一個雙親結點。182、層次模型描述矢量數據特點是將數據組織成一對多關系的結構。層次結構采用關鍵字來訪問其中每一層次的每一部分。層次數據庫結構特別適用于文獻目錄、土壤分類、部門機構等分級數據的組織ⅠⅡ123456abcdefgMMⅠⅡabcdefg1223344134355664c193、層次數據的特點優點：存取方便且速度快結構清晰，容易理解數據修改和數據庫擴展容易實現檢索關鍵屬性十分方便缺陷：結構呆板，缺乏靈活性同一屬性數據要存儲多次，數據冗余大（如公共邊）不適合于拓撲空間數據的組織204、空間對象的層次分類編碼分類對象的從屬和層次關系有明確的分類對象類別和嚴格的隸屬關系高壓711電線架715管線:7地下電力線與電纜72電力線71地下檢修井74管線73低壓712電桿713電塔714不依比例7142依比例7141215、網絡模型基本特征：結點數據之間沒有明確的從屬關系，一個結點可與其它多個結點建立聯系，即結點之間的聯系是任意的，任何兩個結點之間都能發生聯系，可表示多對多的關系。226、用網絡數據模型描述復雜關系

網絡模型用連接指令或指針來確定數據間的顯式連接關系，是具有多對多類型的數據組織方式。系名土木系教師數學生數研究生系名管理系教師數49學生數257研究生71學校名稱工程學院系名測繪系教師數52學生數300研究生70系名教師數學生數研究生系名教師數學生數學號002312姓名楊樂年級3籍貫廣東系名教師數學生數研究生系名教師數學生數教師號66姓名***年齡53職稱教授系名教師數學生數研究生系名教師數學生數課程號A01課程名GIS周學時4學分5系名教師數系名學號002312課程號A01237、網絡數據模型特點優點：能明確而方便地表示數據間的復雜關系數據冗余小缺陷：網狀結構的復雜，增加了用戶查詢和定位的困難需要存儲數據間聯系的指針，使得數據量增大數據的修改不方便（指針必須修改）248、關系數據模型關系模型的數據結構為滿足一定條件的二維表，表具有固定的列數和任意的行數，在數學上稱為“關系”；二維表是同類實體的各種屬性的集合，每個實體對應于表中的一行，在關系中稱為元組，通常稱為一條記錄；表中的列表示屬性，稱為域，相當于通常記錄中的一個數據項。若二維表中有n個域，則每一行叫做一個n元組，這樣的關系稱為n度(元)關系；表的行對應于對象的實例，各個表的行列交點就用來存貯簡單值。滿足一定條件的規范化關系的集合，就構成了關系模型。259、房屋表和道路表房號性質樓層數結構建筑年代20私房7磚198629公房12砼2001編號等級路面材料寬度車道數建筑年代3021水泥12419862012瀝青166200126ⅠⅡ123456abcdefgM10、用關系模型表示地理實體地理實體——多邊形關系：M(Ⅰ，Ⅱ)多邊形——邊關系：Ⅰ(a,b,c,d)Ⅱ(e,f,g,c)邊——結點關系：a(V１，V2)、b(V2，V3)、c(V3，V4)、d(V１，V4)、e(V１，V5)、f(V5，V6))、g(V6，V4)ⅠabcdⅡefgca12b23c34d14e35f56g64MⅠMⅡ2711、關系模型的進一步發展RDBMS的現狀是理論和技術都非常完善和成熟，基本上占據了全部傳統應用領域和90%以上的非傳統應用領域典型的代表有：Oracle、MSSQL、DB2、INGRES、SyBase、Xbase、FoxPro、Rdb/VMS、Informix2812、非結構化大型對象的引進

多媒體——如文本數據、圖象數據、靜止的視頻片斷、全動感的視頻信息、聲音波形等等，需要用關系數據庫存儲和管理這類非結構化數據。DEC公司于1981年就引進能存貯變長字符串和二進制數據的概念，目前一些大型的RDBMS（如Oracle等）中，增加了大型對象這種數據類型。數據從等長轉為變長。2913、分布式數據庫70年代以來計算機網絡迅速發展，在地理上分散的公司、團體和組織對于數據庫更為廣泛的應用，產生了分布式數據庫系統。分布式數據庫系統是數據庫和網絡兩者有機結合的結果。比如，全省各院校可以把招生的情況存放在各自的招生辦，省招生辦可以通過網絡隨時查詢統計各校數據。3014、對象特性的融入為了迎接面向對象數據庫在非傳統應用領域對關系數據庫提出的挑戰，確保關系數據庫在數據庫領域的霸主地位，關系數據庫巨頭Oracle、Sybase、DB2、Informix都在積極努力，使自己的關系型產品增加一些面向對象的成分。目前已經有推向市場的這類產品存在，如Oracle10g、DB2等。3115、面向對象模型面向對象的基本概念是在上世紀70年代萌發，它的基本做法是把系統工程中的某個模塊和構件視為問題空間的一個或一類對象。80年代，面向對象的方法得到很快發展，在系統工程、計算機、人工智能等領域獲得了廣泛應用。90年代，人們在更高級的層次上和更廣泛的領域內對面向對象的方法進行研究。3216、面向對象的特性和核心技術

面向對象方法的特性抽象性、封裝性、多態性面向對象方法的核心技術分類、概括、聚集、聯合3317、面向對象的幾何抽象類型

GIS中的各種地物，在幾何性質方面不外乎表現為四種類型，即點狀地物、線狀處物、面狀地物以及由它們混合組成的復雜地物，因而這四種類型可以作為GIS中各種地物類型的超類。空間地物點狀地物線狀地物面狀地物復雜地物電視塔橋梁車站道路水管電力線建筑物湖公園礦山大學縣34三、二維矢量模型矢量方法強調了離散現象的存在，由邊界線（點、線、面）來確定邊界，因此可以看成是基于要素的。然而，在一些基于矢量的GIS中，表現表面的便利，帶給它模擬二維場的可能性，最常見的例子就是地表高程。35二維矢量數據表示36四、柵格數據模型柵格數據模型是基于連續鋪蓋的，它是將連續空間離散化，即用二維鋪蓋或劃分覆蓋整個連續空間；鋪蓋可以分為規則的和不規則的，后者可當做拓撲多邊形處理，如社會經濟分區、城市街區；鋪蓋的特征參數有尺寸、形狀、方位和間距。對同一現象，也可能有若干不同尺度、不同聚分性（AggregationorSubdivisions）的鋪蓋。在邊數從3到N的規則鋪蓋（RegularTesselations）中，方格、三角形和六角形是空間數據處理中最常用的。三角形是最基本的不可再分的單元，根據角度和邊長的不同，可以取不同的形狀，方格、三角形和六角形可完整地鋪滿一個平面。37柵格單元的形態38柵格數據表示的地表39五、三維空間模型三維矢量模型三維邊界用頂點、邊、面和體三個表來表示40三維柵格數據模型假設體V可以放在一個充分大的正方體C內，C的邊長為2n。對形體VC，如果V=C，那么V的八叉樹僅有樹根，否則對C等分為八個子立方體。只要某個子立方體不是完全空白或完全為V所占據，就要再被八等分。直到灰節點分完八叉樹上的節點可分為三類：1）灰節點，對應的立方體部分地為V所占據；2）白節點，所對應的立方體中無V的內容；3）黑節點，所對應的立方體全為V所占據41體元形式的三維數據

42線性八叉樹編碼

43本章要點建立數據模型的意義數據模型和數據結構的區別空間數據的三個基本特征如何描述地理空間數據？空間數據的分類、分級、編碼工作空間、分區、層的概念空間索引的種類、網格索引、R樹面向對象數據模型的優點44第七章地理空間數據結構無拓撲矢量數據結構拓撲數據結構柵格數據結構DEM結構四叉樹和八叉樹其它數據結構457.1無拓撲矢量數據結構點的矢量結構鏈的矢量結構面的矢量結構點：節點結點鏈：弧邊線線段面：多邊形區域面體：46點弧面的矢量表示點號XYH1237623426521235弧表1鏈號坐標串1xyhxyh…2xyhxyh…弧表2鏈號點號串1點號點號…2點號點號…面表1面表2面表3面號坐標串1xyhxyh…2xyhxyh…面號點號串1點號點號…2點號點號…面號弧號串1弧號弧號…2弧號弧號…點表47各種表示法的比較點號—弧、弧號——面冗余小、維護方便、調用復雜弧——坐標、面——坐標冗余大、維護不便、調用簡單易產生多重坐標487.2拓撲數據結構在GIS中，為了真實地反映地理實體，不僅要存儲實體的位置、形狀、大小和屬性，還必須存儲實體間的相互關系。拓撲元素點、弧、面拓撲關系最基本關系關聯：空間圖形中不同類元素之間的拓撲關系鄰接：空間圖形中同類元素之間的拓撲關系其它關系包含：空間圖形中同類不同級元素之間的拓撲關系連通：空間網絡圖形中，結點之間存在的路徑關系層次：相同拓撲元素間的等級關系49拓撲關系的表示50拓撲關系表示實例面塊ID弧段串AL6BL7、-L8、L9、L10CL1、-L11、-L7、-L5DL11、L2、L12、L8EL13、-L9、-L12、L3

FL4、L5、-L10、-L13L1P9、P2L2

P2、P3

L3

P3、P6

L4

P6、P9

┇┇P1L6P2

L1、L11、L2

P3

L2、L12、L3

P4

L12、L8、L9

┇┇L10CL2

0DL3

0EL4

0FL5

CF┇┇┇弧段ID起點，終點結點ID弧段串弧段ID左多邊形右多邊形51全顯式和半隱式弧段、起結點、終結點、左多邊形、右多邊形全顯式半隱式527.3柵格數據結構基于像元基于層基于多邊形53柵格數據結構的存儲順序54柵格數據結構小結基本概念像元及像元陣列、像元屬性及屬性取值方法像元越小，分辨率越高，圖斑越精細理解柵格編碼同樣的數據可以有不同的編碼方式，不影響結果的顯示數據壓縮編碼方式可以自己定義557.4DEM結構矩形格網結構不規則三角網結構DEM的生成56DEM的概念☆數字高程模型（DEM)：DTM中屬性為高程的要素稱為數字高程模型,它是地表單元上的高程集合,通常用矩陣來表示。☆DEM是建立DTM的“基礎數據”或稱為單要素圖；其它要素均可以從DEM數據直接或間接導出，這些“派生數據”通常包括：平均高程、坡度、坡向等。57矩形格網結構矩形格網GRID是一個高程矩陣可以由高程點、等高線內插產生，也可以由全數字攝影測量模式產生，直接接收VirtuoZo系統格式的數字高程模型和正射影像數據。同時，也接受解析測圖儀實測的隨機采樣數據和既有地形圖數字化等高線數據對于特殊地形，還存在地形地物特征點線數據。隨機柵格轉換的算法包括距離加權平均（又稱移動曲面法）和基于TIN的兩種方法58內插矩形格網5960TIN結構61TIN的主要特征TIN由一系列三角形組成三角形頂點都是一些特征點每個三角形的坡度、坡向均一三角形大小隨地形變化而變盡可能是等邊三角形三角形外接圓內沒有其它點與Voronoi多邊形(泰森多邊形)對偶以拓撲方式存儲62DEM的生成r637.5四叉樹和八叉樹將柵格數據二維空間區域按照4個象限進行遞歸分割（2n×2n，且n>1），直到子象限的數值單調為止，最后得到一棵四分叉的倒向樹。四叉樹分解，各子象限大小不完全一樣，但都是同代碼柵格單元組成的子塊，其中最上面的一個結點叫做根結點，它對應于整個圖形。不能再分的結點稱為葉子結點，可能落在不同的層上，該結點代表子象限單一的代碼，所有葉子結點所代表的方形區域覆蓋了整個圖形。從上到下，從左到右為葉子結點編號，最下面的一排數字表示各子區的代碼。為了保證四叉樹分解能不斷的進行下去，要求圖形必須為2n×2n的柵格陣列。n為極限分割次數，n＋1是四叉樹最大層數或最大高度。64四叉樹編碼①②③④⑤⑥⑦⑧⑨⑩1112131415161718192021222324252627282930313233363738393435400000333033333530022232222022225255533355西南東南西北東北65四叉樹地址和Morton碼66Morton碼—葉節點碼將十進制Morton碼轉為二進制碼39——100111將二進制Morton碼每二位轉為十進制數10011121367葉節點碼—Morton碼將葉節點碼逐位轉為二進制213100111將二進制葉節點碼轉為Morton碼100111——391*25+0*24+0*23+1*22+1*21+1*2032+0+0+4+2+1=3968Morton碼—行列值將Morton碼39轉為二進制100111將二進制的Morton碼奇偶分開100111101011將奇偶分別變成十進制的行列1010115369行列值—Morton碼將十進制的行列分別變成二進制53101011將二進制的行列值奇偶合并得Morton碼101011100111將二進制Morton碼變為十進制1*25+0*24+0*23+1*22+1*21+1*2032+0+0+4+2+1=3970十進制和二進制的轉換十進制轉二進制：

用2輾轉相除至結果為0，

將余數從下向上倒序寫就是二進制值例如302轉二進制

302/2=151余0

151/2=75余1

75/2=37余1

37/2=18余1

18/2=9余0

9/2=4余1

4/2=2余0

2/2=1余01/2=0余1

故十進制302=二進制100101110

二進制轉十進制

從最后一位開始算，依次列為第0、1、2...位、第n位的數（0或1）乘以2的n次方，得到的結果相加就是十進制值。例如:01101011.轉十進制:

第0位:1乘2的0次方=1

第1位:

1乘2的1次方=2

第2位:

0乘2的2次方＝0

第3位:1乘2的3次方＝8

第4位:

0乘2的4次方＝0

第5位:1乘2的5次方＝32

第6位:1乘2的6次方＝64

第7位:0乘2的7次方＝0

然后：1＋2＋0＋8＋0＋32＋64＋0＝107．

二進制＝十進制10771八叉樹V的長、寬、高均為2n，用3個面將其分為8塊S、N、W、E；T、B的組合為地址727.6其它數據結構區域數據結構動態分段73區域數據結構由線和面建立，由區域層和區域構成區域層內的區域具有相同屬性區域可以重疊一個區域可以由分離的面構成區域的數據表：區域號多邊形號區域號圈號弧段號74動態分段動態分段(Dynamic

Segmentation)思想是由美國威斯康星交通廳戴維.復萊特于1987年首先提出的。該思想解決了傳統的GIS在處理線性特征時所遇到的問題，是一種新的線性特征的動態分析、現實和繪圖技術。它是在傳統GIS數據模型的基礎上利用線性參考系統和相應算法，在需要分析、現實、查詢及輸出時，動態計算出屬性數據的空間位置，即動態地完成各種屬性數據集的顯示、分析及繪圖的一種方法。75動態分段區段表點事件表線事件表50100150200250紅旗大街東直路太平大街里程樁事件路徑鏈號弧段鏈號始測度到測度始位置到位置P#P-IDP-IDID路名始至屬性76本章要點矢量數據的表達方式、拓撲結構柵格數據的表達方式、壓縮方法四叉樹如何定義？如何編碼？動態分段有什么用途？77習題根據下圖，（1）列出點、線（鏈）、面（多邊形）的簡單數據結構表；（2）列出面-鏈、鏈-結點、結點-鏈、鏈-面拓撲數據結構表注：黑點為結點圓圈為節點78第八章地理空間數據庫數據庫概念數據庫系統結構數據庫管理系統的功能與組成空間數據庫管理系統的管理模式地理數據庫中的時間維Geodatabase數據庫創建798.1數據庫概念計算機對數據管理的四個階段程序——文件——數據庫——數據倉庫數據庫的英文是DATABASE，其意義為數據基地，即統一存貯和集中管理數據的基地。數據庫可以看作是與現實世界有一定相似性的模型，是集中、統一地存儲和管理某個領域信息的系統，它根據數據間的自然聯系而構成，數據較少冗余，且具有較高的數據獨立性，能為多種應用服務。80數據庫三個基本部分數據集一個結構化的相關數據的集合體，包括數據本身和數據間的聯系。數據集獨立于應用程序而存在，是數據庫的核心和管理對象。物理存儲介質指計算機的外存儲器和內存儲器。前者存儲數據；后者存儲操作系統和數據庫管理系統，并有一定數量的緩沖區，用于數據處理，以減少內外存交換次數，提高數據存取效率。數據庫軟件其核心是數據庫管理系統(DBMS)。主要任務是對數據庫進行管理和維護。具有對數據進行定義、描述、操作和維護等功能，接受并完成用戶程序和終端命令對數據庫的請求，負責數據庫的安全。818.2數據庫系統結構用戶A1用戶A2用戶B1用戶B2用戶B3A/C映射外部模型A外部模型B概念模型

C物理數據內部模型C/D映射數據庫管理系統子模式模式存儲模式828.3數據庫管理系統的功能與組成數據庫定義功能用數據庫的數據描述語言DDL來定義概念模式、外模式和內模式，即定義數據庫框架。數據庫管理功能對數據進行更新、存取等的控制功能。通常提供有數據操作語言來作為用戶和數據庫之間的接口。數據庫維護功能改善系統的性能、受損后的復原、用戶管理、拓寬數據庫用戶的要求數據庫通訊功能應具有與操作系統的接口、與各種語言的接口、與其它數據庫通訊等能力838.4空間數據庫管理系統的管理模式GIS應用軟件空間及屬性數據文件GIS應用軟件空間及屬性數據庫擴展DBMS以容納空間數據商業數據庫GIS應用軟件空間及屬性數據庫用戶設計的數據庫GIS應用軟件空間數據庫屬性數據庫管理空間數據的軟件管理屬性數據的DBMS84文件關系數據庫混合管理方案屬性數據建立在RDBMS上，數據存儲和檢索比較可靠、有效；幾何數據采用圖形文件管理，功能較弱，特別是在數據的安全性、一致性、完整性、并發控制方面，比商用數據庫要遜色得多。空間數據分開存儲，數據的完整性有可能遭到破壞。GIS軟件：Arc/Info，MGE，SICARD、GENEMAP等。幾何數據屬性數據ID數據文件數據庫早期圖形用戶界面圖形處理DBMS屬性用戶界面圖形文件庫屬性數據庫GIS用戶界面圖形處理DBMS圖形文件庫屬性數據庫高級語言ODBC協議GIS用戶界面圖形處理DBMS圖形文件庫屬性數據庫高級語言數據庫開發語言數據庫開發數據庫開發85全關系