空間數(shù)據(jù)結(jié)構(gòu)

第四章空間數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)即數(shù)據(jù)的組織形式，是適用于計算機存儲、管理、處理的數(shù)據(jù)邏輯表達。換句話說，是指數(shù)據(jù)以什么形式在計算機中存儲和處理。空間數(shù)據(jù)結(jié)構(gòu)是空間邏輯數(shù)據(jù)模型在計算機中的組織關(guān)系和編排方式。包括基于矢量模型的矢量數(shù)據(jù)結(jié)構(gòu)、基于柵格模型的柵格數(shù)據(jù)結(jié)構(gòu)和基于不規(guī)那么鑲嵌模型的TIN的曲面數(shù)據(jù)結(jié)構(gòu)等。4.1矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)是對矢量數(shù)據(jù)模型進行數(shù)據(jù)的組織，通過記錄坐標的方式盡可能精確地表示點、線、多邊形等地理實體，坐標空間設(shè)為連續(xù)，允許任意位置、長度和面積的精確定義。其精度僅受數(shù)字化設(shè)備的精度和數(shù)值記錄字長的限制。矢量數(shù)據(jù)矢量數(shù)據(jù)的類型Buildings.PolygonStreams,LineWells,PointRoads,LineZoning, PolygonMAPSHEETS 矢量結(jié)構(gòu)允許最復(fù)雜的數(shù)據(jù)以最小的數(shù)據(jù)冗余進行存儲，相對柵格結(jié)構(gòu)來說，數(shù)據(jù)精度高，數(shù)據(jù)存儲的冗余小，是高效的空間數(shù)據(jù)結(jié)構(gòu)。分為實體數(shù)據(jù)結(jié)構(gòu)和拓撲數(shù)據(jù)結(jié)構(gòu)。實體數(shù)據(jù)結(jié)構(gòu)實體數(shù)據(jù)結(jié)構(gòu)中，空間數(shù)據(jù)按照根本的空間對象〔點、線或多邊形〕為單元進行單獨的組織，其中不包含拓撲關(guān)系信息，最典型的是所謂的面條〔spaghetti〕結(jié)構(gòu)，又稱為坐標序列法。常采用這種數(shù)據(jù)結(jié)構(gòu)的有ArcGIS中的Shape文件和MapInfo的Tab文件等?！?9頁〕點的表示線的表示面的表示矢量數(shù)據(jù)模型中單一空間實體的表達坐標序列法〔Spaghetti方式〕例如圖形數(shù)據(jù)10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1。20：x1,y1；x12,y12；x13,y13；x14,y14；x15,y15；x16,y16；x17,y17；x18,y18；x19,y19；x20,y20；x21,y21；x22,y22；x23,y23；x8,y8；x9,y9；x10,y10；x11,y11；x1,y1。編碼數(shù)據(jù)坐標序列法的優(yōu)缺點優(yōu)點：文件結(jié)構(gòu)簡單，易于實現(xiàn)以多邊形為單位的運算和顯示缺點：對于相連的線，交叉點要重復(fù)輸入和存儲；對于多邊形其公共邊也要重復(fù)輸入和存儲，從而產(chǎn)生數(shù)據(jù)冗余和分析處理不便的問題；對于復(fù)雜多邊形，不能解決多邊形中“島〞、“洞〞之類的鑲套問題，“島〞或“洞〞只能作為單個的多邊形來構(gòu)造，沒有和周圍的多邊形建立關(guān)系；很難檢查多邊形的邊界正確與否，即多邊形的完整性；每個多邊形自成體系，缺少有關(guān)鄰域的信息，使拓撲關(guān)系，即相鄰關(guān)系很難跟蹤。適用范圍：制圖及一般查詢，不適合復(fù)雜的空間分析4.1.2拓撲結(jié)構(gòu)編碼法具有拓撲關(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)就是拓撲數(shù)據(jù)結(jié)構(gòu)。拓撲數(shù)據(jù)模型是一種基于矢量的比較有效的數(shù)據(jù)模型，ArcGIS的Coverage就是一種拓撲數(shù)據(jù)結(jié)構(gòu)。拓撲數(shù)據(jù)結(jié)構(gòu)包括樹狀索引編碼法、雙重獨立編碼結(jié)構(gòu)、鏈狀雙重獨立編碼結(jié)構(gòu)等。其實質(zhì)是通過地理實體之間的空間關(guān)系表示來線和多邊形。根本概念弧段：構(gòu)成多邊形的線稱為弧段，每個弧段可以有許多中間點。節(jié)點：兩條以上弧段相交的點稱為節(jié)點島：由一條弧段組成的多邊形稱為島或洞。簡單多邊形：多邊形圖中不含島的多邊形稱為簡單多邊形。復(fù)合多邊形：含島的多邊形稱為復(fù)合多邊形，包括為邊界和內(nèi)邊界，島可以看做復(fù)合多邊形的內(nèi)邊界。1樹狀索引編碼法〔層次索引法、索引式結(jié)構(gòu)〕采用樹狀索引以減少數(shù)據(jù)冗余并間接增加鄰域信息，方法是對所有邊界點進行數(shù)字化，將坐標對以順序方式存儲，由點索引與邊界線號相聯(lián)系，以線索引與各多邊形相聯(lián)系，形成樹狀索引結(jié)構(gòu)樹狀索引編碼法例如圖形數(shù)據(jù)樹狀索引編碼法例如線與多邊形之間的樹狀索引樹狀索引編碼法例如點與邊界線之間的樹狀索引樹狀索引編碼法例如形成的文件記錄索引式

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

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

