計(jì)算機(jī)地圖制圖中國礦業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)PPT課件

1、第二章 地圖數(shù)據(jù)結(jié)構(gòu)第1頁/共91頁2.1 2.1 空間實(shí)體及其描述空間實(shí)體及其描述2.2 2.2 矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)2.3 2.3 柵格數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu)2.4 2.4 矢柵一體化數(shù)據(jù)結(jié)構(gòu)矢柵一體化數(shù)據(jù)結(jié)構(gòu)2.5 2.5 三維數(shù)據(jù)結(jié)構(gòu)三維數(shù)據(jù)結(jié)構(gòu)第2頁/共91頁2.1 2.1 空間實(shí)體及其描述空間實(shí)體及其描述1 1）地理實(shí)體2 2）地理實(shí)體的描述3 3）實(shí)體的空間特征4 4）實(shí)體間的關(guān)系第3頁/共91頁2.2 2.2 矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)1 1）圖形表示2 2）獲取方式3 3）組織4 4）編碼方式第4頁/共91頁2.3 2.3 柵格數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu)1 1）圖形表示2 2）數(shù)據(jù)

2、組織3 3）柵格結(jié)構(gòu)的建立4 4）柵格數(shù)據(jù)編碼第5頁/共91頁2.4 2.4 矢柵一體化數(shù)據(jù)結(jié)構(gòu)矢柵一體化數(shù)據(jù)結(jié)構(gòu)1 1）矢柵一體化概念2 2）三個(gè)約定和細(xì)分格網(wǎng)法3 3）一體化數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)第6頁/共91頁2.5 2.5 三維數(shù)據(jù)結(jié)構(gòu)三維數(shù)據(jù)結(jié)構(gòu)1 1）概述2 2）八叉樹結(jié)構(gòu)3 3）三維邊界表示法第7頁/共91頁本章重點(diǎn)本章重點(diǎn)點(diǎn)、線、面狀實(shí)體；空間數(shù)據(jù)拓?fù)潢P(guān)系；矢量數(shù)據(jù)結(jié)構(gòu)、柵格數(shù)據(jù)結(jié)構(gòu)；第8頁/共91頁空間實(shí)體（地理實(shí)體）空間實(shí)體（地理實(shí)體） 自然界現(xiàn)象和社會(huì)經(jīng)濟(jì)事件中不能再分割的單元，具有概括性，復(fù)雜性，相對(duì)意義。2.1 2.1 空間實(shí)體及其描述空間實(shí)體及其描述點(diǎn)狀實(shí)體-0-0維線狀實(shí)體

3、-1-1維面狀實(shí)體-2-2維體狀實(shí)體-3-3維第9頁/共91頁點(diǎn)狀實(shí)體點(diǎn)狀實(shí)體 有特定位置，維數(shù)為0 0的物體。 實(shí)體點(diǎn)注記點(diǎn)內(nèi)點(diǎn)節(jié)點(diǎn)（VertexVertex）拐點(diǎn)第10頁/共91頁線狀實(shí)體線狀實(shí)體 具有相同屬性的點(diǎn)的軌跡，由一系列有序坐標(biāo)表示的物體。實(shí)體長度彎曲度方向性第11頁/共91頁面狀實(shí)體（多邊形）面狀實(shí)體（多邊形） 是對(duì)湖泊、島嶼、地塊等一類現(xiàn)象的描述。在數(shù)據(jù)庫中由一封閉曲線加內(nèi)點(diǎn)來表示。面積范圍周長獨(dú)立性內(nèi)島嶼或鋸齒狀外形重疊性與非重疊性第12頁/共91頁體狀實(shí)體（多邊形）體狀實(shí)體（多邊形） 描述三維空間中的現(xiàn)象的物體。體積周長內(nèi)島含有弧立塊或相鄰塊斷面圖與剖面圖第13頁/共91

