《空間數(shù)據(jù)結(jié)構(gòu)》PPT課件.pptVIP

,第二章 空間數(shù)據(jù)結(jié)構(gòu),返回,返回,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),一、地理實體（空間實體）-GIS處理對象,1、定義： 指自然界現(xiàn)象和社會經(jīng)濟(jì)事件中不能再分割的單元，它是一個具體有概括性，復(fù)雜性，相對意義的概念。 2、理解： 地理實體類別及實體內(nèi)容的確定是從具體需要出發(fā)的，例如，在全國地圖上由于比例尺很小，武漢就是一個點，這個點不能再分割，可以把武漢定為一個空間實體，而在大比例尺的武漢市地圖上，武漢的許多房屋，街道都要表達(dá)出來，所以武漢必須再分割，不能作為一個空間實體，應(yīng)將房屋，街道等作為研究的地理實體，由此可見，GIS中的空間實體是一個概括，復(fù)雜，相對的概念。,返回,二、地理實體的描述空間數(shù)據(jù),2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、描述的內(nèi)容,反映了實體的三個特征,3、數(shù)據(jù)類型,4、數(shù)據(jù)結(jié)構(gòu),以什么形式存儲和處理,幾何數(shù)據(jù)（空間數(shù)據(jù)、圖形數(shù)據(jù)） 關(guān)系數(shù)據(jù)實體間的鄰接、關(guān)聯(lián)包含等相互關(guān)系 屬性數(shù)據(jù)各種屬性特征和時間 元數(shù)據(jù),矢量、柵格、TIN（專用于地表或特殊造型） RDBMS屬性表-采用MIS較成熟,同物理、化學(xué)等學(xué)科使用的數(shù)據(jù)類型相比，空間數(shù)據(jù)是一種較復(fù)雜的數(shù)據(jù)類型，涉及到空間特征、屬性特征及它們之間關(guān)系的描述,空間元數(shù)據(jù),返回,位置、形狀、尺寸 、 識別碼（名稱）實體的角色、功能、行為、實體的衍生信息 時間 測量方法、編碼方法、空間參考系等,空間特征：地理位置和空間關(guān)系 屬性特征名稱、等級、類別等 時間特征,2、基本特征,2、空間數(shù)據(jù)基本特征,返回,3、空間數(shù)據(jù)類型,1）依據(jù)數(shù)據(jù)來源的不同分為： 地圖數(shù)據(jù) 地形數(shù)據(jù) 屬性數(shù)據(jù) 元數(shù)據(jù) 影象數(shù)據(jù),2）依據(jù)表示對象的不同分為：,3、空間數(shù)據(jù)類型（續(xù)）,返回,三、實體的空間特征,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),（一）空間維數(shù)：有0，1，2，3 維之分，點、線、面、體。,（二）空間特征類型,（三）實體類型組合,返回,在地圖上實體維數(shù)的表示可以改變 點-面 線（單線河）-面（雙線河），通過地圖綜合。,1、點狀實體,2、線狀實體,3、面狀實體,4、體狀實體,1、點狀實體,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),點或節(jié)點、點狀實體。點：有特定位置，維數(shù)為0的物體。,4）角點、節(jié)點Vertex： 表示線段和弧段上的連接點。,1）實體點：用來代表一個實體。,2）注記點：用于定位注記。,3）內(nèi)點：用于負(fù)載多邊形的屬性，存在于多邊形內(nèi)。,返回,2、線狀實體,1）實體長度： 從起點到終點的總長 2）彎曲度： 用于表示像道路拐彎時彎曲的程度。 3）方向性： 如：水流方向，上游下游， 公路，單、雙向之分。,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),具有相同屬性的點的軌跡，線或折線，由一系列的有序坐標(biāo)表示，并有如下特性：,線狀實體包括： 線段，邊界、鏈、弧段、網(wǎng)絡(luò)等。,返回,3、面狀實體（多邊形）,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),面狀實體的如下特征： 1）面積范圍 2）周長 3）獨立性或與其它地物相鄰 如中國及其周邊國家 4）內(nèi)島嶼或鋸齒狀外形： 如島嶼的海岸線封閉所圍成的區(qū)域。 5）重疊性與非重疊性： 如學(xué)校的分區(qū)，菜市場的服務(wù)范圍等都有可能出現(xiàn)交叉重疊現(xiàn)象，而一個城市的各個城區(qū)一般說來不會出現(xiàn)重疊。,是對湖泊、島嶼、地塊等一類現(xiàn)象的描述。 在數(shù)據(jù)庫中由一封閉曲線加內(nèi)點來表示。,返回,4、體、立體狀實體,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,立體狀實體用于描述三維空間中的現(xiàn)象與物體，它具有長度、寬度及高度等屬性，立體狀實體一般具有以下一些空間特征： 體積，如工程開控和填充的土方量。 每個二維平面的面積。 周長。 內(nèi)島。 含有弧立塊或相鄰塊。 斷面圖與剖面圖。,（三）實體類型組合,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,現(xiàn)實世界的各種現(xiàn)象比較復(fù)雜，往往由不同的空間單元組合而成，例如根據(jù)某些空間單元或幾種空間單元的組合將空間問題表達(dá)出來，復(fù)雜實體由簡單實體組合表達(dá)。 點、線、面兩兩之間組合表達(dá)復(fù)雜的空間問題： 如：線面 面-面,可見，用各要素之間的空間關(guān)系，可描述諸多空間問題。空間關(guān)系是GIS數(shù)據(jù)描述和表達(dá)的重要內(nèi)容，一方面它為GIS數(shù)據(jù)庫的有效建立，空間查詢，空間分析，輔助決策等提供了最基本的關(guān)系，另一方面有助于形成標(biāo)準(zhǔn)的SQL空間查詢語言，便于空間特征的存儲，提取，查詢，更新等。,線面,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、區(qū)域包含線：計算區(qū)域內(nèi)線的密度，某省的水系分布情況。 2、線通過區(qū)域：公路上否通過某縣。 3、線環(huán)繞區(qū)域：區(qū)域邊界，搜索左右區(qū)域名稱，中國與哪些國家接壤。 4、線與區(qū)域分離：距離。,面面,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、 包含：島,某省的湖泊分布。 2、 相合：重疊，學(xué)校服務(wù)范圍與菜場服務(wù)范圍重疊區(qū)。 3、 相交：劃分子區(qū)。 4、 相鄰：計算相鄰邊界性質(zhì)和長度，公共連接邊界。 分離：計算距離。,返回,四、實體間空間關(guān)系,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,（一）空間關(guān)系類型,（二）拓?fù)潢P(guān)系,1、 拓?fù)淇臻g關(guān)系： 2、 順序空間關(guān)系： （方向空間關(guān)系） 用上下左右、前后、東南西北等方向性名稱來描述空間實體的順序關(guān)系，算法復(fù)雜，至今沒有很好的解決方法。 3、 度量空間關(guān)系，主要指實體間的距離關(guān)系，遠(yuǎn)近。 1）在地理空間中兩點間的距離有兩種度量方法。 a、沿真實的地球表面進(jìn)行,除與兩點的地理坐標(biāo)有關(guān)外，還與所通過路徑的地形起伏有關(guān)，復(fù)雜,引入第二種。 b、沿地球旋轉(zhuǎn)橢球體的距離量算。 2） 距離類別： 歐氏距離（笛卡爾坐標(biāo)系）、曼哈頓（出租車）距離、時間距離（緯度差）、大地測量距離（大地線）（沿地球大圓經(jīng)過兩個城市中心的距離）。,（二）拓?fù)潢P(guān)系,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、定義： 指圖形保持連續(xù)狀態(tài)下變形，但圖形關(guān)系不變的性質(zhì)。 將橡皮任意拉伸，壓縮，但不能扭轉(zhuǎn)或折疊。,1、定義 2、種類 3、拓?fù)潢P(guān)系的表達(dá) 4、意義,2、種類,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1）關(guān)聯(lián)性： （不同類要素之間）結(jié)點與弧段：如V9與L5,L6,L3 多邊形與弧段：P2與L3,L5,L2 2）鄰接性： (同類元素之間) 多邊形之間、結(jié)點之間。 鄰接矩陣 重疊：- 鄰接：1 不鄰接：0,3）連通性：與鄰接性相類似，指對弧段連接的判別，如用于網(wǎng)絡(luò)分析中確定路徑、 街道是否相通。,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),連通矩陣： 重疊：- 連通：1 不連通：0,4）方向性,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),一條弧段的起點、終點確定了弧段的方向。用于表達(dá)現(xiàn)實中的有向弧段，如城市道路單向，河流的流向等。 5）包含性：指面狀實體包含了哪些線、點或面狀實體。 6）區(qū)域定義：多邊形由一組封閉的線來定義。 7）層次關(guān)系：相同元素之間的等級關(guān)系，武漢市有各個區(qū)組成。 主要的拓?fù)潢P(guān)系：拓?fù)溧徑?、拓?fù)潢P(guān)聯(lián)、拓?fù)浒?拓?fù)潢P(guān)系具體可由4個關(guān)系表來表示： （1） 面-鏈關(guān)系： 面 構(gòu)成面的弧段 （2） 鏈-結(jié)點關(guān)系： 鏈 鏈兩端的結(jié)點 （3） 結(jié)點-鏈關(guān)系： 結(jié)點 通過該結(jié)點的鏈 （4） 鏈面關(guān)系： 鏈 左面 右面,3、拓?fù)潢P(guān)系的表達(dá),對于數(shù)據(jù)處理和GIS空間分析具有重要的意義，因為： 1）拓?fù)潢P(guān)系能清楚地反映實體之間的邏輯結(jié)構(gòu)關(guān)系，它比幾何關(guān)系具有更大的穩(wěn)定性，不隨地圖投影而變化。 2）有助于空間要素的查詢，利用拓?fù)潢P(guān)系可以解決許多實際問題。如某縣的鄰接縣，-面面相鄰問題。又如供水管網(wǎng)系統(tǒng)中某段水管破裂找關(guān)閉它的閥門，就需要查詢該線（管道）與哪些點（閥門）關(guān)聯(lián)。 3）根據(jù)拓?fù)潢P(guān)系可重建地理實體。,2-1空間實體及其描述,第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,4、拓?fù)潢P(guān)系的意義：,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,柵格結(jié)構(gòu)用密集正方形（或三角形，多邊形）將地理區(qū)域劃分為網(wǎng)格陣列。 位置由行，列號定義，屬性為柵格單元的值。,一、圖形表示,點：由單個柵格表達(dá)。 線：由沿線走向有相同屬性取值的一組相鄰柵格表達(dá)。 面：由沿線走向有相同屬性取值的一片柵格表達(dá)。 柵格數(shù)據(jù)表示的是二維表面上的地理數(shù)據(jù)的離散化數(shù)值。在柵格數(shù)據(jù)中，地表被分割為相互鄰接、規(guī)則排列的地塊，每個地塊與一個象元相對應(yīng)。因此，柵格數(shù)據(jù)的比例尺就是柵格(象元)的大小與地表相應(yīng)單元的大小之比，當(dāng)象元所表示的面積較大時，對長度、面積等的量測有較大影響。每個象元的屬性是地表相應(yīng)區(qū)域內(nèi)地理數(shù)據(jù)的近似值，因而有可能產(chǎn)生屬性方面的偏差。,二、柵格數(shù)據(jù)組織,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,針對一個柵格單元對應(yīng)多個屬性值的多層?xùn)鸥裎募?組織方法,組織方法,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,方法c：以層為基礎(chǔ)，每層內(nèi)以多邊形為序記錄多邊形的屬性值和多邊形內(nèi)各象元的坐標(biāo)。節(jié)約用于存儲屬性的空間。將同一屬性的制圖單元的n個象元的屬性只記錄一次，便于地圖分析和制圖處理。,方法a：以象元為記錄序列，不同層上同一象元位置上的各屬性值表示為一個列數(shù)組。N層中只記錄一層的象元位置，節(jié)約大量存儲空間，柵格個數(shù)很多。,方法b：每層每個象元的位置、屬性一一記錄，結(jié)構(gòu)最簡單，但浪費存儲。,三、柵格結(jié)構(gòu)的建立,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、 手工獲取，專題圖上劃分均勻網(wǎng)格，逐個決定其網(wǎng)格代碼。 2、掃描儀掃描專題圖的圖像數(shù)據(jù)行、列、顏色（灰度），定義顏色與屬性對應(yīng)表，用相應(yīng)屬性代替相應(yīng)顏色，得到（行、列、屬性）再進(jìn)行柵格編碼、存貯，即得該專題圖的柵格數(shù)據(jù)。 3、 由矢量數(shù)據(jù)轉(zhuǎn)換而來。 4、 遙感影像數(shù)據(jù)，對地面景象的輻射和反射能量的掃描抽樣，并按不同的光譜段量化后，以數(shù)字形式記錄下來的象素值序列。 5、 格網(wǎng)DEM數(shù)據(jù)，當(dāng)屬性值為地面高程，則為格網(wǎng)DEM，通過DEM內(nèi)插得到。,（一）建立途徑,（二）柵格系統(tǒng)的確定,(三)柵格代碼的確定,（二）柵格系統(tǒng)的確定,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、 柵格坐標(biāo)系的確定 表示具有空間分布特征的地理要素，不論采用什么編碼系統(tǒng)，什么數(shù)據(jù)結(jié)構(gòu)(矢、柵)都應(yīng)在統(tǒng)一的坐標(biāo)系統(tǒng)下，而坐標(biāo)系的確定實質(zhì)是坐標(biāo)系原點和坐標(biāo)軸的確定。 由于柵格編碼一般用于區(qū)域性GIS，原點的選擇常具有局部性質(zhì)，但為了便于區(qū)域的拼接，柵格系統(tǒng)的起始坐標(biāo)應(yīng)與國家基本比例尺地形圖公里網(wǎng)的交點相一致，并分別采用公里網(wǎng)的縱橫坐標(biāo)軸作為柵格系統(tǒng)的坐標(biāo)軸。,2、 柵格單元的尺寸,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1）原則：應(yīng)能有效地逼近空間對象的分布特征，又減少數(shù)據(jù)的冗余度。 格網(wǎng)太大，忽略較小圖斑，信息丟失。 一般講實體特征愈復(fù)雜，柵格尺寸越小，分辨率愈高，然而柵格數(shù)據(jù)量愈大（按分辨率的平方指數(shù)增加）計算機成本就越高，處理速度越慢。 2）方法：用保證最小多邊形的精度標(biāo)準(zhǔn)來確定尺寸經(jīng)驗公式： h為柵格單元邊長 Ai為區(qū)域所有多邊形的面積。,(三)柵格代碼（屬性值）的確定,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,當(dāng)一個柵格單元內(nèi)有多個可選屬性值時，按一定方法來確定柵格屬性值。 1、中心點法：取位于柵格中心的屬性值為該柵格的屬性值。 2、面積占優(yōu)法：柵格單元屬性值為面積最大者，常用于分類較細(xì)，地理類別圖斑較小時。 3、 重要性法：定義屬性類型的重要級別，取重要的屬性值為柵格屬性值，常用于有重要意義而面積較小的要素，特別是點、線地理要素。 4、長度占優(yōu)法每個柵格單元的值由該柵格中線段最長的實體的屬性來確定。,A,B,b,a,a,2,1,四、柵格數(shù)據(jù)編碼方法,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、直接?xùn)鸥窬幋a： 將柵格數(shù)據(jù)看作一個數(shù)據(jù)矩陣，逐行記錄代碼數(shù)據(jù)。 1）每行都從左到右記錄； AAAAABBBAABBAABB 2）奇數(shù)行從左到右，偶數(shù)行從右到左； 特點：最直觀、最基本的網(wǎng)格存貯結(jié)構(gòu)，沒有進(jìn)行任何壓縮數(shù)據(jù)處理。,A A A A A B B B A A B B A A B B,柵格數(shù)據(jù)量大，格網(wǎng)數(shù)多，由于地理數(shù)據(jù)往往有較強的相關(guān)性，即相鄰象元的值往往是相同的。所以，出現(xiàn)了各種柵格數(shù)據(jù)壓縮方法。 數(shù)據(jù)壓縮是將數(shù)據(jù)表示成更緊湊的格式以減少存儲空間的一項技術(shù)。分為： 無損壓縮：在編碼過程中信息沒有丟失，經(jīng)過解碼可恢復(fù)原有的信息-信息 保持編碼。 有損壓縮：為最大限度壓縮數(shù)據(jù)，在編碼中損失一些認(rèn)為不太重要的信息，解碼后，這部分信息無法恢復(fù)。-信息不保持編碼。,2、行程編碼（變長編碼）：,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,將原圖表示的數(shù)據(jù)矩陣變?yōu)閿?shù)據(jù)對： 1）屬性碼，長度，行號（可不要） 長度：連續(xù)相同碼值的柵格個數(shù)。 2）屬性碼，點位,特點： 對于游程長度編碼，區(qū)域越大，數(shù)據(jù)的相關(guān)性越強，則壓縮越大，適用于類型區(qū)域面積較大的專題圖，而不適合于類型連續(xù)變化或類別區(qū)域分散的分類圖（壓縮比與圖的復(fù)雜程度成反比）。 這種編碼在柵格加密時，數(shù)據(jù)量不會明顯增加，壓縮率高，并最大限度地保留原始柵格結(jié)構(gòu)，編碼解碼運算簡單，且易于檢索，疊加，合并等操作，這種編碼應(yīng)用廣泛。,A A A A A B B B A A B B A A B B,3、塊碼 - 游程編碼向二維擴(kuò)展,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,采用方形區(qū)域作為記錄單元，每個記錄單元包括相鄰的若干柵格。,數(shù)據(jù)對組成：（初始行、列，半徑，屬性值）,特點： 具有可變分辨率，即當(dāng)屬性變化小時圖塊大，對于大塊圖斑記錄單元大，分辨率低，壓縮比高。 小塊圖斑記錄單元小，分辨率高，壓縮比低 所以，與行程編碼類似，隨圖形復(fù)雜程度的提高而降低分辯率。,依次掃描，編過的不重復(fù)。,1 2 3 4 5 6 7 8 1 0 4 4 7 7 7 7 7 2 4 4 4 4 4 7 7 7 3 4 4 4 4 8 8 7 7 4 0 0 4 8 8 8 7 7 5 0 0 8 8 8 8 7 8 6 0 0 0 8 8 8 8 8 7 0 0 0 0 8 8 8 8 8 0 0 0 0 0 8 8 8,如：（1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),4、鏈?zhǔn)骄幋a、Freeman 鏈碼、邊界鏈碼,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1）首先定義一個3x3窗口，中間柵格的走向有8種可能，并將這8種可能07進(jìn)行編碼。 2）記下地物屬性碼和起點行、列后，進(jìn)行追蹤，得到矢量鏈.,將柵格數(shù)據(jù)（線狀地物面域邊界）表示為矢量鏈的記錄,鏈?zhǔn)骄幋a表,a,a,a,a,a,a,b,優(yōu)點：鏈碼可有效地存貯壓縮柵格數(shù)據(jù)，便于面積、長度、轉(zhuǎn)折方向和邊界、線段凹凸度的計算。 缺點：不易做邊界合并，插入操作、編輯較困難（對局部修改將改變整體結(jié)構(gòu)）。區(qū)域空間分析困難，相鄰區(qū)域邊界被重復(fù)存儲。,5、四叉樹編碼,五、四叉樹編碼,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、 基本思想： 將2n2n象元組成的圖像(不足的用背景補上) 按四個象限進(jìn)行遞歸分割， 并判斷屬性是否單一， 單一：不分。 不單一：遞歸分割。 最后得到一顆四分叉的倒向樹。 2、 四叉樹的樹形表示： 用一倒立樹表示這種分割和分割結(jié)果。 根：整個區(qū)域 高：深度、分幾級，幾次分割 葉：不能再分割的塊 樹叉：還需分割的塊 每個樹叉均有4個分叉，叫四叉樹。,（一）四叉樹概述： 一種可變分率的非均勻網(wǎng)格系統(tǒng)。是最有效的柵格數(shù)據(jù)壓縮編碼方法之一,3、 編碼方法,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1）常規(guī)四叉樹 記錄這棵樹的葉結(jié)點外，中間結(jié)點，結(jié)點之間的聯(lián)系用指針聯(lián)系， 每個結(jié)點需要6個變量： 父結(jié)點指針、四個子結(jié)點的指針和本結(jié)點的屬性值。,指針不僅增加了數(shù)據(jù)的存儲量，還增加了操作的復(fù)雜性：如層次數(shù)（分割次數(shù)）由從父結(jié)點移到根結(jié)點的次數(shù)來確定，結(jié)點所代表的圖像塊的位置需要從根節(jié)點開始逐步推算下來。所以，常規(guī)四叉樹并不廣泛用于存儲數(shù)據(jù)，其價值在于建立索引文件，進(jìn)行數(shù)據(jù)檢索。,2）線性四叉樹,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,記錄葉結(jié)點的位置，深度（幾次分割）和屬性。 地址碼（定位碼、Morton碼） 四進(jìn)制、十進(jìn)制 優(yōu)點： 存貯量小，只對葉結(jié)點編碼，節(jié)省了大量中間結(jié)點的存儲，地址碼隱含著結(jié)點的分割路徑和分割次數(shù)。 線性四叉樹可直接尋址，通過其坐標(biāo)值直接計算其Morton碼，而不用建立四叉樹。 定位碼容易存儲和執(zhí)行實現(xiàn)集合相加等組合操作。,（二）四進(jìn)制的Morton碼,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、 方法1： 四叉樹從上而下（形成）（從整體開始） 由葉結(jié)點找Morton碼。 A、分割一次，增加一位數(shù)字，大分割在前，小分割在后。所以，碼的位數(shù)表示分割的次數(shù)。 B、每一個位均是不大于3的四進(jìn)制數(shù)，表達(dá)位置。 由Morton找出四叉樹葉結(jié)點的具體位置。,03,B,A,2、 方法2：四叉樹自下而上合并的方法,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1）計算每個柵格對應(yīng)的MQ MQ=2*Ib+Jb I,J化為二進(jìn)制Ib,Jb 看最大的I,J,不足在前補零。 其始行列號從0計。 2) 按碼的升序排成線性表，放在連續(xù)的內(nèi)存塊中。 3）依次檢查每四個相鄰的MQ對應(yīng)的屬性值，相同合并（不同碼位去掉），不同則存盤,直到?jīng)]有能夠合并的子塊為止。,（三）十進(jìn)制的Morton碼-MD,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、一種按位操作的方法： 如行為2、列為3的柵格的MD 步驟： (1)行、列號為二進(jìn)制 Ib= 1 0 Jb= 1 1 (2)I行J列交叉 1 1 0 1 = 13 (3)再化為十進(jìn)制. 實質(zhì)上是按左上、右上、左下、右下的順序，從零開始對每個柵格進(jìn)行自然編碼。,四進(jìn)制Morton碼直觀上切合四叉樹分割，但許多語言不支持四進(jìn)制變量，需用十進(jìn)制表示Morton碼.,2、把一幅2n2n的圖像壓縮成線性四叉樹的過程,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,1、按Morton碼把圖象讀入一維數(shù)組。 2、相鄰的四個象元比較，一致的合并，只記錄第一個象元的Morton碼。循環(huán)比較所形成的大塊，相同的再合并，直到不能合并為止。 3、進(jìn)一步用游程長度編碼壓縮。壓縮時只記錄第一個象元的Morton碼。,右圖的壓縮處理過程為： 1、按Morton碼讀入一維數(shù)組。 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 B 2、四相鄰象元合并，只記錄第一個象元的Morton碼。 0 1 2 3 4 5 6 7 8 12 A A A B A A B B A B 3、由于不能進(jìn)一步合并，則用游程長度編碼壓縮。 0 3 4 6 8 12 A B A B A B,（四）四叉樹優(yōu)缺點,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),優(yōu)點： 1）對于團(tuán)塊圖像，四叉樹表示法占用空間比網(wǎng)絡(luò)法要少得多，四叉樹表示法基本上是一種非冗余表示法。 2）四叉樹具有可變率或多重分辯率的特點使得它有很好的應(yīng)用前景，適用于處理凝聚性或呈塊狀分布的空間數(shù)據(jù)，特別適用于處理分布不均勻的塊狀空間數(shù)據(jù)，但不適用于連續(xù)表面（如地形）或線狀地物。 此外，目前應(yīng)用四叉樹還存下列問題： 1) 矢/柵正反變換還不理想。 2) 建立四叉樹耗費機時很多。 3) 四叉樹雖可修改，但很費事（具體的數(shù)據(jù)結(jié)構(gòu)中會提到）,4) 四叉樹未能直接表示物體間的拓?fù)潢P(guān)系。,2-3 柵格數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),返回,5) 與非樹表示法比較，四叉樹表示法的缺點在于轉(zhuǎn)換的不穩(wěn)定性或叫滑動變異 例如，兩個圖像的差異僅由于平移，就會構(gòu)成極為不同的四叉樹，因而很難根據(jù)四叉樹來判斷這兩個圖像是否全同，故不利于做形狀分析和模式識別，,6) 一個物體的圖像在構(gòu)成四叉樹時會被分割到若干個象限中，使它失去了內(nèi)在的相關(guān)性。,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),一、圖形表示,返回,摘自 張超,二、矢量數(shù)據(jù)的獲取方式,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1) 由外業(yè)測量獲得 可利用測量儀器自動記錄測量成果(常稱為電子手薄)，然后轉(zhuǎn)到地理數(shù)據(jù)庫中。 2)由柵格數(shù)據(jù)轉(zhuǎn)換獲得 利用柵格數(shù)據(jù)矢量化技術(shù)，把柵格數(shù)據(jù)轉(zhuǎn)換為矢量數(shù)據(jù)。 3)跟蹤數(shù)字化 用跟蹤數(shù)字化的方法，把地圖變成離散的矢量數(shù)據(jù)。,返回,三、矢量數(shù)據(jù)組織,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),矢量數(shù)據(jù)表示時應(yīng)考慮以下問題： 矢量數(shù)據(jù)自身的存貯和處理。 與屬性數(shù)據(jù)的聯(lián)系。 矢量數(shù)據(jù)之間的空間關(guān)系(拓?fù)潢P(guān)系)。,以點為例：,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),坐標(biāo) 識別符 若是簡單點要素如獨立樹、電線竿、三角點，符號、 有關(guān)屬性中包括 比例尺、方向 若是注記點，記錄有關(guān)字符的大小、方向、字體、排列等 若是結(jié)點Vertex：符號：指針、與線相交的角度。 其它屬性 : 三角點設(shè)立年代、材料等,線（符號、方向）、面（符號）都有相應(yīng)的相關(guān)屬性，在此，看看矢量結(jié)構(gòu)中關(guān)于幾何位置坐標(biāo)的編碼方式,返回,四、矢量數(shù)據(jù)編碼方式,（spaghetti）- 面條模型:以實體為單位記錄其坐標(biāo),2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),缺點： 1、相鄰多邊形的公共邊界被數(shù)字化并存儲兩次，造成數(shù)據(jù)冗余和碎屑多邊形數(shù)據(jù)不一致，浪費空間，導(dǎo)致雙重邊界不能精確匹配。 2、自成體系，缺少多邊形的鄰接信息，無拓?fù)潢P(guān)系，難以進(jìn)行鄰域處理，如消除多邊形公共邊界，合并多邊形。 3、島作為一個單個圖形，沒有與外界多邊形聯(lián)系。不易檢查拓?fù)溴e誤。 所以，這種結(jié)構(gòu)只用于簡單的制圖系統(tǒng)中，顯示圖形。,（一）實體式,優(yōu)點：結(jié)構(gòu)簡單、直觀、易實現(xiàn)以實體為單位的運算和顯示。,返回,（二）索引式（樹狀）,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),對所有點的坐標(biāo)按順序建坐標(biāo)文件，再建點與邊（線）、線與多邊形的索引文件。,Map,1、點文件：,索引文件：,3、面文件：,2、弧段文件:,與實體式相比： 優(yōu)點：用建索引的方法消除多邊形數(shù)據(jù)的冗余和不一致，鄰接信息、島信息可在多邊形文件中通過是否公共弧段號的方式查詢。 缺點：表達(dá)拓?fù)潢P(guān)系較繁瑣，給相鄰運算、消除無用邊、處理島信息、檢索拓?fù)潢P(guān)系等帶來困難，以人工方式建立編碼表，工作量大，易出錯。,返回,（三）雙重獨立式編碼,簡稱DIME(Dual Independent Map Encoding)，是美國人口統(tǒng)計系統(tǒng)采用的一種編碼方式，是一種拓?fù)渚幋a結(jié)構(gòu)。,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、點文件,2、線文件:線文件是以線段為記錄單位,3、面文件,關(guān)聯(lián),鄰接,關(guān)聯(lián),連通,拓?fù)潢P(guān)系明確,在DIME中做如下改進(jìn)： 將以線段為記錄單位改為以弧段為單位,鏈狀雙重獨立式編碼,返回,（四）鏈狀雙重獨立式編碼-拓?fù)鋽?shù)據(jù)結(jié)構(gòu),2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、弧段坐標(biāo)文件：,2、弧段文件：鏈面，鏈結(jié)點關(guān)系,3、面文件,4、點拓?fù)湮募?結(jié)點鏈關(guān)系,在拓?fù)浣Y(jié)構(gòu)中，多邊形（面）的邊界被分割成一系列的線（弧、鏈、邊）和點（結(jié)點）等拓?fù)湟?，點、線、面之間的拓?fù)潢P(guān)系在屬性表中定義，多邊形邊界不重復(fù)。,返回,鏈狀雙重獨立式編碼 特點,拓?fù)潢P(guān)系明確，也能表達(dá)島信息，而且以弧段為記錄單位，滿足實際應(yīng)用需要。因為一般數(shù)字化一條街道時，必然有許多中間點，但我們在做空間分析是卻沒有必要以這些中間點所組成的折線為研究對象，而應(yīng)以整條弧段（某條街道）為研究對象. 被一些成熟的商品化軟件采用，如ARC/INFO軟件。 例：ARC文件：二進(jìn)制文件: 弧段號 點數(shù) 坐標(biāo)串 在GIS數(shù)據(jù)輸入中，建拓?fù)涫侵附o圖形數(shù)據(jù)（點、線、面）增加拓?fù)浣Y(jié)構(gòu)，如ARC/INFO中，在ARCEDIT中輸入圖形后，需用BUILD 建圖形拓?fù)?，具體生成許多文件，如AAT，PAT等. INFO：屬性表 如AAT（Arc Attribute Table）,2-2 矢量數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),用戶標(biāo)識碼，表明地物類型 當(dāng)圖形數(shù)據(jù)修改、刪除、增加點、線、面要素后，其拓?fù)潢P(guān)系也發(fā)生改變，所以，需重新建拓?fù)洹?返回,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),一、矢、柵優(yōu)缺點：,矢量、柵格數(shù)據(jù)結(jié)構(gòu)的選擇,柵格結(jié)構(gòu):大范圍小比例尺的自然資源、環(huán)境、農(nóng)林業(yè)等區(qū)域問題的研究。,矢量結(jié)構(gòu)：城市分區(qū)或詳細(xì)規(guī)劃、土地管理、公用事業(yè)管理等方面的應(yīng)用。,在GIS建立過程中，應(yīng)根據(jù)應(yīng)用目的和應(yīng)用特點、可能獲得的數(shù)據(jù)精度以及地理信息系統(tǒng)軟件和硬件配置情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)。,返回,二、矢柵一體化概念,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),將矢量面對目標(biāo)的方法和柵格元子充填的方法結(jié)合起來，具體采用填滿線狀目標(biāo)路徑和充填面狀目標(biāo)空間的方法作為一體化數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)。 線狀地物：除記錄原始取樣點外，還記錄路徑所通過的柵格。 面狀地物：除記錄它的多邊形周邊以外，還包括中間的面域柵格。 一方面，它保留了矢量的全部性質(zhì)，以目標(biāo)為單元直接聚集所有的位置信息，并能建立拓?fù)潢P(guān)系； 另一方面，它建立了柵格與地物的關(guān)系，即路徑上的任一點都直接與目標(biāo)建立了聯(lián)系。,從原理上說，這是一種以矢量的方式來組織柵格數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)。,返回,三、三個約定和細(xì)分格網(wǎng)法,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),為便于組織數(shù)據(jù)，首先作如下約定： a. 地面上的點狀地物是地球表面上的點，它僅有空間位置，沒有形狀和面積，在計算機內(nèi)部僅有一個位置數(shù)據(jù)。,為提高柵格表示精度，采用細(xì)分格網(wǎng)法： 將一對X,Y坐標(biāo)用兩個Morton碼代替： 前一M1表示該點（采樣點或附加的交叉點）所在基本格網(wǎng)的地址碼，后者M(jìn)2 表示該點對應(yīng)的細(xì)分格網(wǎng)的Morton碼，既顧全整體定位，又保證精度。,b. 地面上的線狀地物是地球表面的空間曲線，它有形狀但沒有面積，它在平面上的投影是一連續(xù)不間斷的直線或曲線，在計算機內(nèi)部需要用一組元子填滿整個路徑。,c. 地面上的面狀地物是地球表面的空間曲面，并具有形狀和面積，它在平面上的投影是由邊界包圍的緊致空間和一組填滿路徑的元子表達(dá)的邊界組成。,x,y,M1 M2,返回,四、一體化數(shù)據(jù)結(jié)構(gòu)設(shè)計,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),線性四叉樹(Morton)是基本數(shù)據(jù)格式，三個約定設(shè)計點、線、面數(shù)據(jù)結(jié)構(gòu)的基本依據(jù)，細(xì)分格網(wǎng)法保證足夠精度。,約定1，點僅有位置、沒有形狀和面積，只要將點的坐標(biāo)轉(zhuǎn)化為地址碼M1 和M2 ,結(jié)構(gòu)簡單靈活，便于點的插入和刪除，還能處理一個柵格內(nèi)包含多個點狀目標(biāo)的情況。,1、點狀地物和結(jié)點的數(shù)據(jù)結(jié)構(gòu),返回,2、線狀地物的數(shù)據(jù)結(jié)構(gòu),2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),約定（2），線狀地物有形狀但沒有面積，沒有面積意味著只要用一串?dāng)?shù)據(jù)表達(dá)每個線狀地物的路徑即可，將該線狀地物經(jīng)過的所有柵格的地址全部記錄下來。仿照矢量數(shù)據(jù)組織的鏈狀雙重獨立式編碼，以弧段為記錄單位。,弧段的數(shù)據(jù)結(jié)構(gòu):,線狀地物的數(shù)據(jù)結(jié)構(gòu):,返回,3、面狀地物的數(shù)據(jù)結(jié)構(gòu),2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1) 弧段文件,2）帶指針的二維行程碼,葉結(jié)點的屬性值,改為指向該地物的下一個子塊的循環(huán)指針,邊界弧段-形狀,面域,循環(huán)指針指向該地物下一個子塊的地址碼，并在最后指向該地物本身,返回,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),用循環(huán)指針將同屬于一個目標(biāo)的葉結(jié)點鏈接起來,只要進(jìn)入第一塊就可以順著指針直接提取該地物的所有子塊，從而避免像柵格數(shù)據(jù)那樣為查詢某一個目標(biāo)需遍歷整個矩陣，大大提高了查詢速度。,返回,0,8,32,40,46,3）面文件,2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),這種數(shù)據(jù)結(jié)構(gòu)是面向地物的，具有矢量的特點。通過面狀地物的標(biāo)識號可以找到它的邊界弧段并順著指針提取所有的中間面塊。同時它又具有柵格的全部特性，二維行程本身就是面向位置的結(jié)構(gòu)，帶指針的二維行程碼中的Morton碼表達(dá)了位置的相互關(guān)系，前后M碼之差隱含了該子塊的大小。給出任意一點的位置都可順著指針找到面狀地物的標(biāo)識號確定是哪一個地物。,返回,4、復(fù)雜地物的數(shù)據(jù)結(jié)構(gòu),2-4 矢柵一體化數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),由幾個或幾種點、線、面狀簡單地物組成的地物稱為復(fù)雜地物。例如將一條公路上的中心線、交通燈、立交橋等組合為一個復(fù)雜地物，用一個標(biāo)識號表示。復(fù)雜地物的數(shù)據(jù)結(jié)構(gòu)如表7所示。,返回,2-5 三維數(shù)據(jù)結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),目前GIS主要還停留在處理地球表面的數(shù)據(jù)，若數(shù)據(jù)是地表以下或以上，則先將它投影到地表，再進(jìn)行處理，其實質(zhì)是以二維的形式來模擬、處理任何數(shù)據(jù)，在有些領(lǐng)域可行，但涉及到三維問題的處理時，往往力不從心。 二維V=f(x,y)，在不同的層V的含義不同，當(dāng)V表示的是高程時，就是DEM。由于地形三維視圖的原因，人們常把DEM誤認(rèn)為是三維模型。但從本質(zhì)上講，DEM是二維的，因為它只能表示地表的信息，不能對地表內(nèi)部進(jìn)行有效的表示。目前，人們常把DEM稱為2.5維的數(shù)據(jù)模型。 真三維模型V=f(x,y,z)，z是一自變量，不受x,y的影響。三維GIS的要求與二維GIS相似，但在數(shù)據(jù)采集，系統(tǒng)維護(hù)和界面設(shè)計等方面比二維GIS復(fù)雜得多，如三維數(shù)據(jù)的組織與重建，三維變換、查詢、運算、分析、維護(hù)等方面。下面主要介紹三維數(shù)據(jù)結(jié)構(gòu)。同樣，三維結(jié)構(gòu)存在柵格和矢量兩種形式。 柵格：將地理實體的三維空間分成細(xì)小單元-體元。普遍用八叉樹 矢量：x,y,z，抽象為點、線、面、體，面構(gòu)成體。方法多種，常用三維邊界表示法。,返回,一、概述,二、八叉樹結(jié)構(gòu),第二章 GIS 數(shù)據(jù)結(jié)構(gòu),1、思想： 四叉樹在三維空間的推廣。 將要表示的形體V放在一個充分大的正方體C內(nèi)，C的邊長為2n，不斷用兩個與XOY、XOZ的平