樹狀索引編碼消除了相鄰多邊形邊界的數(shù)據(jù)冗余和不一致的問題，在簡化過于復(fù)雜的邊界線或合并相鄰多邊形時可不必改造索引表，鄰域信息和島狀信息可以通過對多邊形文件的線索引處理得到，但是比較繁瑣，因而給相鄰函數(shù)運算，消除無用邊，處理島狀信息以及檢查拓撲關(guān)系帶來一定的困難，而且兩個編碼表都需要以人工方式建立，工作量大且容易出錯。2.雙重獨立編碼結(jié)構(gòu)美國人口調(diào)查局于1980年建立的雙重獨立地圖編碼系統(tǒng)。簡稱DIME(DualIndependentMapEncoding)，這種結(jié)構(gòu)最適合于城市地理信息系統(tǒng)。線文件是雙重獨立編碼結(jié)構(gòu)的根本對象。線文件由線標識碼、起始節(jié)點、終止節(jié)點、左多邊形和右多邊形組成；節(jié)點文件由節(jié)點的標識碼、節(jié)點坐標及與該節(jié)點連接的線的標識碼等；多邊形文件由多邊形標識碼、組成該多邊形的線標識碼組成。C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7線號起結(jié)點終結(jié)點左多邊形右多邊形C1N1N2P2P1C2N3N2P1P4C3N1N3P1?C4N1N4?P2C5N2N5P2P4C6N4N5P3P2多邊形：多邊形由一系列的相互連結(jié)的線組成，并通過其內(nèi)部的唯一標識點來標識。標識點的標識碼和該多邊形屬性表中的標識碼相一致，由此建立的多邊形空間信息和屬性信息的關(guān)系。多邊形線IDP1C1,C2,C3P2C1,C5,C4P3C6,C7,C8P4C5,C7,C10,C2….C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7面拓撲節(jié)點坐標線N1X1,y1C1,C4,C3N2X2,y2C1,C5,C2N3X3,y3C2,C3,C10N4X4,y4C4,C6,C8….C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7點拓撲補充：基于雙重獨立編碼的拓撲檢查從線文件中，找出與當前編輯的多邊形相關(guān)的所有記錄。如對上例中的P1進行檢查，先在線文件中找出與p1有關(guān)的所有記錄：線號起結(jié)點終結(jié)點左多邊形右多邊形C1N1N2P2P1C2N3N2P1P4C3N1N3P1?C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7補充：基于雙重獨立編碼的拓撲檢查2.如果P1在左〔右〕多邊形的位置，將之與處在右〔左〕多邊形處位置的多邊形號相交換，同時也將該記錄的節(jié)點號位置相應(yīng)的交換；反之，順序不變。線號起結(jié)點終結(jié)點左多邊形右多邊形C1N1N2P2P1C2N2N3P4P1C3N3N1?P1C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7補充：基于雙重獨立編碼的拓撲檢查從經(jīng)過代碼位置轉(zhuǎn)換的記錄中，任取一個起始節(jié)點作為起點，順序連接各節(jié)點，使得節(jié)點能自行封閉，即N1N2N3N1。如果不能自動封閉，那么說明出現(xiàn)記錄缺損或多余，線文件有錯誤。線號起結(jié)點終結(jié)點左多邊形右多邊形C1N1N2P2P1C2N2N3P4P1C3N3N1?P1C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N73.鏈式雙重獨立編碼結(jié)構(gòu)鏈式雙重獨立編碼是DIME數(shù)據(jù)結(jié)構(gòu)的一種改進。在DIME中，一條邊只能用直線兩端點的序號及相鄰多邊形表示，而在鏈狀數(shù)據(jù)結(jié)構(gòu)中，將假設(shè)干條直線段合為一個弧段〔或鏈段〕，每個弧段可以有許多中間點。ARCGIS中的Coverage數(shù)據(jù)模型就是采用鏈式雙重獨立編碼結(jié)構(gòu)。拓撲結(jié)構(gòu)的特點是:除結(jié)點外，每個空間對象都是由更根本的對象組成的。只有點的坐標是被實際存儲的，其他復(fù)雜空間對象的坐標信息實際上是邏輯構(gòu)成的。任一復(fù)雜對象能分解為一組結(jié)點及其拓撲關(guān)系的定義。這樣，一個圖層中存儲的全部坐標信息就是結(jié)點的坐標，建立其他對象只是建立對這些坐標的引用。雖然建立拓撲結(jié)構(gòu)需要額外的存儲數(shù)據(jù)，但對坐標數(shù)據(jù)的存儲卻沒有數(shù)據(jù)冗余的問題。拓撲結(jié)構(gòu)編碼是某些空間分析的根底。小結(jié)矢量數(shù)據(jù)結(jié)構(gòu)特點：定位明顯，屬性隱含。其定位是根據(jù)坐標直接存儲的，無需任何推算；屬性那么一般存于文件頭或數(shù)據(jù)結(jié)構(gòu)中某些特定的位置上。這種特點使得矢量數(shù)據(jù)結(jié)構(gòu)在圖形運算的算法總體上比柵格數(shù)據(jù)結(jié)構(gòu)復(fù)雜的多，在疊加運算、鄰域搜索等操作時比較困難，有些甚至難以實現(xiàn)，但其也有便利和獨到之處，在計算長度、面積、形狀和圖形編輯、幾何變換操作中，矢量結(jié)構(gòu)有很高的效率和精度。4.2柵格數(shù)據(jù)結(jié)構(gòu)柵格結(jié)構(gòu)是最簡單最直接的空間數(shù)據(jù)結(jié)構(gòu)，是指將地球外表劃分為大小均勻緊密相鄰的網(wǎng)格陣列，每個網(wǎng)格作為一個象元或象素由行、列定義，并包含一個代碼表示該象素的屬性類型或量值，或僅僅包括指向其屬性記錄的指針。柵格數(shù)據(jù)編碼方法分為兩大類：直接?xùn)鸥窬幋a〔完全柵格數(shù)據(jù)結(jié)構(gòu)〕壓縮編碼方法〔壓縮柵格數(shù)據(jù)結(jié)構(gòu)〕鏈碼游程長度編碼塊碼四叉樹二維行程編碼4.2.1直接?xùn)鸥窬幋a直接編碼就是將柵格數(shù)據(jù)看作一個數(shù)據(jù)矩陣，逐行〔或逐列〕逐個記錄代碼，可以每行都從左到右逐個象元進行記錄，也可以奇數(shù)行地從左到右而偶數(shù)行地從右向左記錄，為了特定目的還可采用其他特殊的順序一些常用的柵格排列順序4.2.2壓縮編碼方式壓縮編碼的目的就是用盡可能少的數(shù)據(jù)量記錄盡可能多的信息，其類型分為信息無損編碼:編碼過程中沒有任何信息損失，通過解碼操作可以完全恢復(fù)原來的信息 信息有損編碼:為了提高編碼效率，最大限度地壓縮數(shù)據(jù)，在壓縮過程中損失一局部相對不太重要的信息，解碼時這局部難以恢復(fù)