4、頁實(shí)體類型組合實(shí)體類型組合為地圖數(shù)據(jù)庫的有效建立，空間查詢，空間分析，輔助決策等提供了最基本的關(guān)系。有助于形成標(biāo)準(zhǔn)的SQLSQL空間查詢語言，便于空間特征的存儲(chǔ)，提取，查詢，更新等。第14頁/共91頁線面1 1、區(qū)域包含線：計(jì)算區(qū)域內(nèi)線的密度，某省的水系分布情況。2 2、線通過區(qū)域：公路上否通過某縣。3 3、線環(huán)繞區(qū)域：區(qū)域邊界，搜索左右區(qū)域名稱，中國與哪些國家接壤。4 4、線與區(qū)域分離：距離。 第15頁/共91頁面面1 1、包含：島, ,某省的湖泊分布。2 2、相合：重疊，學(xué)校服務(wù)范圍與菜場(chǎng)服務(wù)范圍重疊區(qū)。3 3、相交：劃分子區(qū)。4 4、相鄰：計(jì)算相鄰邊界性質(zhì)和長度，公共連接邊界。5 5、分

5、離：計(jì)算距離。 學(xué)校菜場(chǎng)第16頁/共91頁空間實(shí)體的描述空間實(shí)體的描述空間數(shù)據(jù)空間數(shù)據(jù)內(nèi)容 數(shù)據(jù)類型數(shù)據(jù)結(jié)構(gòu)幾何數(shù)據(jù)（空間數(shù)據(jù)、圖形數(shù)據(jù)） 關(guān)系數(shù)據(jù)實(shí)體間的鄰接、關(guān)聯(lián)包含等相互關(guān)系 屬性數(shù)據(jù)各種屬性特征和時(shí)間元數(shù)據(jù) 矢量、柵格、TINTIN（專用于地表或特殊造型） RDBMSRDBMS屬性表- -采用MISMIS較成熟 位置、形狀、尺寸 、識(shí)別碼（名稱）實(shí)體的角色、功能、行為、實(shí)體的衍生信息時(shí)間測(cè)量方法、編碼方法、空間參考系等 空間特征：地理位置和空間關(guān)系屬性特征名稱、等級(jí)、類別等時(shí)間特征基本特征第17頁/共91頁空間數(shù)據(jù)的基本特征空間數(shù)據(jù)的基本特征第18頁/共91頁空間數(shù)據(jù)的類型空間數(shù)據(jù)的類

6、型1 1）依據(jù)數(shù)據(jù)來源： 地圖數(shù)據(jù)、地形數(shù)據(jù)、屬性數(shù)據(jù)、元數(shù)據(jù)、影象數(shù)據(jù)。第19頁/共91頁2 2）依表示對(duì)象：第20頁/共91頁第21頁/共91頁實(shí)體間空間關(guān)系實(shí)體間空間關(guān)系1 1、拓?fù)淇臻g關(guān)系 2 2、順序空間關(guān)系（方向空間關(guān)系）3 3、度量空間關(guān)系1 1）地理空間中兩點(diǎn)間的距離有兩種度量方法：2 2）距離類別：上下左右、前后、東南西北。a a、沿真實(shí)地球表面。b b、沿地球旋轉(zhuǎn)橢球體距離。歐氏距離、時(shí)間距離、大地測(cè)量距離。第22頁/共91頁1 1、定義： 指圖形保持連續(xù)狀態(tài)下變形，但圖形關(guān)系不變的性質(zhì)。將橡皮任意拉伸，壓縮，但不能扭轉(zhuǎn)或折疊。拓?fù)潢P(guān)系拓?fù)潢P(guān)系 拓?fù)渥儞Q（橡皮變換）第23頁

7、/共91頁非拓?fù)鋵傩苑峭負(fù)鋵傩裕◣祝◣缀螌傩裕┖螌傩裕┩負(fù)鋵傩酝負(fù)鋵傩裕]發(fā)生變化的屬（沒發(fā)生變化的屬性）性）兩點(diǎn)間距離兩點(diǎn)間距離一點(diǎn)指向另一點(diǎn)一點(diǎn)指向另一點(diǎn)的方向的方向弧段長度、區(qū)域弧段長度、區(qū)域周長、面積等周長、面積等一個(gè)點(diǎn)在一條弧段的端點(diǎn)一個(gè)點(diǎn)在一條弧段的端點(diǎn) 一條弧是一簡單弧段一條弧是一簡單弧段 一個(gè)一個(gè)點(diǎn)在一個(gè)區(qū)域的邊界上點(diǎn)在一個(gè)區(qū)域的邊界上一個(gè)點(diǎn)在一個(gè)區(qū)域的內(nèi)部一個(gè)點(diǎn)在一個(gè)區(qū)域的內(nèi)部/ /外部外部一個(gè)點(diǎn)在一個(gè)環(huán)的內(nèi)一個(gè)點(diǎn)在一個(gè)環(huán)的內(nèi)/ /外部外部一個(gè)面是一個(gè)簡單面一個(gè)面是一個(gè)簡單面一個(gè)面的連通性一個(gè)面的連通性第24頁/共91頁2 2、種類：1 1）關(guān)聯(lián)性（不同類要素間）結(jié)點(diǎn)與弧段：

8、如V9V9與L5,L6,L3L5,L6,L3多邊形與弧段：P2P2與L3,L5,L2L3,L5,L22 2）鄰接性： ( (同類元素之間) )多邊形之間、結(jié)點(diǎn)之間。第25頁/共91頁鄰接矩陣：重疊： 鄰接：1 1 不鄰接：0 0連通矩陣：重疊： 連通：1 1 不連通：0 0第26頁/共91頁3)3)方向性：一條弧段的起點(diǎn)、終點(diǎn)確定了弧段的方向。用于表達(dá)現(xiàn)實(shí)中的有向弧段，如城市道路單向，河流的流向等。4)4)包含性：指面狀實(shí)體包含了哪些線、點(diǎn)或面狀實(shí)體。5)5)區(qū)域定義：多邊形由一組封閉的線來定義。6)6)層次關(guān)系：相同元素之間的等級(jí)關(guān)系，武漢市有各個(gè)區(qū)組成。第27頁/共91頁3 3、拓?fù)潢P(guān)系的

9、表達(dá)：拓?fù)潢P(guān)系具體可由4 4個(gè)關(guān)系表來表示：（1 1）面-鏈關(guān)系： 面 構(gòu)成面的弧段（2 2）鏈-結(jié)點(diǎn)關(guān)系：鏈 鏈兩端的結(jié)點(diǎn)（3 3）結(jié)點(diǎn)-鏈關(guān)系：結(jié)點(diǎn) 通過該結(jié)點(diǎn)的鏈（4 4）鏈面關(guān)系： 鏈 左面 右面第28頁/共91頁4 4、拓?fù)潢P(guān)系的意義：1 1）能清楚地反映實(shí)體之間的邏輯結(jié)構(gòu)關(guān)系。它比幾何關(guān)系具有更大的穩(wěn)定性，不隨地圖投影變化。2 2）有助于空間要素的查詢，利用拓?fù)潢P(guān)系可以解決許多實(shí)際問題。3 3）根據(jù)拓?fù)潢P(guān)系可重建地理實(shí)體。第29頁/共91頁哥尼斯堡七橋問題哥尼斯堡七橋問題第30頁/共91頁2.2 2.2 矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)圖形表示圖形表示第31頁/共91頁獲取方式獲取方式1)

10、1) 外業(yè)測(cè)量（電子手簿）外業(yè)測(cè)量（電子手簿）2 2）柵格數(shù)據(jù)轉(zhuǎn)換（柵格數(shù)據(jù)矢量化）柵格數(shù)據(jù)轉(zhuǎn)換（柵格數(shù)據(jù)矢量化）3 3）跟蹤數(shù)字化）跟蹤數(shù)字化第32頁/共91頁矢量數(shù)據(jù)組織矢量數(shù)據(jù)組織應(yīng)考慮以下問題：矢量數(shù)據(jù)自身的存貯和處理。與屬性數(shù)據(jù)的聯(lián)系。矢量數(shù)據(jù)之間的空間關(guān)系( (拓?fù)潢P(guān)系) )。第33頁/共91頁以點(diǎn)為例： 線（符號(hào)、方向）、面（符號(hào)）都有相應(yīng)的相關(guān)屬性（矢量結(jié)構(gòu)中關(guān)于幾何位置坐標(biāo)的編碼方式）。第34頁/共91頁矢量數(shù)據(jù)的編碼方式矢量數(shù)據(jù)的編碼方式1 1）實(shí)體式面條模型（spaghettispaghetti）: :以實(shí)體為單位記錄坐標(biāo)1234567891011 1213 1415P