在地理信息系統(tǒng)中的壓縮編碼多采用信息無損編碼，而對原始遙感影像進行壓縮時也可以采取有損壓縮編碼方法。鏈碼〔ChainCodes〕鏈式編碼又稱為弗里曼鏈碼(Freeman，1961〕或邊界鏈碼。該編碼方法將數(shù)據(jù)表示為由某一原點開始并按某些根本方向確定的單位矢量鏈。如：根本方向可定義為：東＝0，東南＝1，南＝2，西南＝3，西＝4，西北＝5，北＝6，東北＝7等八個根本方向。例如，確定原點為像元〔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。其中前兩個數(shù)字10和1表示起點為第十行第一列，從第三個數(shù)字開始每個數(shù)字表示單位矢量的方向，八個方向以0—7的整數(shù)代表。5555443355554432555553225555552276614433777144332221111122555551練習鏈碼〔ChainCodes〕優(yōu)缺點優(yōu)點： 鏈式編碼對多邊形的表示具有很強的數(shù)據(jù)壓縮能力，且具有一定的運算功能，如面積和周長計算等，探測邊界急彎和凹進局部等都比較容易，比較適于存儲圖形數(shù)據(jù)。缺點： 對疊置運算如組合、相交等那么很難實施，對局部修改將改變整體結(jié)構(gòu)，效率較低，而且由于鏈碼以每個區(qū)域為單位存儲邊界，相鄰區(qū)域的公共邊界被重復(fù)存儲會產(chǎn)生冗余。游程長度編碼〔Run-LengthCodes〕 它的根本思路是：對于一幅柵格圖像，常常有行〔或列〕方向上相鄰的假設(shè)干點具有相同的屬性代碼，因而可采取某種方法壓縮那些重復(fù)的記錄內(nèi)容。所謂的游程〔行程〕是指柵格矩陣內(nèi)相鄰?fù)禆鸥竦臄?shù)量。游程長度編碼〔Run-LengthCodes〕其實現(xiàn)方法有兩種一種編碼方案是，只在各行〔或列〕數(shù)據(jù)的代碼發(fā)生變化時依次記錄該代碼以及相同的代碼重復(fù)的個數(shù)，從而實現(xiàn)數(shù)據(jù)的壓縮。另一種游程長度編碼方案就是逐個記錄各行〔或列〕代碼發(fā)生變化的位置和相應(yīng)代碼

游程長度編碼例如按第一種編碼方法〔左上角坐標，沿行方向〕，此數(shù)據(jù)游程長度編碼：〔0，1〕，〔4，2〕，〔7，5〕；〔4，5〕，〔7，3〕；〔4，4〕，〔8，2〕，〔7，2〕；〔0，2〕，〔4，1〕，〔8，3〕，〔7，2〕；〔0，2〕，〔8，4〕，〔7，1〕，〔8，1〕；(0，3)，(8，5)；(0，4)，(8，4)；(0，5)，(8，3)。用44個整數(shù)表達了原始數(shù)據(jù)中的64個柵格。游程長度編碼例如〔1，0〕，〔2，4〕，〔4，0〕；〔1，4〕，〔4，0〕；〔1，4〕，〔5，8〕，〔6，0〕；〔1，7〕，〔2，4〕，〔4，8〕，〔7，0〕；〔1，7〕，〔2，4〕，〔3，8〕，〔8，0〕；〔1，7〕，〔3，8〕；〔1，7〕，〔6，8〕；〔1，7〕，〔5，8〕。按第二種編碼方法，記錄各行〔或列〕代碼發(fā)生變化的位置和相應(yīng)代碼此數(shù)據(jù)游程長度編碼〔左上角坐標，沿列方向〕：游程編碼能否壓縮數(shù)據(jù)量，主要取決于柵格數(shù)據(jù)的性質(zhì)，通常可以通過事先測試，估計數(shù)據(jù)冗余度Re：Re=1-Q/mn式中：Q表示相鄰屬性值變化次數(shù)的累加和m表示行數(shù)n表示列數(shù)

當Re的值大于1/5時，表示柵格數(shù)據(jù)的壓縮可取的明顯的效果其壓縮效果可以由壓縮比來表征：S=m×n/K式中：K為游程總數(shù)m表示行數(shù)n表示列數(shù)

壓縮比越大，表示壓縮效果越好游程長度編碼優(yōu)缺點優(yōu)點壓縮效率較高，且易于進行檢索，疊加合并等操作，運算簡單，適用于機器存儲容量小，數(shù)據(jù)需大量壓縮，而又要防止復(fù)雜的編碼解碼運算增加處理和操作時間的情況缺點對于圖斑破碎，屬性和邊界多變的數(shù)據(jù)壓縮效率較低，甚至壓縮后的數(shù)據(jù)量比原始數(shù)據(jù)還大。