11、PP PP P優(yōu)點(diǎn)：結(jié)構(gòu)簡單、直觀、易實(shí)現(xiàn)以實(shí)體為單位的運(yùn)算和顯示。第35頁/共91頁缺點(diǎn)： 1 1、相鄰多邊形的公共邊界被數(shù)字化并存儲(chǔ)兩次，造成數(shù)據(jù)冗余和碎屑多邊形（數(shù)據(jù)不一致），浪費(fèi)空間，雙重邊界不能精確匹配。2 2、自成體系，缺少多邊形的鄰接信息，無拓?fù)潢P(guān)系，難以進(jìn)行鄰域處理。3 3、島作為一個(gè)單個(gè)圖形，沒有與外界多邊形聯(lián)系。不易檢查拓?fù)溴e(cuò)誤。 所以，這種結(jié)構(gòu)只用于簡單的制圖系統(tǒng)中顯示圖形。第36頁/共91頁2 2）索引式（樹狀） 對(duì)所有點(diǎn)的坐標(biāo)按順序建坐標(biāo)文件，再建點(diǎn)與邊（線）、線與多邊形的索引文件。1234567891011 1213 1415P PP PP P第37頁/共91頁與實(shí)

12、體式相比：優(yōu)點(diǎn)：用建索引的方法消除多邊形數(shù)據(jù)的冗余和不一致，鄰接信息、島信息可在多邊形文件中通過是否公共弧段號(hào)的方式查詢。缺點(diǎn)：表達(dá)拓?fù)潢P(guān)系較繁瑣，給相鄰運(yùn)算、消除無用邊、處理島信息、檢索拓?fù)潢P(guān)系等帶來困難，以人工方式建立編碼表，工作量大，易出錯(cuò)。第38頁/共91頁3 3）雙重獨(dú)立式編碼 DIME(Dual Independent Map Encoding)DIME(Dual Independent Map Encoding)，是美國人口統(tǒng)計(jì)系統(tǒng)采用的一種編碼方式，是一種拓?fù)渚幋a結(jié)構(gòu)。1234567891011 1213 1415P PP PP P拓?fù)潢P(guān)系明確第39頁/共91頁4 4）鏈狀雙重

13、獨(dú)立式編碼以線段為記錄單位改為以弧段為單位。1234567891011 1213 1415P PP PP P第40頁/共91頁特點(diǎn)：拓?fù)潢P(guān)系明確，以弧段為記錄單位，滿足實(shí)際應(yīng)用。被一些成熟的商品化軟件采用，如ARC/INFOARC/INFO軟件。例：ARCARC文件： INFOINFO：屬性表AATAAT（Arc Attribute TableArc Attribute Table）第41頁/共91頁2.3 2.3 柵格數(shù)據(jù)結(jié)構(gòu)柵格數(shù)據(jù)結(jié)構(gòu)圖形表示圖形表示 用密集正方形（或三角形，多邊形）將地理區(qū)域劃分為網(wǎng)格陣列。位置由行，列號(hào)定義，屬性為柵格單元的值。柵格數(shù)據(jù)的比例尺就是柵格( (象元) )

14、的大小與地表相應(yīng)單元的大小之比。點(diǎn)：單個(gè)柵格線：相鄰柵格組面：柵格片第42頁/共91頁柵格數(shù)據(jù)組織柵格數(shù)據(jù)組織針對(duì)一個(gè)柵格單元對(duì)應(yīng)多個(gè)屬性值的多層?xùn)鸥裎募?。?3頁/共91頁組織方法組織方法第44頁/共91頁柵格結(jié)構(gòu)的建立柵格結(jié)構(gòu)的建立1 1）建立途徑手工獲取掃描儀掃描 矢量數(shù)據(jù)轉(zhuǎn)換遙感影像數(shù)據(jù) 格網(wǎng)DEMDEM數(shù)據(jù)第45頁/共91頁2 2）柵格系統(tǒng)的確定 實(shí)質(zhì)是柵格坐標(biāo)系的確定-坐標(biāo)系原點(diǎn)和坐標(biāo)軸的確定。 起始坐標(biāo)應(yīng)與國家基本比例尺地形圖公里網(wǎng)的交點(diǎn)相一致，并分別采用公里網(wǎng)的縱橫坐標(biāo)軸作為柵格系統(tǒng)的坐標(biāo)軸。第46頁/共91頁3 3）柵格單元尺寸的確定l原則：應(yīng)能有效地逼近空間對(duì)象的分布特征，