塊碼〔ChainCodes〕 塊碼是游程長度編碼擴展到二維的情況，采用方形區(qū)域作為記錄單元，每個記錄單元包括相鄰的假設(shè)干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置〔行、列號〕和半徑，再加上記錄單位的代碼組成。塊碼編碼例如其塊碼編碼為：(1,1,1,0),(1,2,2,4),(1,4,1,7),(1,5,1,7),(1,6,2,7),(1,8,1,7),(2,1,1,4),(2,4,1,4),(2,5,1,4),(2,8,1,7),(3,1,1,4),(3,2,1,4),(3,3,1,4),(3,4,1,4),(3,5,2,8),(3,7,2,7),(4,1,2,0),(4,3,1,4),(4,4,1,8),(5,3,1,8),(5,4,2,8),(5,6,1,8),(5,7,1,7),(5,8,1,8),(6,1,3,0),(6,6,3,8),(7,4,1,0),(7,5,1,8),(8,4,1,0),(8,5,1,0)。四叉樹編碼 四叉樹編碼將整個圖像區(qū)逐步分解為一系列僅包含單一類型的方形區(qū)域，最小的方形區(qū)域為一個柵格象元。

四叉樹編碼 其根本分割方法是將一幅柵格地圖或圖像等分為四局部。逐塊檢查其柵格屬性值(或灰度)。如果某個子區(qū)的所有柵格值都具有相同的值。那么這個子區(qū)就不再繼續(xù)分割，否那么還要把這個子區(qū)再分割成四個子區(qū)。這樣依次地分割，直到每個子塊都只含有相同的屬性值或灰度為止。 四叉樹編碼例如

四叉樹編碼要求

采用四叉樹編碼時，為了保證四叉樹分解能不斷地進行下去，要求圖像必須為2n×2n的柵格陣列，對于非標準尺寸的圖像需首先通過增加背景的方法將圖像擴充為2n×2n的圖像。