15、又減少數(shù)據(jù)的冗余度。l方法：用保證最小多邊形的精度標(biāo)準(zhǔn)來確定尺寸經(jīng)驗(yàn)公式： h h為柵格單元邊長 AiAi為區(qū)域所有多邊形的面積。第47頁/共91頁4 4）柵格代碼（屬性值）的確定中心點(diǎn)法面積占優(yōu)法重要性法長度占優(yōu)法第48頁/共91頁柵格數(shù)據(jù)編碼柵格數(shù)據(jù)編碼1 1）直接?xùn)鸥窬幋a 將柵格數(shù)據(jù)看作一個(gè)數(shù)據(jù)矩陣，逐行記錄代碼數(shù)據(jù)。1 1）每行都從左到右記錄：AAAAABBBAABBAABBAAAAABBBAABBAABB2 2）奇數(shù)行從左到右，偶數(shù)行從右到左；特點(diǎn)：直觀、基本，沒進(jìn)行任何壓縮數(shù)據(jù)處理。第49頁/共91頁 將數(shù)據(jù)表示成更緊湊的格式以減少存儲(chǔ)空間的一項(xiàng)技術(shù)。分為：無損壓縮：在編碼過程中信

16、息沒有丟失，經(jīng)過解碼可恢復(fù)原有的信息-信息保持編碼。有損壓縮：為最大限度壓縮數(shù)據(jù)，在編碼中損失一些認(rèn)為不太重要的信息，解碼后，這部分信息無法恢復(fù)。-信息不保持編碼。 數(shù)據(jù)壓縮第50頁/共91頁2 2）行程編碼（變長編碼） 將原圖表示的數(shù)據(jù)矩陣變?yōu)閿?shù)據(jù)對(duì)：1 1）屬性碼，長度，行號(hào)（可不要）2 2）屬性碼，點(diǎn)位特點(diǎn)：數(shù)據(jù)量增加不明顯，壓縮率高，易于操作，適用于區(qū)域面積較大專題圖。第51頁/共91頁3 3）塊碼（游程編碼向二維的擴(kuò)展） 采用方形區(qū)域作為記錄單元，每個(gè)記錄單元包括相鄰的若干柵格。依次掃描，編過的不重復(fù)。 數(shù)據(jù)對(duì)組成：（初始行、列，半徑，屬性值）特點(diǎn)：具有可變分辨率，分辨率低，壓縮比高

17、，隨圖形復(fù)雜程度的提高而降低。（1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7)第52頁/共91頁4 4）鏈?zhǔn)骄幋a、FreemanFreeman鏈碼、邊界鏈碼 將柵格數(shù)據(jù)（線狀地物面域邊界）表示為矢量鏈的記錄。優(yōu)點(diǎn)：便于面積、長度、轉(zhuǎn)折方向和邊界、線段凹凸度的計(jì)算。缺點(diǎn)：不易做邊界合并，插入操作、編輯較困難。區(qū)域空間分析困難，相鄰區(qū)域邊界被重復(fù)存儲(chǔ)。 第53頁/共91頁5 5）四叉樹編碼 四叉樹概述：一種可變分率的非均勻網(wǎng)格系統(tǒng)。是最有效的柵格數(shù)據(jù)壓縮編碼方法之一。l基本思想： 將2 2n n2 2n n象元組成的圖像( (不足的用背景補(bǔ)上) ) 按四象限進(jìn)行遞歸分

18、割，判斷屬性是否單一。最后得到一顆四分叉的倒向樹。第54頁/共91頁l樹形表示： 用一倒立樹表示這種分割和分割結(jié)果。根：整個(gè)區(qū)域高：深度、分幾級(jí)，幾次分割葉：不能再分割的塊樹叉：還需分割的塊 每個(gè)樹叉均有4 4個(gè)分叉，叫四叉樹。第55頁/共91頁l編碼方法：常規(guī)四叉樹：記錄葉結(jié)點(diǎn)，中間結(jié)點(diǎn)，結(jié)點(diǎn)之間用指針聯(lián)系。每個(gè)結(jié)點(diǎn)需要6 6個(gè)變量：父結(jié)點(diǎn)指針、四個(gè)子結(jié)點(diǎn)的指針和本結(jié)點(diǎn)的屬性值。線性四叉樹：記錄葉結(jié)點(diǎn)的位置，深度，屬性。地址碼（定位碼、MortonMorton碼）指針不僅增加了數(shù)據(jù)的存儲(chǔ)量，還增加了操作的復(fù)雜性，并不廣泛用于存儲(chǔ)數(shù)據(jù)。存貯量小，只對(duì)葉結(jié)點(diǎn)編碼，直接尋址，定位碼容易存儲(chǔ)和執(zhí)行實(shí)

19、現(xiàn)集合相加等組合操作。 第56頁/共91頁四進(jìn)制MortonMorton碼方法1 1：四叉樹從上而下由葉結(jié)點(diǎn)找MortonMorton碼。A A、分割一次，增加一位數(shù)字，大分割在前，小分割在后。所以，碼的位數(shù)表示分割的次數(shù)。B B、每一個(gè)位均是不大于3 3的四進(jìn)制數(shù)，表達(dá)位置。由MortonMorton找出四叉樹葉結(jié)點(diǎn)的具體位置。第57頁/共91頁方法2 2：四叉樹自下而上合并的方法。1 1）計(jì)算每個(gè)柵格對(duì)應(yīng)的MQMQMQ=2MQ=2* *Ib+Jb Ib+Jb 其始行列號(hào)從0 0計(jì)。2) 2) 按碼的升序排成線性表，放在連續(xù)的內(nèi)存塊中。3 3）依次檢查每四個(gè)相鄰的MQMQ對(duì)應(yīng)的屬性值，相同合

20、并（不同碼位去掉），不同則存盤, ,直到?jīng)]有能夠合并的子塊為止。第58頁/共91頁十進(jìn)制MortonMorton碼按位操作的方法。如行為2 2、列為3 3的柵格的MDMD步驟：(1)(1)行、列號(hào)為二進(jìn)制 (2)I(2)I行J J列交叉 (3)(3)再化為十進(jìn)制. . 實(shí)質(zhì)上是按左上、右上、左下、右下的順序，從零開始對(duì)每個(gè)柵格進(jìn)行自然編碼。第59頁/共91頁把一幅2n2n2n2n的圖像壓縮成線性四叉樹的過程：1 1、按MortonMorton碼把圖象讀入一維數(shù)組。2 2、相鄰的四個(gè)象元比較，一致的合并，只記錄第一個(gè)象元的MortonMorton碼。循環(huán)比較所形成的大塊，相同的再合并，直到不能合

21、并為止。3 3、進(jìn)一步用游程長度編碼壓縮。壓縮時(shí)只記錄第一個(gè)象元的MortonMorton碼。第60頁/共91頁1 1、按MortonMorton碼讀入一維數(shù)組。MortonMorton碼：0 1 2 3 4 5 6 7 8 9 10 11 12 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1514 15象元值：A A A B A A B B A A A A B B B BA A A B A A B B A A A A B B B B2 2、四相鄰象元合并，只記錄第一個(gè)象元的MortonMorton碼。0 1 2 3 4 5 6 7 8 120 1 2 3 4

22、5 6 7 8 12A A A B A A B B A BA A A B A A B B A B3 3、用游程長度編碼壓縮。0 3 4 6 8 120 3 4 6 8 12A B A B A B A B A B A B 第61頁/共91頁四叉樹優(yōu)缺點(diǎn)優(yōu)點(diǎn)：1 1）占用空間比網(wǎng)絡(luò)法要少得多，是一種非冗余表示法。2 2）四叉樹具有可變率或多重分辯率的特點(diǎn)使得它有很好的應(yīng)用前景，適用于處理凝聚性或呈不均勻的塊狀分布的空間數(shù)據(jù)，但不適用于連續(xù)表面或線狀地物。第62頁/共91頁缺點(diǎn)：1 1）矢/ /柵正反變換還不理想。2 2）建立四叉樹耗費(fèi)機(jī)時(shí)很多。3 3）修改費(fèi)事。4 4）未能直接表示物體間的拓?fù)潢P(guān)系