生成四叉樹主要有兩種方法，即自上而下〔top-down〕和自下而上〔bottton-up〕。由上而下的方法運算量大，耗時較長。因而實踐中可以采用從下而上的方法建立四叉樹編碼。對柵格數(shù)據(jù)按Morton碼的順序進行檢測：如果每相鄰四個柵格值相同那么進行合并，逐次往上遞歸合并，直到符合四叉樹的原那么為止。這種方法重復(fù)計算較少，運算速度較快。四叉樹的生成四叉樹結(jié)構(gòu)的編碼方式四叉樹結(jié)構(gòu)按其編碼的方法不同分為常規(guī)四叉樹和線性四叉樹：常規(guī)四叉樹：除了記錄葉結(jié)點之外，還要記錄中間結(jié)點。結(jié)點之間借助指針聯(lián)系，每個結(jié)點需要用六個量表達：四個葉結(jié)點指針，一個父結(jié)點指針和一個結(jié)點的屬性或灰度值。這些指針不僅增加了數(shù)據(jù)貯存量，而且增加了操作的復(fù)雜性。常規(guī)四叉樹主要在數(shù)據(jù)索引和圖幅索引等方面應(yīng)用。四叉樹結(jié)構(gòu)的編碼方式線性四叉樹：只存貯最后葉結(jié)點的信息。包括葉結(jié)點的位置〔莫頓碼值〕、深度和本結(jié)點的屬性或灰度值。所謂深度是指處于四叉樹的第幾層上。由深度可推知子區(qū)的大小。線性四叉樹葉結(jié)點的編號需要遵循一定的規(guī)那么，這種編號稱為地址碼，它隱含了葉結(jié)點的位置和深度信息。最常用的地址碼是二進制或十進制的Morton碼。美國馬里蘭大學(xué)地理信息系統(tǒng)中采用的編碼方式：該方法記錄了葉子結(jié)點的地址和值，值就是子區(qū)域的代碼，而地址碼包括兩個局部，由32位來表示〔二進制〕，最右邊4位記錄該葉子結(jié)點的深度，即處于四叉樹的第幾層上，有了深度即可推知子區(qū)域的大??；從右邊第5位開始2n個字節(jié)記錄葉子結(jié)點的路徑，用以描述葉子結(jié)點的位置，0，1，2，3分別表示SW,SE,NW,NE；其余各位用0補齊。上圖空白處葉子結(jié)點5，深度為3；路徑為3，0，0；用馬里蘭大學(xué)的編碼方式可以記為：0…….0〔22位〕；110000〔6位〕；0011〔四位〕柵格數(shù)據(jù)編碼練習二維行程編碼在生成線性四叉樹之后，仍然存在前后葉節(jié)點的值相同的情況，因而可以進一步壓縮數(shù)據(jù)，將前后值相同的葉節(jié)點合并，行程新的線性列表?！惨奝101圖4.14〕柵格數(shù)據(jù)壓縮存儲的編碼方法AAAAARAAARAAARAARAAAAAAAAAGGAAGGGGGGGAGGGAGGAAAAAARAAAARAAARRAAA143258761234567801234567起點行列號，單位矢量R:(1,5),3,2,2,3,3,2,3鏈式編碼游程長度編碼逐行編碼數(shù)據(jù)結(jié)構(gòu):行號,屬性,重復(fù)次數(shù)1,A,4,R,1,A,4塊狀編碼正方形區(qū)域為記錄單元數(shù)據(jù)結(jié)構(gòu):初始位置,半徑,屬性(1,1,3,A),(1,4,1,A),(1,5,1,R),(1,6,2,A),…NESWNWSEGGGGAGGAAGAAA四叉樹編碼常見柵格壓縮編碼方法總結(jié)：鏈碼的壓縮效率較高，已經(jīng)近矢量結(jié)構(gòu)，對邊界的運算比較方便，但不具有區(qū)域的性質(zhì)，區(qū)域空間分析運算困難。游程長度編碼既可以在很大程度上壓縮數(shù)據(jù)，又最大限度地保存了原始柵格結(jié)構(gòu)，編碼解碼十分容易。但對破碎數(shù)據(jù)處理效果不好。塊碼和四叉樹編碼具有區(qū)域性質(zhì)，又具有可變的分辨率，有較高的壓縮效率，但運算效率是其瓶頸。其中四叉樹編碼可以直接進行大量圖形圖像運算，效率較高，是很有前途的方法。其他壓縮編碼方式 還有很多編碼方法，如傅立葉變換、小波變換、余弦變換等，常常用于遙感原始數(shù)據(jù)的壓縮。由于它們多數(shù)是有損壓縮，一般不用于需要進行分析的柵格數(shù)據(jù)。在四叉樹根底上開展而來的八叉樹目前也是研究熱點之一。小結(jié)柵格數(shù)據(jù)結(jié)構(gòu)屬性明顯，定位隱含：屬性明顯數(shù)據(jù)中直接記錄了數(shù)據(jù)屬性或指向數(shù)據(jù)屬性的指針，因而我們可以直接得到地物的屬性代碼定位隱含所在位置那么根據(jù)行列號轉(zhuǎn)換為相應(yīng)的坐標，也就是說定位是根據(jù)數(shù)據(jù)在數(shù)據(jù)集中的位置得到的。柵格結(jié)構(gòu)是按一定的規(guī)那么排列的，所表示的實體的位置很容易隱含在格網(wǎng)文件的存儲結(jié)構(gòu)中柵格模型矢量模型優(yōu)點：（1）數(shù)據(jù)結(jié)構(gòu)簡單；（2）空間數(shù)據(jù)的疊置和組合十分容易方便；（3）各類空間分析都很易于進行；（4）數(shù)學(xué)模擬方便；（5）技術(shù)開發(fā)費用低。優(yōu)點：（1）表示地理數(shù)據(jù)的精度較高；（2）嚴密的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)量小；（3）用網(wǎng)絡(luò)連接法能完整地描述拓撲關(guān)系；（4）圖形輸出精確美觀；（5）圖形數(shù)據(jù)和屬性數(shù)據(jù)的恢復(fù)、更新、綜合都能實現(xiàn)。缺點：（1）圖形數(shù)據(jù)量大；（2）用大像元減少數(shù)據(jù)量時，可識別的現(xiàn)象結(jié)構(gòu)將損失大量信息；（3）地圖輸出不精美；（4）難以建立網(wǎng)絡(luò)連接關(guān)系；（5）投影變換花的時間多。缺點：（1）數(shù)據(jù)結(jié)構(gòu)復(fù)雜；（2）矢量多邊形地圖或多邊形網(wǎng)很難用疊置方法與柵格圖進行組合；（3）顯示和繪圖費用高，特別是高質(zhì)量繪圖、彩色繪圖和暈線圖等；（4）數(shù)學(xué)模擬比較困難；（5）技術(shù)復(fù)雜，多邊形內(nèi)的空間分析不容易實現(xiàn)?！?.3矢量數(shù)據(jù)結(jié)構(gòu)與柵格數(shù)據(jù)結(jié)構(gòu)比較矢量數(shù)據(jù)模型與柵格數(shù)據(jù)模型比較從應(yīng)用領(lǐng)域來看——柵格結(jié)構(gòu)和矢量結(jié)構(gòu)都有一定的局限性。一般來說，大范圍小比例尺的自然資源、環(huán)境、農(nóng)業(yè)、林業(yè)、地質(zhì)等區(qū)域問題的研究，城市總體規(guī)劃階段的戰(zhàn)略性布局研究等使用柵格模型比較適宜；城市分區(qū)或詳細規(guī)劃、土地管理、公共事業(yè)管理等方面應(yīng)用矢量模型比較適宜。從數(shù)據(jù)來源來看——對于一個與遙感相結(jié)合的地理信息系統(tǒng)來說，柵格結(jié)構(gòu)是必不可少的，因為遙感影像是以像元為單位的，可以直接將原始數(shù)據(jù)或經(jīng)處理的影像數(shù)據(jù)納入柵格結(jié)構(gòu)的地理信息系統(tǒng)；而對地圖數(shù)字化、拓撲檢測、矢量繪圖等，矢量數(shù)據(jù)結(jié)構(gòu)又是必不可少的?！噶繑?shù)據(jù)結(jié)構(gòu)與柵格數(shù)據(jù)結(jié)構(gòu)的選擇在GIS建立過程中，應(yīng)根據(jù)應(yīng)用的目的和應(yīng)用的特點、可能獲取的數(shù)據(jù)精度以及地理信息系統(tǒng)軟件和硬件的配置情況選擇適宜的數(shù)據(jù)結(jié)構(gòu)。矢量與柵格一體化〔了解〕為了發(fā)揮矢量和柵格數(shù)據(jù)結(jié)構(gòu)各自的特點，在兩種數(shù)據(jù)的根底上開展了矢量—柵格一體化數(shù)據(jù)結(jié)構(gòu)〔unifieddatastructure),這種空間數(shù)據(jù)結(jié)構(gòu)的思想是通過同時記錄多邊形邊界和邊界中間包含的柵格地址，實現(xiàn)既保持矢量數(shù)據(jù)的特征又具有柵格數(shù)據(jù)的性質(zhì)。根本思想：為了提高點、線和邊界的表示精度，一般將點所在格網(wǎng)或線、邊界通過的格網(wǎng)細分，根據(jù)精度要求可分為按照256×256或16×16將根本格網(wǎng)細分。根本格網(wǎng)和細分格網(wǎng)都采用線性四叉數(shù)編碼，采樣點和線目標與根本格網(wǎng)的交點用兩個十進制Morton碼表示。一、矢量與柵格一體化的概念為了建立矢量與柵格一體化數(shù)據(jù)結(jié)構(gòu)，要對點、線、面目標數(shù)據(jù)結(jié)構(gòu)的存儲要求作如下的統(tǒng)一約定:對點狀目標，因為沒有形狀和面積，在計算機內(nèi)部只需要表示該點的一個位置數(shù)據(jù)及與結(jié)點關(guān)聯(lián)的弧段信息。對線狀目標，它有形狀，但沒有面積，在計算機內(nèi)部需用一組元子來填滿整個路徑，并表示該弧段相關(guān)的拓撲信息。對面狀目標，它既有形狀，又有面積，在計算機內(nèi)部需表示由元子填滿路徑的組邊界和由邊界組成的緊湊空間。4.4不規(guī)那么鑲嵌數(shù)據(jù)結(jié)構(gòu)4.4.1Voronio數(shù)據(jù)結(jié)構(gòu)〔見教材106頁〕4.1.2TIN數(shù)據(jù)結(jié)構(gòu)TIN模型的數(shù)據(jù)存儲方式比柵格數(shù)據(jù)復(fù)雜，它不僅要存儲每個點的高程，還要存儲其平面坐標、節(jié)點連接的拓撲關(guān)系，三角形及鄰接三角形等關(guān)系。TIN模型在概念上類似于多邊形網(wǎng)絡(luò)的矢量拓撲結(jié)構(gòu)，對于每個三角形、邊和節(jié)點都對應(yīng)一個記錄，如下：三角形記錄包括三個指向它三個邊的記錄的指針；三角形頂點鄰接三角形ⅠabcⅡⅢⅡcdaⅠⅣⅢbecⅠⅤⅣⅣcedⅡⅢⅧⅤebgⅢⅥⅩⅥbhgⅤⅦ……………………邊有四個指針字段，包括兩個指向相鄰三角形的指針和它的兩個頂點的記錄的指針；邊頂點相鄰三角形1abⅠ2acⅠⅡ3bcⅠⅢ……………每個節(jié)點包括三個坐標值的字段，分別存儲X,Y,Z坐標。頂點xyzabcde※柵格數(shù)據(jù)模型和TIN數(shù)據(jù)模型的比較對地理空間的劃分：TIN模型為不規(guī)那么三角形；而柵格模型為規(guī)那么格網(wǎng)；空間對象的表示：柵格數(shù)據(jù)模型既可以描述連續(xù)變化的地理現(xiàn)象，又可以表示離散的地理現(xiàn)象〔點、線、面〕，而TIN模型只能表示聯(lián)系變化的地理現(xiàn)象；但TIN能精確地表示曲面類型地理現(xiàn)象的形狀以及特殊的地形要素，比方山脊、山峰等，而柵格模型不能精確表示；外表模型的精度：柵格使用統(tǒng)一的CELL大小來表示，在地形平坦的地方，存在大量的數(shù)據(jù)冗余，而TIN具有隨坡度變化而不同的點密度，在坡度變化大的地區(qū)點密度較高；柵格模型適合進行空間一致性分析、近鄰分析、離散度分析及外表最低本錢分析，TIN模型適合進行坡度、坡向、體積計算和視線分析等4.5三維空間數(shù)據(jù)模型4.5.1三維空間的目標分類4.5.2八叉樹數(shù)據(jù)結(jié)構(gòu)4.5.3四面體格網(wǎng)在三維空間中，可將空間地物按維數(shù)分成零維〔點〕，一維〔線〕、二維〔面〕和三維〔體〕四大類。零維空間：有點狀地物和用來表示與弧段的關(guān)聯(lián)關(guān)系的結(jié)點兩類目標。一維空間：有“拓樸弧段〞、“無拓樸弧段〞和線狀地物。其中“拓樸弧段〞可以是構(gòu)成多邊形的邊界線也可是構(gòu)成各類網(wǎng)線〔如水系網(wǎng)、交通網(wǎng)、城市地下管網(wǎng)〕的網(wǎng)線段。二維空間：主要有三類目標，一個是構(gòu)成面狀地物的拓樸面片；第二個是像素，用它可組成面狀要素；第三個是根據(jù)有限的離散數(shù)據(jù)建立數(shù)字外表模型。三維空間，有由假設(shè)干個面片或由數(shù)字立體模型表示體狀地物；以及根據(jù)有限的三維空間離散數(shù)據(jù)建成的數(shù)字立體模型。4.5.1八叉樹數(shù)據(jù)結(jié)構(gòu)八叉樹數(shù)據(jù)結(jié)構(gòu)是三維柵格數(shù)據(jù)的壓縮形式，是二維柵格數(shù)據(jù)中的四叉樹在三維空間的推廣，該數(shù)據(jù)結(jié)構(gòu)是將所要表示的三維空間V按X、Y、Z三個方向從中間進行分割，把V分割成八個立方體，然后根據(jù)每個立方體中所含的目標來決定是否對各立方體繼續(xù)進行八等分的劃分，一直劃分到每個立方體被一個目標所充滿，或沒有目標，或其大小已成為預(yù)先定義的不可再分的體素為止。三維空間體V及劃分編碼三維空間體V中的物體八叉樹數(shù)據(jù)結(jié)構(gòu)舉例八叉樹編碼八叉樹結(jié)構(gòu)就是將空間區(qū)域不斷地分解為八個同樣大小的子區(qū)域(即將一個六面的立方體再分解為八個相同大小的小立方體)，同—區(qū)域的屬性相同。八叉樹主要用來解決地理信息系統(tǒng)中的三維問題。

八叉樹的主要優(yōu)點在于可以非常方便地實現(xiàn)有廣泛用途的集合運算〔例如，可以求兩個物體的并、交、差等運算〕而這些恰是其它表示方法比較難以處理或者需要消耗許多計算資源的地方。此外，由于這種方法的有序性及分層性，因而對顯示精度和速度的平衡，隱線和隱面的消除等，帶來了很大的方便，特別有用。4.5.2四面體格網(wǎng)四面體格網(wǎng)〔TetrahedralNetwork—TEN〕是將目標空間用緊密排列但不重疊的不規(guī)那么四面體形成的格網(wǎng)來表示，其實質(zhì)是2DTIN結(jié)構(gòu)在3D空間上的擴展。在概念上首先將2DVoronoi格網(wǎng)擴展到3D，形成3DVoronoi多面體，然后將TIN結(jié)構(gòu)擴展到3D形成四面體格網(wǎng)〔見圖示〕。四面體格網(wǎng)表示三維空間物體的例子四面體格網(wǎng)表示三維空間物體的例子的數(shù)據(jù)結(jié)構(gòu)四面體格網(wǎng)由點、線、面和體四類根本元素組合而成。整個格網(wǎng)的幾何變換可以變?yōu)槊總€四面體變換后的組合，這一特性便于許多復(fù)雜的空間數(shù)據(jù)分析。同時，四面體格網(wǎng)既具有體結(jié)構(gòu)的優(yōu)點，如快速幾何變換、快速顯示，又可以看成是一種特殊的邊界表示，具有一些邊界表示的優(yōu)點，如關(guān)系的快速處理。矢量數(shù)據(jù)結(jié)構(gòu)和柵格數(shù)據(jù)結(jié)構(gòu)的相互轉(zhuǎn)換是地理信息系統(tǒng)的根本功能之一，目前已經(jīng)開展了許多高效的轉(zhuǎn)換算法。但是從柵格到矢量數(shù)據(jù)的轉(zhuǎn)換，特別是掃描圖像的自動識別，仍然是研究的重點。4.6矢量數(shù)據(jù)結(jié)構(gòu)與柵格數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換〔教材P164〕對于點實體，每個實體都僅由一個坐標對表示，其結(jié)構(gòu)的轉(zhuǎn)換不存在太大的技術(shù)問題。在這重點講解一下線實體和多邊形實體向柵格格式轉(zhuǎn)換的過程。如下：4.6.1矢量格式向柵格格式的轉(zhuǎn)換線實體向柵格格式的轉(zhuǎn)換由于GIS中線實體是由順次連接一組坐標點形成的折線段表達的，所以，線的柵格化可以分解為對做成線實體的折線段的柵格化。對于線段的柵格化，先使用點柵格化的方法，柵格化線段的兩個端點，然后再柵格化線段的中間局部。而對于線段中間的局部的柵格化，需要分兩種情況來處理:

設(shè)線段兩端點的坐標分別為(x1,y1)和(x2,y2),柵格化后所隊形的行列號分別為〔I1,J1)(I2,J2).那么行差為△I=︱I1-I2︱，列差為△J=︱J1-J2︱。分兩種情況處理：一是列差大于行差△J>△I的情況，二是行差大于列差△I>△J的情況，運用掃描線算法實現(xiàn)。當△J>△I時，平行于y軸做每一列柵格的中心線，稱為掃描線。求每一條掃描線與線段的交點，按點柵格化的方法將交點轉(zhuǎn)換為柵格坐標。當△I>△J時，同理。△J>△I△I>△J多邊形矢量格式向柵格格式的轉(zhuǎn)換

內(nèi)部點擴散算法射線算法和掃描算法邊界代數(shù)算法1內(nèi)部點擴散法每個面域多邊形中選擇一個內(nèi)部點〔擴散種子〕；從種子點開始向8個鄰域柵格擴散，分別判斷8個柵格是否在多邊形的邊界上，有兩種結(jié)果，一是在邊界上，那么這個柵格不再作為種子；二是不再邊界上，這個柵格將作為新的種子新的種子與原有種子一起繼續(xù)參與擴撒運算重復(fù)〔2〕〔3〕，直到所有種子點填滿該多邊形為止。擴散算法程序設(shè)計比較復(fù)雜，需要在柵格陣列中進行搜索，占用內(nèi)存很大。2射線算法射線算法可逐點判別數(shù)據(jù)柵格點在某多邊形之外或在多邊形內(nèi)，由待判點向圖外某點引射線，判斷該射線與某多邊形所有邊界相交的總次數(shù)，如相交偶數(shù)次，那么待判點在該多邊形的外部，如為奇數(shù)次，那么待判點在該多邊形內(nèi)部。射線算法要計算與多邊形交點，因此運算量大。另一個比較麻煩的問題是射線與多邊形相交時有些特殊情況如相切、重合等，會影響交點的個數(shù)，必須予以排除，由此造成算法的不完善，并增加了編程的復(fù)雜性。3掃描算法掃描算法是射線算法的改進，通常情況下，沿柵格陣列的行方向掃描，在每兩次遇到多邊形邊界點的兩個位置之間的柵格，屬于該多邊形。掃描算法省去了計算射線與多邊形交點的大量運算，大大提高了效率，但一般需要預(yù)留一個較大的數(shù)組以存放邊界點，而且掃描線與多邊形邊界相交的幾種特殊情況仍然存在，需要加以判別。4邊界代數(shù)算法邊界代數(shù)多邊形填充算法〔BoundaryAlgebraFilling，簡稱BAF〕，是任伏虎等設(shè)計并在微機地理信息系統(tǒng)上實現(xiàn)的一種基于積分思想的矢量格式向柵格格式轉(zhuǎn)換算法。適合記錄拓撲關(guān)系的多邊形矢量數(shù)據(jù)轉(zhuǎn)換為柵格數(shù)據(jù)。事實上，每幅地圖都是由多個多邊形區(qū)域組成的。如果把不屬于任何多邊形的區(qū)域〔包括無窮遠點〕看成一個編號為零的特殊區(qū)域，那么每一條邊界弧段都與兩個不同編號的多邊形相鄰，按邊界弧段的前進方向分別稱為左、右多邊形。對圖3－24所示的3個多邊形的6條邊，有如表3－5所示的多邊形編號。表3-5線號與左右多邊形號的對應(yīng)關(guān)系線號左多邊形右多邊形Ⅰ0n1Ⅱn20Ⅲn3n2Ⅳn1n2Ⅴn30Ⅵn3n1n2n1n3邊界代數(shù)算法的根本思想：對每幅地圖的全部具有左右多邊形編號的邊界弧段，沿其前進的方向逐個搜索，當邊界上行時，將邊界線位置與左圖框之間的網(wǎng)格點加上一個值=〔左多邊形編號〕-〔右多邊形編號〕；當邊界線下行時，將邊界線位置與左圖框的柵格點加上一個值=〔右多邊形編號〕-〔左多邊形編號〕，而不管邊界線的排列順序。射線算法單個多邊形的轉(zhuǎn)換多個多邊形的轉(zhuǎn)換