23、。5 5）轉(zhuǎn)換的不穩(wěn)定性（滑動(dòng)變異）。6 6）無內(nèi)在相關(guān)性。第63頁/共91頁第64頁/共91頁矢量、柵格數(shù)據(jù)結(jié)構(gòu)的選擇 應(yīng)根據(jù)應(yīng)用目的和應(yīng)用特點(diǎn)、可能獲得的數(shù)據(jù)精度以及軟件和硬件配置情況，選擇合適的數(shù)據(jù)結(jié)構(gòu)。柵格結(jié)構(gòu): :大范圍小比例尺的自然資源、環(huán)境、農(nóng)林業(yè)等區(qū)域問題的研究。矢量結(jié)構(gòu)：城市分區(qū)或詳細(xì)規(guī)劃、土地管理、公用事業(yè)管理等方面的應(yīng)用。第65頁/共91頁2.4 2.4 矢柵一體化數(shù)據(jù)結(jié)構(gòu)矢柵一體化數(shù)據(jù)結(jié)構(gòu)以矢量的方式來組織柵格數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)：線狀地物：記錄原始取樣點(diǎn)和路徑所通過的柵格。面狀地物：記錄多邊形周邊以外及中間的面域柵格。保留了矢量的全部性質(zhì)，也建立了柵格與地物的關(guān)系，即路徑上

24、的任一點(diǎn)都直接與目標(biāo)建立了聯(lián)系。將矢量面對(duì)目標(biāo)的方法和柵格元子充填的方法結(jié)合。第66頁/共91頁a.a.點(diǎn)狀地物是地球表面上的點(diǎn)僅有空間位置，沒有形狀和面積，在計(jì)算機(jī)內(nèi)部僅有一個(gè)位置數(shù)據(jù)。三個(gè)約定和細(xì)分格網(wǎng)法b.b.線狀地物是地球表面的空間曲線，有形狀但沒有面積，在平面上的投影是一連續(xù)不間斷的直線或曲線，在計(jì)算機(jī)內(nèi)部需要用一組元子填滿整個(gè)路徑。c.c.面狀地物是地球表面的空間曲面，具有形狀和面積，在平面上的投影是由邊界包圍的緊致空間和一組填滿路徑的元子表達(dá)的邊界組成。 第67頁/共91頁為提高柵格表示精度，采用細(xì)分格網(wǎng)法：將一對(duì)X,YX,Y坐標(biāo)用兩個(gè)MortonMorton碼代替：前一M M1

25、 1表示該點(diǎn)（采樣點(diǎn)或附加的交叉點(diǎn)）所在基本格網(wǎng)的地址碼，后者M(jìn) M2 2 表示該點(diǎn)對(duì)應(yīng)的細(xì)分格網(wǎng)的MortonMorton碼，既顧全整體定位，又保證精度。 第68頁/共91頁一體化數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 線性四叉樹(Morton)(Morton)是基本數(shù)據(jù)格式，三個(gè)約定設(shè)計(jì)點(diǎn)、線、面數(shù)據(jù)結(jié)構(gòu)的基本依據(jù)，細(xì)分格網(wǎng)法保證足夠精度。1 1）點(diǎn)狀地物和結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：點(diǎn)僅有位置、沒有形狀和面積，將點(diǎn)的坐標(biāo)轉(zhuǎn)化為地址碼M1M1和M2 , M2 , 便于點(diǎn)的插入和刪除和處理柵格內(nèi)含多個(gè)點(diǎn)狀目標(biāo)的情況。第69頁/共91頁2 2）線狀地物和結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)：有形狀但沒有面積，沒有面積意味著只要用一串?dāng)?shù)據(jù)表達(dá)每個(gè)線狀地物

26、的路徑即可，將該線狀地物經(jīng)過的所有柵格的地址全部記錄下來。仿照矢量數(shù)據(jù)組織的鏈狀雙重獨(dú)立式編碼，以弧段為記錄單位。第70頁/共91頁3 3）面狀地物的數(shù)據(jù)結(jié)構(gòu)：弧段文件邊界弧段-形狀帶指針的二維行程碼 面域 葉結(jié)點(diǎn)的屬性值改為指向該地物的下一個(gè)子塊的循環(huán)指針。循環(huán)指針指向該地物下一個(gè)子塊的地址碼，并在最后指向該地物本身。第71頁/共91頁 只要進(jìn)入第一塊就可以順著指針直接提取該地物的所有子塊，從而避免像柵格數(shù)據(jù)那樣為查詢某一個(gè)目標(biāo)需遍歷整個(gè)矩陣，大大提高了查詢速度。第72頁/共91頁4 4）復(fù)雜地物的數(shù)據(jù)結(jié)構(gòu)： 由幾個(gè)或幾種點(diǎn)、線、面狀簡單地物組成的地物稱為復(fù)雜地物。例如將一條公路上的中心線、