線號左多邊形右多邊形Ⅰ0n1Ⅱn20Ⅲn3n2Ⅳn1n2Ⅴn30Ⅵn3n1n2n1n3n2n1n3邊界代數(shù)法與其它算法的不同之處在于它不是逐點搜尋判別邊界，而是根據(jù)邊界的拓撲信息，通過簡單的加減代數(shù)運算將拓撲信息動態(tài)地賦予各柵格點，實現(xiàn)了矢量格式到柵格格式的轉(zhuǎn)換。由于不需考慮邊界與搜索軌跡之間的關(guān)系，因此算法簡單，可靠性好，而且由于僅采用加減代數(shù)運算，每條邊界僅計算一次，免去了公共邊界重復(fù)運算，又可不考慮邊界存放的順序，因此運算速度快，同時較少受內(nèi)存容量的限制，特別適用于微機地理信息系統(tǒng)。柵格數(shù)據(jù)向矢量數(shù)據(jù)轉(zhuǎn)換的目的有三：①數(shù)據(jù)入庫；②數(shù)據(jù)壓縮；③矢量制圖；

4.6.2柵格格式向矢量格式的轉(zhuǎn)換1〕多邊形邊界提?。骸捕祷?，平滑，細化〕2〕邊界線追蹤※3〕拓撲關(guān)系生成4〕去除多余點及曲線圓滑柵格格式向矢量格式的轉(zhuǎn)換的一般需要以下幾個步驟所謂的二值化，是在一個設(shè)定的灰度闕值的根底上，對掃描獲得的灰度圖像〔如256級灰度〕進行0或1的簡化處理，即有無判斷。算法如下：1〕圖像二值化1多邊形邊界提取由于線不光滑以及掃描、攝像系統(tǒng)的分辨率限制，使得一些曲線目標帶來多余的小分支〔即毛刺噪聲〕；此外，還有空洞和凹陷噪聲〔如以下圖〕，就會造成細化誤差和失真，這樣最影響最終柵格的跟蹤和矢量化。曲線目標越寬，提取骨架和去除輪廓所需的次數(shù)也就越多，因此誤差的影響也越大。2〕圖像細化預(yù)處理二值圖像平滑去除毛刺和空洞為了去除毛刺和空洞的影響，可以采用下面兩個模板進行處理。處理過程如下：按點陣格式掃描圖像上的每一個像素，只要圖像相應(yīng)區(qū)域與模板〔包括模板的90旋轉(zhuǎn)〕吻合，那么判定為毛刺〔或空洞〕，對應(yīng)模板中心數(shù)值變給0〔空洞模板將模板中心位置值改為1〕000010XXXX1X101XXX去除毛刺模板，X為任意值去除空洞模板，X為任意值3〕圖像細化線細化是處理包含線狀地物二值圖像的一種重要技術(shù)，在地圖掃描處理中，由于地圖上主要信息是不同粗細和不同形狀的線，必須首先進行線細化，以準確有效地提取這些線信息，并進一步矢量化。線細化就是不斷去除曲線上不影響連通性的輪廓像素的過程，對細化的一般要求是：保證細化后曲線的連通性；細化結(jié)果是原曲線的中心線；保存細線端點下面介紹幾種典型的細化方法：經(jīng)典的細化算法對于二值柵格圖像中每個像素點P,以及其直接相鄰的8個像素點，令：N(p)為p的鄰點的數(shù)值的和；圖像像素聯(lián)結(jié)數(shù)T(p)；Pw,PE,PS,PN分別指像素左側(cè)、右側(cè)、下邊、上邊鄰點的數(shù)值T(p)=0T(p)=0T(p)=1T(p)=1T(p)=2T(p)=2T(p)=2T(p)=3T(p)=4算法步驟如下：對于柵格圖像中的每一點p做如下操作：第一步：如果將所有被標志的柵格點賦值為0，如果沒有被標志的點，那么算法結(jié)束第二步：如果將所有被標志的柵格點賦值為0，如果沒有被標志的點，那么算法結(jié)束轉(zhuǎn)到第一步。骨架法原理：在二值化的根底上，針