27、交通燈、立交橋等組合為一個(gè)復(fù)雜地物，用一個(gè)標(biāo)識(shí)號(hào)表示。第73頁/共91頁矢量和柵格的轉(zhuǎn)換矢量和柵格的轉(zhuǎn)換矢量矢量柵格柵格點(diǎn)和線地物柵格 根據(jù)點(diǎn)或線的某個(gè)屬性對(duì)相應(yīng)柵格點(diǎn)進(jìn)行賦值。第74頁/共91頁多邊形 需要進(jìn)行填充，填充則要基于點(diǎn)和多邊形的空間關(guān)系判斷 掃描線算法（相切的情形需要區(qū)分）第75頁/共91頁基于拓?fù)涠噙呅蔚倪吔绱鷶?shù)算法第76頁/共91頁柵格到矢量的轉(zhuǎn)換abcd(a)aabc(b)abcc(c)abac(d)abcb(e)abca(f)abbc(e)abba(g)將每個(gè)柵格點(diǎn)視為一個(gè)方形區(qū)域因此，總是轉(zhuǎn)換得到多邊形地物思路：區(qū)分不同的節(jié)點(diǎn)和邊界類型（及2 2* *2 2柵格區(qū)域內(nèi)柵

28、格數(shù)值的組合）aabb(a)abab(b)aaab(c)aaba(d)abbb(e)abaa(f)節(jié)點(diǎn)邊界點(diǎn)第77頁/共91頁2.5 2.5 三維數(shù)據(jù)結(jié)構(gòu)三維數(shù)據(jù)結(jié)構(gòu) 目前計(jì)算機(jī)地圖制圖主要還停留在處理地球表面的數(shù)據(jù)，若數(shù)據(jù)是地表以下或以上，則先將它投影到地表，再進(jìn)行處理，其實(shí)質(zhì)是以二維的形式來模擬、處理任何數(shù)據(jù)，在有些領(lǐng)域可行，但涉及到三維問題的處理時(shí)，往往力不從心。 二維V=f(x,y)V=f(x,y)在不同的層V V的含義不同，當(dāng)V V表示的是高程時(shí)，就是DEMDEM。第78頁/共91頁 真三維模型V=f(x,y,z)V=f(x,y,z)，z z是一自變量，不受x,yx,y的影響。在數(shù)據(jù)

29、采集，系統(tǒng)維護(hù)和界面設(shè)計(jì)等方面比二維復(fù)雜得多，同樣，三維結(jié)構(gòu)存在柵格和矢量兩種形式。柵格：將地理實(shí)體的三維空間分成細(xì)小單元-體元。普遍用八叉樹。矢量：x,y,zx,y,z，抽象為點(diǎn)、線、面、體，面構(gòu)成體。方法多種，常用三維邊界表示法。 第79頁/共91頁八叉樹：1 1）思想：四叉樹在三維空間的推廣。 將要表示的形體V V放在一個(gè)充分大的正方體C C內(nèi)，C C的邊長為2 2n n，不斷用兩個(gè)與XOYXOY、XOZXOZ的平面均分C C為8 8個(gè)子體，并判斷屬性單一性。第80頁/共91頁2 2）存儲(chǔ)結(jié)構(gòu)：l規(guī)則八叉樹 與常規(guī)四叉樹類似，用1010項(xiàng)字段來記錄每個(gè)結(jié)點(diǎn)（8 8個(gè)子結(jié)點(diǎn)指針， 1 1個(gè)父結(jié)點(diǎn)指針，1 1個(gè)結(jié)點(diǎn)屬性）。l線性八叉樹 用某一預(yù)先確定的次序?qū)瞬鏄滢D(zhuǎn)換成線性表，表中的每個(gè)元素與一個(gè)結(jié)點(diǎn)相對(duì)應(yīng)。