第三章+空間數(shù)據(jù)結(jié)構

第三章空間數(shù)據(jù)結(jié)構內(nèi)容提要柵格數(shù)據(jù)結(jié)構矢量數(shù)據(jù)結(jié)構兩種數(shù)據(jù)結(jié)構的比較和轉(zhuǎn)換其他數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構：即數(shù)據(jù)組織的形式，是適合于計算機存儲、管理和處理的數(shù)據(jù)邏輯結(jié)構?？臻g數(shù)據(jù)結(jié)構：對地理實體的空間排列方式和相互關系的抽象描述方式，是對空間數(shù)據(jù)的一種解釋。GIS空間數(shù)據(jù)結(jié)構類型：柵格數(shù)據(jù)結(jié)構矢量數(shù)據(jù)結(jié)構矢柵一體化數(shù)據(jù)結(jié)構鑲嵌數(shù)據(jù)結(jié)構三維數(shù)據(jù)結(jié)構矢量結(jié)構和柵格結(jié)構第一節(jié)柵格數(shù)據(jù)結(jié)構基本概念數(shù)據(jù)表達形式特點數(shù)據(jù)獲取途徑?jīng)Q定柵格單元代碼的方式壓縮編碼方式1、

柵格數(shù)據(jù)結(jié)構基本概念

柵格結(jié)構是最簡單最直接的空間數(shù)據(jù)結(jié)構，又稱網(wǎng)格（gridcell)結(jié)構或像元（pixel）結(jié)構，是指將地球表面劃分為大小均勻、緊密相鄰的網(wǎng)格陣列，每個網(wǎng)格作為一個像元或像素由行號、列號定義，并包含一個代碼表示該像素的屬性類型或量值，或僅僅包括指向其屬性記錄的指針。柵格結(jié)構是以規(guī)則的陣列來表示空間地物或現(xiàn)象分布的數(shù)據(jù)組織，組織中的每個數(shù)據(jù)表示地物或現(xiàn)象的非幾何屬性特征。柵格結(jié)構表示的地表是不連續(xù)的，是量化和近似離散的數(shù)據(jù)。每一個單元格對應一個相應的地塊。點：一個柵格單元表示線：沿線走向的一組相鄰柵格單元表示面：有區(qū)域?qū)傩缘南噜彇鸥駟卧募媳硎?、柵格數(shù)據(jù)表達形式RealworldGridPointLineAreaValue=0=1=2=3RowColumnTrianglesHexagonsRASTER柵格數(shù)據(jù)結(jié)構示例（a）點（b）線（c）面柵格數(shù)據(jù)單元格經(jīng)常是矩形（主要是正方形）的，但并不是必須如此。其單元格形狀可以隨應用的需要進行具體設定，比如設置為三角形。柵格數(shù)據(jù)的比例尺就是柵格大小與地表相應單元大小之比。柵格尺寸越小，其分辨率越高，數(shù)據(jù)量也越大。柵格數(shù)據(jù)的形狀、尺寸及相關問題如右圖中，這幅地圖的比例尺=10cm:1000m=1:10000比例尺是刻畫數(shù)據(jù)精度的量（如最小線寬為地圖的空間分辨率）；空間分辨率示例1pixel=10mX10m分辨率=10m10M10M1Pixel由于柵格結(jié)構對地表的離散，在計算面積、長度、距離、形狀等空間指標時，若柵格尺寸較大，則造成較大的誤差。由于柵格單元中存在多種地物，而數(shù)據(jù)中常常只記錄一個屬性值，這會導致屬性誤差。比如，遙感數(shù)據(jù)中的“混合像元”問題。柵格數(shù)據(jù)的形狀、尺寸及相關問題3、柵格數(shù)據(jù)結(jié)構的特點屬性明顯數(shù)據(jù)中直接記錄了數(shù)據(jù)屬性或指向數(shù)據(jù)屬性的指針，因而我們可以直接得到地物的屬性代碼。定位隱含所在位置則根據(jù)行列號轉(zhuǎn)換為相應的坐標，也就是說定位是根據(jù)數(shù)據(jù)在數(shù)據(jù)集中的位置得到的。柵格結(jié)構是按一定的規(guī)則排列的，所表示的實體的位置很容易隱含在格網(wǎng)文件的存儲結(jié)構中。

3、柵格數(shù)據(jù)結(jié)構的特點柵格數(shù)據(jù)結(jié)構容易實現(xiàn)，算法簡單，且易于擴充、修改，也很直觀，特別是易于同遙感影像的結(jié)合處理，給地理空間數(shù)據(jù)處理帶來了極大的方便。4、柵格數(shù)據(jù)的獲取途徑目讀法矢量數(shù)據(jù)轉(zhuǎn)化掃描數(shù)字化分類影像輸入5、決定柵格單元代碼的方式

基本原則：在決定柵格代碼時盡量保持地表的真實性，保證最大的信息容量。注意：每一個單元可能對應多個地物種類或多個屬性值。比如遙感圖像中的“混合像元”。（1）中心點法處理方法：用處于柵格中心處的地物類型或現(xiàn)象特性決定柵格代碼。常用于具有連續(xù)分布特性的地理要素，如降雨量分布、人口密度圖等。例如：中心點O落在代碼為C的地物范圍內(nèi)，按中心點法的規(guī)則，該矩形區(qū)域相應的柵格單元代碼為C（2）面積占優(yōu)法處理方法：以占柵格區(qū)域面積比例最大的地物類型或現(xiàn)象特性決定柵格單元的代碼面積占優(yōu)法常用于分類較細，地物類別斑塊較小的情況。例如：所示的例子中，顯見B類地物所占面積最大，故相應柵格代碼定為B。（3）

重要性法處理方法：根據(jù)柵格內(nèi)不同地物的重要性，選取最重要的地物類型決定相應的柵格單元代碼重要性法常用于具有特殊意義而面積較小的地理要素，特別是點、線狀地理要素，如城鎮(zhèn)、交通樞紐、交通線、河流水系等，在柵格中代碼應盡量表示這些重要地物例如：假設A類最重要的地物類型，即A比B和C類更為重要，則柵格單元的代碼應為A（4）百分比法處理方法：根據(jù)柵格區(qū)域內(nèi)各地理要素所占面積的百分比數(shù)確定柵格單元的代碼。適用于地物面積具有重要意義的分類體系例如：可記面積最大的兩類BA，也可以根據(jù)B類和A類所占面積百分比數(shù)在代碼中加入數(shù)字（5）其他方法根據(jù)具體的應用內(nèi)容，柵格單元的代碼確定方式還可以采用其他方法，如插值方法（平均值就是其中之一），或使用特定的計算函數(shù)等。6、柵格數(shù)據(jù)編碼柵格數(shù)據(jù)編碼方法分為兩大類：直接柵格編碼壓縮編碼方法鏈碼

游程長度編碼

塊碼

四叉樹

直接柵格編碼直接編碼就是將柵格數(shù)據(jù)看作一個數(shù)據(jù)矩陣，逐行（或逐列）逐個記錄代碼，可以每行都從左到右逐個像元進行記錄，也可以奇數(shù)行的從左到右而偶數(shù)行的從右向左記錄，為了特定目的還可采用其他特殊的順序。優(yōu)點：編碼簡單，信息無壓縮、無丟失缺點:數(shù)據(jù)量大一些常用的柵格排列順序直接柵格編碼最簡單最直觀的一種柵格結(jié)構編碼方法。直接編碼就是將柵格數(shù)據(jù)看作一個數(shù)據(jù)矩陣，逐行逐個記錄代碼。0000000200010000203300000203330022220302022222002002222222000022220330020000333320000033332000000000壓縮編碼方式壓縮編碼的目的就是用盡可能少的數(shù)據(jù)量記錄盡可能多的信息，其類型分為：信息無損編碼編碼過程中沒有任何信息損失，通過解碼操作可以完全恢復原來的信息。

信息有損編碼為了提高編碼效率，最大限度地壓縮數(shù)據(jù)，在壓縮過程中損失一部分相對不太重要的信息，解碼時這部分難以恢復。

壓縮編碼方式在地理信息系統(tǒng)中的壓縮編碼多采用信息無損編碼，而對原始遙感影像進行壓縮時也可以采取有損壓縮編碼方法。壓縮編碼方式1鏈式編碼（ChainCodes）鏈式編碼又稱為弗里曼鏈碼（Freeman，1961）或邊界鏈碼。主要記錄線狀地物或面狀地物的邊界,忽略空白區(qū)域。它把線狀地物或面狀地物的邊界表示為：由某一起始點開始并按某些基本方向確定的單位矢量鏈。前兩個數(shù)字表示起點的行列號，從第三個數(shù)字開始的每個數(shù)字表示單位矢量的方向。基本方向可定義為：東＝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ù)代表。鏈碼（ChainCodes）優(yōu)點：

鏈式編碼對多邊形的表示具有很強的數(shù)據(jù)壓縮能力，且具有一定的運算功能，如面積和周長計算等，類似于矢量數(shù)據(jù)結(jié)構，比較適合于存儲線和面圖形數(shù)據(jù)。探測邊界急彎和凹進部分等都比較容易，比較適于存儲圖形數(shù)據(jù)。缺點：

對疊置運算如組合、相交等則很難實施，對局部修改將改變整體結(jié)構，效率較低，而且由于鏈碼以每個區(qū)域為單位存儲邊界，相鄰區(qū)域的公共邊界被重復存儲會產(chǎn)生冗余。壓縮編碼方式2、

游程長度編碼（Run-LengthCodes）

基本思路：對于一幅柵格圖像，常常有行（或列）方向上相鄰的若干點具有相同的屬性代碼，因而可采取某種方法壓縮那些重復的記錄內(nèi)容。

游程長度編碼（Run-LengthCodes）其實現(xiàn)方法有兩種：一種編碼方案是，只在各行（或列）數(shù)據(jù)的代碼發(fā)生變化時依次記錄該代碼以及相同的代碼重復的個數(shù)，從而實現(xiàn)數(shù)據(jù)的壓縮。即記錄該代碼以及相同代碼重復的個數(shù)。

另一種游程長度編碼方案就是逐個記錄各行（或列）代碼發(fā)生變化的位置和相應代碼。即記錄代碼及變化的位置（列數(shù)）。

游程長度編碼示例按第一種編碼方法，代碼,個數(shù)，代碼,個數(shù)……此數(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個柵格。游程長度編碼示例按第二種編碼方法，代碼,（終止）位置，代碼,（終止）位置……此數(shù)據(jù)游程長度編碼（沿列方向）：（0，1），（4，3），（7，8）（4，5），（7，8）；（4，4），（8，6），（7，8）；（0，2），（4,3）（8，6），（7，8）（0，2），（8，6），（7，7），（8，8）；（0，3），（8，8）；（0，4，（8，8）；（0，5），（8，8）游程長度編碼的特點及優(yōu)缺點屬性的變化愈少，行程愈長，壓縮比例越大，即壓縮比的大小與圖的復雜程度成反比。優(yōu)點壓縮效率較高（保證原始數(shù)據(jù)不丟失），易于檢索，疊加、合并等操作，運算簡單。缺點只顧及單行單列，沒有考慮周圍的其他方向的代碼值是否相同。對于圖斑破碎，屬性和邊界多變的數(shù)據(jù)壓縮效率較低，甚至壓縮后的數(shù)據(jù)量比原始數(shù)據(jù)還大。

壓縮編碼方式3、塊碼（ChainCodes）

塊碼是游程長度編碼擴展到二維的情況，采用方形區(qū)域作為記錄單元，每個記錄單元包括相鄰的若干柵格，數(shù)據(jù)結(jié)構由初始位置（行、列號）和半徑，再加上記錄單位的代碼組成。即：（初始行、列，半徑，屬性值）塊碼編碼示例其塊碼編碼為：(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)。特點：具有可變分辨率，即當屬性變化小時圖塊大，對于大塊圖斑記錄單元大，分辨率低，壓縮比高。小塊圖斑記錄單元小，分辨率高，壓縮比低,所以，與游程長度編碼類似，隨圖形復雜程度的提高而分辯率降低。壓縮編碼方式4、

四叉樹編碼

基本思路：將一幅柵格圖象等分為四等分，逐塊檢查其格網(wǎng)屬性值（或灰度）。如果某一子區(qū)的所有柵格的具有相同的值，則這個子區(qū)不再繼續(xù)分割，否則還要把這個子區(qū)再分割為四個子區(qū)。這樣依此地分割，直到每個子區(qū)都有相同的屬性值或灰度為止。

結(jié)果：將整個圖像區(qū)逐步分解為一系列僅包含單一類型的方形區(qū)域，最小的方形區(qū)域為一個柵格象元。

四叉樹的樹形表示：用一倒立樹表示這種分割和分割結(jié)果。根：整個區(qū)域高：深度、分幾級，幾次分割葉：不能再分割的塊樹叉：還需分割的塊每個樹叉均有4個分叉，叫四叉樹。AAAAABBBAABBAABB0123

其中最上面的結(jié)點叫根結(jié)點，它對應整個圖形。此樹共有4層結(jié)點，每個結(jié)點對應一個象限，如第2層4個結(jié)點分別對應于整個圖形的四個象限，排列次序依次為南西（SW）、南東（SE）、北西（NW）和北東（NE），不能再分的結(jié)點稱為終止結(jié)點（又稱葉子結(jié)點），可能落在不同的層上，該結(jié)點代表的子象限具有單一的代碼，所有終止結(jié)點所代表的方形區(qū)域覆蓋了整個圖形。從上到下，從左到右為葉子結(jié)點編號，共有40個葉子結(jié)點，也就是原圖被劃分為40個大小不等的方形子區(qū)（最下面的一排數(shù)字表示各子區(qū)的代碼）。四叉樹編碼示例四叉樹編碼

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

四叉樹編碼

由上而下的方法運算量大，耗時較長。因而實踐中可以采用從下而上的方法建立四叉樹編碼。對柵格數(shù)據(jù)按如下的順序進行檢測：如果每相鄰四個柵格值相同則進行合并，逐次往上遞歸合并，直到符合四叉樹的原則為止。這種方法重復計算較少，運算速度較快。四叉樹的結(jié)構方式四叉樹結(jié)構按其編碼的方法不同分為常規(guī)四叉樹和線性四叉樹：常規(guī)四叉樹：除了記錄葉結(jié)點之外，還要記錄中間結(jié)點。結(jié)點之間借助指針聯(lián)系，每個結(jié)點需要用六個量表達：四個葉結(jié)點指針，一個父結(jié)點指針和一個結(jié)點的屬性或灰度值。這些指針不僅增加了數(shù)據(jù)貯存量，而且增加了操作的復雜性。常規(guī)四叉樹主要在數(shù)據(jù)索引和圖幅索引等方面應用。四叉樹的結(jié)構方式四叉樹結(jié)構按其編碼的方法不同分為常規(guī)四叉樹和線性四叉樹：線性四叉樹：只存貯最后葉結(jié)點的信息。包括葉結(jié)點的位置、深度和本結(jié)點的屬性或灰度值。所謂深度是指處于四叉樹的第幾層上。由深度可推知子區(qū)的大小。線性四叉樹葉結(jié)點的編號需要遵循一定的規(guī)則，這種編號稱為地址碼，它隱含了葉結(jié)點的位置和深度信息。最常用的地址碼是四進制或十進制的Morton碼。四叉樹編碼示例

四叉樹編碼的優(yōu)缺點優(yōu)點：四叉樹編碼具有可變的分辨率，樹的深度隨數(shù)據(jù)的破碎程度而變化，并且有區(qū)域性質(zhì)，壓縮數(shù)據(jù)靈活，許多數(shù)據(jù)和轉(zhuǎn)換運算可以在編碼數(shù)據(jù)上直接實現(xiàn)，大大地提高了運算效率，并支持拓撲“洞”（嵌套多邊形）的表達，是優(yōu)秀的柵格壓縮編碼之一。缺點：其最大不足是其不穩(wěn)定性，即同樣的原始數(shù)據(jù)應用不同的算法進行編碼可能會得到不同的編碼結(jié)果。不利于數(shù)據(jù)分析。壓縮編碼方式5、其他編碼

還有很多編碼方法，如傅立葉變換、小波變換、余弦變換等，常常用于遙感原始數(shù)據(jù)的壓縮。由于它們多數(shù)是有損壓縮，一般不用于需要進行分析的柵格數(shù)據(jù)。在四叉樹基礎上發(fā)展而來的八叉樹目前也是研究熱點之一。壓縮編碼的相關問題同所有的數(shù)據(jù)結(jié)構問題一樣，壓縮編碼過程的主要矛盾也是數(shù)據(jù)量壓縮和運算時間之間的矛盾：為了更有效地利用空間資源，減少數(shù)據(jù)冗余，不得不花費更多的運算時間進行編碼。好的壓縮編碼方法就是要在盡可能減少運算時間的基礎上達到最大的數(shù)據(jù)壓縮效率，并且是算法適應性強，易于實現(xiàn)。常見柵格壓縮編碼方法總結(jié)鏈碼：壓縮效率較高，已經(jīng)近矢量結(jié)構，對邊界的運算比較方便，但不具有區(qū)域的性質(zhì)，區(qū)域運算困難。游程長度編碼：既可以在很大程度上壓縮數(shù)據(jù)，又最大限度地保留了原始柵格結(jié)構，編碼解碼十分容易。但對破碎數(shù)據(jù)處理效果不好。塊碼和四叉樹編碼：具有區(qū)域性質(zhì)，又具有可變的分辨率，有較高的壓縮效率，但運算效率是其瓶頸。其中四叉樹編碼可以直接進行大量圖形圖像運算，效率較高，是很有前途的方法。

第二節(jié)矢量數(shù)據(jù)結(jié)構及其編碼基本概念特點數(shù)據(jù)獲取方式編碼方式1．矢量數(shù)據(jù)結(jié)構基本概念前導概念：矢量（起點－>終點）矢量數(shù)據(jù)結(jié)構：通過記錄坐標的方式盡可能精確地表示點、線、多邊形等地理實體，坐標空間設為連續(xù)，允許任意位置、長度和面積的精確定義。在一般情況下，其精度比柵格數(shù)據(jù)結(jié)構高得多。其精度僅受數(shù)字化設備的精度和數(shù)值記錄字長的限制。矢量結(jié)構允許最復雜的數(shù)據(jù)以最小的數(shù)據(jù)冗余進行存儲，相對柵格結(jié)構來說，數(shù)據(jù)精度高，所占空間小，是高效的空間數(shù)據(jù)結(jié)構。矢量數(shù)據(jù)的類型Buildings.PolygonStreams,LineWells,PointRoads,LineZoning, PolygonMAPSHEETS矢量表達形式點：單獨一對坐標(x、y)表示線：兩對以上的坐標對(x1、y1)，(x2、y2),…(xn、yn)表示。（弧、鏈）面：兩對以上的坐標對(x1、y1)，(x2、y2),…(xn、yn),(x1、y1)表示。適合于表達有精確的形狀和邊界離散的實體2．矢量數(shù)據(jù)結(jié)構特點（1）定位明顯

其定位是根據(jù)坐標直接存儲的，無需任何推算。（2）屬性隱含

屬性則一般存于文件頭或數(shù)據(jù)結(jié)構中某些特定的位置上。2、矢量數(shù)據(jù)結(jié)構特點

矢量數(shù)據(jù)結(jié)構圖形運算的算法總體上比柵格數(shù)據(jù)結(jié)構復雜的多，在疊加運算、鄰域搜索等操作時比較困難，有些甚至難以實現(xiàn)。 但其也有便利和獨到之處，在計算長度、面積、形狀和圖形編輯、幾何變換操作中，矢量結(jié)構有很高的效率和精度。矢量數(shù)字化法：矢量數(shù)據(jù)掃描數(shù)字化法：柵格數(shù)據(jù)-〉矢量數(shù)據(jù)野外測量數(shù)據(jù)（全站儀、GPS等）：矢量數(shù)據(jù)影像：柵格數(shù)據(jù)-〉矢量數(shù)據(jù)手工輸入：矢量數(shù)據(jù)3、矢量數(shù)據(jù)結(jié)構獲取途徑4、矢量數(shù)據(jù)編碼編碼方法：點實體線實體多邊形無拓撲關系的編碼方法拓撲結(jié)構編碼法

(X,Y)(X2,Y2)(X3,Y3)(X4,Y4)(X5,Y5)LinePoint(X5,Y5)(X,Y)(X2,Y2)(X4,Y4)(X3,Y3)Polygon(X,Y)4、矢量數(shù)據(jù)編碼（1）點實體

點是空間上不能再分的地理實體，可以是具體的或抽象的，如地物點、文本位置點或線段網(wǎng)絡的結(jié)點等，由一對（x、y）坐標表示。 對于點實體，矢量結(jié)構中只記錄其在特定坐標系下的坐標和屬性代碼。點實體數(shù)據(jù)編碼（2）線實體 對于線實體，在數(shù)字化時即進行量化，就是用一系列足夠短的直線首尾相接表示一條曲線，當曲線被分割成多而短的線段后，這些小線段可以近似地看成直線段，而這條曲線也可以足夠精確地由這些小直線段序列表示，矢量結(jié)構中只記錄這些小線段的端點坐標，將曲線表示為一個坐標序列，坐標之間認為是以直線段相連，在一定精度范圍內(nèi)可以逼真地表示各種形狀的線狀地物。線實體矢量數(shù)據(jù)編碼唯一標識碼是系統(tǒng)排列序號；線標識碼可以標識線的類型；起始點和終止點號可直接用坐標表示；顯示信息是顯示時的文本或符號等；與線相聯(lián)系的非幾何屬性可以直接存儲于線文件中，也可單獨存儲，而由標識碼聯(lián)接查找。（3）多邊形實體編碼

“多邊形”在地理信息系統(tǒng)中是指一個任意形狀、邊界完全閉合的空間區(qū)域。其邊界將整個空間劃分為外部和內(nèi)部。 多邊形數(shù)據(jù)是描述地理信息的最重要的一類數(shù)據(jù)。在區(qū)域?qū)嶓w中，具有名稱屬性和分類屬性的，多用多邊形表示，如行政區(qū)、土地類型、植被分布等。多邊形實體編碼

多邊形矢量編碼不但要表示位置和屬性，更為重要的是要能表達區(qū)域的拓撲性質(zhì)，如形狀、鄰域和層次等，以便使這些基本的空間單元可以作為專題圖資料進行顯示和操作，由于要表達的信息十分豐富，基于多邊形的運算多而復雜，因此多邊形矢量編碼比點和線實體的矢量編碼要復雜得多，也更為重要。多邊形實體編碼方法多邊形實體的編碼方法分為兩種：一是無拓撲關系的編碼方法：僅記錄地理目標的空間位置和屬性信息，而不記錄拓撲關系。Spaghetti模型(獨立實體法)點位字典法二是拓撲關系的編碼方法：不僅記錄地理目標的位置和屬性信息，而且記錄拓撲關系。樹狀索引編碼法網(wǎng)絡模型(NetworkModel)拓撲模型(TopologicalModel)1、坐標序列法（Spaghetti模型）

由多邊形邊界的x、y坐標對集合及說明信息組成，是最簡單的一種多邊形矢量編碼。Spaghetti模型：以實體為單位進行編碼點目標：唯一標識碼，地物編碼，(X,Y)線目標：唯一標識碼，地物編碼，(X1,Y1…Xn,Yn)面目標：唯一標識碼，地物編碼，(X1,Y1…Xn,Yn,X1,Y1)坐標序列法（Spaghetti方式）坐標序列法的優(yōu)缺點優(yōu)點文件結(jié)構簡單，易于實現(xiàn)以多邊形為單位的運算和顯示缺點多邊形之間的公共邊界被數(shù)字化和存儲兩次，由此產(chǎn)生冗余和碎屑多邊形；每個多邊形自成體系而缺少鄰域信息，難以進行鄰域處理，如消除某兩個多邊形之間的共同邊界；島只作為一個單個的圖形建造，沒有與外包多邊形的聯(lián)系；不易檢查拓撲錯誤。這種方法可用于簡單的粗精度制圖系統(tǒng)中。點位字典法：點坐標作為一個文件，點、線和多邊形由點號組成，即點位字典：點號、(X,Y)點目標：唯一標識碼，地物編碼，點號線目標：唯一標識碼，地物編碼，(點號1…點號n)面目標：唯一標識碼，地物編碼，(點號1…點號n,點號1)優(yōu)點：編碼比較容易，數(shù)字化操作比較簡單，數(shù)據(jù)編碼比較直觀缺點：操作比較困難，拓撲關系不完整.2、點位字典法拓撲結(jié)構編碼法

要徹底解決鄰域和島狀信息處理問題必須建立一個完整的拓撲關系結(jié)構，這種結(jié)構應包括以下內(nèi)容：唯一標識，多邊形標識，外包多邊形指針，鄰接多邊形指針，邊界鏈接，范圍（最大和最小x、y坐標值，即外包矩形信息）。采用拓撲結(jié)構編碼可以較好地解決空間關系查詢等問題，但增加了算法的復雜性和數(shù)據(jù)庫的大小。3、樹狀索引編碼法

采用樹狀索引以減少數(shù)據(jù)冗余并間接增加鄰域信息。

方法：對所有邊界點進行數(shù)字化，將坐標對以順序方式存儲，由點索引與邊界線號相聯(lián)系，以線索引與各多邊形相聯(lián)系，形成樹狀索引結(jié)構。樹狀索引編碼法示例圖形數(shù)據(jù)樹狀索引編碼法示例線與多邊形之間的樹狀索引樹狀索引編碼法示例點與邊界線之間的樹狀索引樹狀索引編碼法示例形成的文件記錄

樹狀索引編碼法的優(yōu)勢和不足

樹狀索引編碼消除了相鄰多邊形邊界的數(shù)據(jù)冗余和不一致的問題，在簡化過于復雜的邊界線或合并相鄰多邊形時可不必改造索引表，鄰域信息和島狀信息可以通過對多邊形文件的線索引處理得到，但是比較繁瑣，因而給相鄰函數(shù)運算，消除無用邊，處理島狀信息以及檢查拓撲關系帶來一定的困難，而且兩個編碼表都需要以人工方式建立，工作量大且容易出錯。4、網(wǎng)絡模型網(wǎng)絡模型(NetworkModel)概念節(jié)點(Node):連接弧段的點弧段(Arc)：開始于節(jié)點，而終止于節(jié)點的線應用矢量數(shù)據(jù)編碼網(wǎng)絡模型DIME(DualIndependentMapEncoding)-雙重獨立地圖編碼基本原理：對圖上網(wǎng)狀或面狀要素的任何一條線段，用其兩端的節(jié)點及相鄰的面域來予以定義。最早用于美國人口普查分析和制圖，以城市街道為編碼的主體，采用了拓撲編碼結(jié)構。多邊形實體編碼節(jié)點號坐標1x,y2x,y3x,y4x,y5x,y6x,y7x,y8x,y9x,y弧段號起始節(jié)點起始節(jié)點左多邊形右多邊形112012230234513456245783068940714108473092521105843113602126904節(jié)點表弧段表1234567891234569107812341112雙重獨立式地圖編碼網(wǎng)絡模型(NetworkModel)主要包含兩個表：節(jié)點表：唯一標識碼，(X,Y)弧段表：唯一標識碼，起始結(jié)點，終止結(jié)點，中間點坐標串。表示的拓撲關系：節(jié)點-節(jié)點之間的鄰接關系，節(jié)點-弧段之間的關聯(lián)關系，多邊形實體編碼5、拓撲模型(TopologicalModel）拓撲模型包含三或四個個文件：節(jié)點文件：唯一標識碼，(X,Y)弧段文件：唯一標識碼，起始結(jié)點，終止結(jié)點，左多邊形，右多邊形，指向中間點坐標的指針或者坐標串多邊形文件：唯一標識碼，組成多邊形的弧段號及面積、周長及中心點坐標等弧段坐標：如果弧段中的中間點為指針多邊形實體編碼三個四個節(jié)點號坐標1x,y2x,y3x,y4x,y5x,y6x,y7x,y8x,y9x,y弧段號起始節(jié)點起始節(jié)點左多邊形右多邊形中間點11201p122302p234513456245783068940714108473092521105843113602126904p12節(jié)點文件弧段文件1234567891234569107812341112POLYVRT（Polygon-Converter)結(jié)構:多邊形號弧段號面積周長11,9,3,722,11,4,933,10,5,844,12,6,10多邊形文件ID坐標12弧段坐標文件POLYVRT（Polygon-Converter)結(jié)構:美國計算機圖形及空間分析實驗室研制，是當今各種圖形數(shù)據(jù)結(jié)構的基本框架（鏈狀雙重獨立式）。拓撲模型(TopologicalModel)表示的拓撲關系：節(jié)點-節(jié)點之間的鄰接關系，多邊形-多邊形之間的鄰接關系，節(jié)點-線段之間的關聯(lián)關系，線段-多邊形之間的關聯(lián)關系。優(yōu)點：數(shù)據(jù)結(jié)構緊湊、數(shù)據(jù)冗余??；拓撲關系明晰使得拓撲查詢、拓撲分析效率高缺點：對單個地理實體的操作效率低、難以表達復雜的地理實體、查詢效率低、局部更新困難。矢量數(shù)據(jù)結(jié)構編碼總結(jié)

矢量編碼保證了信息的完整性和運算的靈活性，這是由矢量結(jié)構自身的特點所決定的。目前并沒有統(tǒng)一的最佳的矢量結(jié)構編碼方法，在具體工作中應根據(jù)數(shù)據(jù)的特點和任務的要求而靈活設計。第三節(jié)、兩種數(shù)據(jù)結(jié)構的比較及轉(zhuǎn)換一、柵格結(jié)構與矢量結(jié)構的比較優(yōu)點缺點矢量數(shù)據(jù)結(jié)構數(shù)據(jù)結(jié)構嚴密，冗余度小，數(shù)據(jù)量小2.空間拓撲關系清晰，易于網(wǎng)絡分析；3.面向?qū)ο竽繕说?，不僅能表達屬性編碼，而且能方便地記錄每個目標的具體的屬性描述信息；4.能夠?qū)崿F(xiàn)圖形數(shù)據(jù)的恢復、更新和綜合；5、圖形顯示質(zhì)量好、精度高。1.數(shù)據(jù)結(jié)構處理算法復雜2.疊置分析與柵格圖組合比較難；3.數(shù)學模擬比較困難；4.空間分析技術上比較復雜，需要更復雜的軟、硬件條件；5.顯示與繪圖成本比較高。柵格數(shù)據(jù)結(jié)構1.數(shù)據(jù)結(jié)構簡單，易于算法實現(xiàn)；2.空間數(shù)據(jù)的疊置和組合容易，有利于與遙感數(shù)據(jù)的匹配應用和分析；3.各類空間分析，地理現(xiàn)象模擬均較為容易；4.輸出方法快速簡易，成本低廉。1.圖形數(shù)據(jù)量大，用大像元減小數(shù)據(jù)量時，精度和信息量受損失；2.難以建立空間網(wǎng)絡連接關系；3.投影變化實現(xiàn)困難；4.圖形數(shù)據(jù)質(zhì)量低，地圖輸出不精美。在地理信息系統(tǒng)中，柵格數(shù)據(jù)與矢量數(shù)據(jù)各有千秋，它們互相補充，必要時可互相轉(zhuǎn)換，這是由地理信息系統(tǒng)處理方式以及這兩種數(shù)據(jù)格式各自的特點所決定的；矢量數(shù)據(jù)->柵格數(shù)據(jù)柵格數(shù)據(jù)->矢量數(shù)據(jù)二、數(shù)據(jù)轉(zhuǎn)換矢量數(shù)據(jù)->柵格數(shù)據(jù)（1）點的柵格化

i=1+integer((Ymax-y)/dx)

j=1+integer((x-Xmin)/dy)

dx=(Xmax-Xmin)/J

dy=(Ymax-Ymin)/I

其中(x,y)為矢量點位坐標；dx,dy為柵格單元的兩個邊長；Xmin,Ymin表示圖幅范圍的最小值，Xmax,Ymax表示圖幅范圍的最大值，I,J表示全圖網(wǎng)格單元的行數(shù)和列數(shù)。1、矢量——柵格轉(zhuǎn)換1、矢量數(shù)據(jù)->柵格數(shù)據(jù)（2）線段的柵格化：確定直線經(jīng)過的中間網(wǎng)格。

矢量數(shù)據(jù)->柵格數(shù)據(jù)（3）面域的柵格化左碼記錄法種子點填充算法射線算法掃描線算法復數(shù)積分算法邊界代數(shù)算法

1、矢量-柵格轉(zhuǎn)換射線算法單個多邊形的轉(zhuǎn)換多個多邊形的轉(zhuǎn)換

左碼記錄法基本原理：有一閉合多邊形，它將整個矩形面域分割成屬性為1和0的兩部分。面域外為0，面域內(nèi)為1。對多邊形的每一條邊，按線段柵格化的方法進行轉(zhuǎn)換。對轉(zhuǎn)換后的多邊形節(jié)點進行處理，使節(jié)點的柵格值唯一而準確。從第一行其逐行按列的先后順序排序，形成壓縮編碼柵格結(jié)構。將壓縮編碼柵格結(jié)構展開為全柵格數(shù)據(jù)結(jié)構。2、柵格數(shù)據(jù)->矢量數(shù)據(jù)點線二值化－>0、1細化->骨架圖線追蹤面二值化－>0、1細化->骨架圖邊界線追蹤拓撲關系生成去處多余點并進行曲線光滑2、柵格——矢量轉(zhuǎn)化轉(zhuǎn)換算法柵格格式向矢量格式的轉(zhuǎn)換1）多邊形邊界提取2）邊界線追蹤3）拓撲關系生成4）去除多余點及曲線圓滑第四節(jié)其他數(shù)據(jù)結(jié)構1、矢柵一體化數(shù)據(jù)結(jié)構2、鑲嵌數(shù)據(jù)結(jié)構3、三維數(shù)據(jù)結(jié)構1、矢柵一體化數(shù)據(jù)結(jié)構概念：將矢量面向地理實體的方法和柵格像元充填的方法結(jié)合起來表達地理實體的數(shù)據(jù)結(jié)構。從本質(zhì)上說，是一種以矢量的方式來組織柵格數(shù)據(jù)的數(shù)據(jù)結(jié)構?；舅悸罚好鏍顚嶓w的邊界采用矢量數(shù)據(jù)結(jié)構描述，而其內(nèi)部采用柵格數(shù)據(jù)結(jié)構表達；線狀實體一般采用矢量數(shù)據(jù)結(jié)構表達，同時將線所經(jīng)過位置以柵格單元填充。實體點則同時描述其空間坐標和柵格單元位置。理論基礎：多級格網(wǎng)方法三個基本約定線性四叉樹編碼返回多級格網(wǎng)方法將柵格劃分為多級格網(wǎng)：粗格網(wǎng)、基本格網(wǎng)和細分格網(wǎng)。粗格網(wǎng)：建立空間索引基本格網(wǎng)：基本柵格的大小。細分格網(wǎng)：為了增加空間分辨率，在基本格網(wǎng)的基礎上細分為16×16或256×256的格網(wǎng)。三個基本約定（1）地面上的點狀地物是地球表面上的點，它僅有空間位置，沒有形狀和面積，在計算機內(nèi)部僅有一個位置數(shù)據(jù)。（2）地面上的線狀地物是地球表面的空間曲線，它有形狀但沒有面積，它在平面上的投影是一連續(xù)不間斷的直線或曲線，在計算機內(nèi)部需要用一組元子填滿整個路徑。（3）地面上的面狀地物是地球表面的空間曲面，并具有形狀和面積，它在平面上的投影是由邊界包圍的空間和一組填滿路徑的元子表達的邊界組成。點狀地物：除記錄原始點的空間坐標外，還記錄柵格單元的位置。用（M1、M2)代替(X、Y)；線狀地物：除記錄原始取樣點外，還記錄路徑所通過的柵格。用Morton碼記錄原始采樣點的中間點的位置，必要時記錄線目標所穿過的基本網(wǎng)格的交線位置。面狀地物：除記錄它的多邊形周邊以外，還包括中間的面域柵格。除用Morton碼記錄原始采樣點的中間點的位置，必要時記錄線目標所穿過的基本網(wǎng)格的交線位置外，還要用鏈指針記錄多邊形的內(nèi)部柵格。（1）它保留了矢量的全部性質(zhì)，以目標為單元直接聚集所有的位置信息，并能建立拓撲關系；（2）它建立了柵格與地物的關系，即路徑上的任一點都直接與目標建立了聯(lián)系。矢柵一體化數(shù)據(jù)結(jié)構域的特征334334423344423344234422212提問：請說出上述兩種方法的坐標記錄上的差異2、鑲嵌數(shù)據(jù)結(jié)構原理：基于連續(xù)鋪蓋的思想，利用規(guī)則或不規(guī)則的小面塊集合來逼近自然界不規(guī)則的地理單元，小面塊之間不重疊且能完整鋪滿整個地理空間。根據(jù)面塊的形狀，鑲嵌數(shù)據(jù)結(jié)構分為（1）規(guī)則鑲嵌數(shù)據(jù)結(jié)構（2）不規(guī)則鑲嵌數(shù)據(jù)結(jié)構（1）規(guī)則鑲嵌數(shù)據(jù)結(jié)構基本原理：用規(guī)則的小面塊集合來逼近自然界不規(guī)則的地理單元。鑲嵌單元：正三角形、等腰直角三角形、矩形、正六方形、平行四邊形。模型構建：用數(shù)學手段將一個鋪蓋格網(wǎng)疊置在所研究的區(qū)域上，把連續(xù)的地理空間離散為互不覆蓋的面塊單元（格網(wǎng)）。（1）規(guī)則鑲嵌數(shù)據(jù)結(jié)構優(yōu)點：（1）數(shù)據(jù)結(jié)構為通常的二維柵格矩陣結(jié)構，每個格網(wǎng)單元表示二維空間的一個位置。（2）以矩陣形式存儲的數(shù)據(jù)具有隱式坐標，不需要進行坐標數(shù)字化，規(guī)則格網(wǎng)系統(tǒng)還便于實現(xiàn)多要素的疊置分析。（2）不規(guī)則鑲嵌數(shù)據(jù)結(jié)構基本概念：用來進行鑲嵌的小面塊具有不規(guī)則的形狀或邊界。分類：不規(guī)則三角網(wǎng)（TIN數(shù)據(jù)結(jié)構)

Voronoi圖（Thiessen多邊形）不規(guī)則三角網(wǎng)（TIN）模型不規(guī)則三角網(wǎng)（TriangulatedIrregularNetwork,TIN）是另外一種表示連續(xù)地理實體或者現(xiàn)象的方法，它既減少規(guī)則格網(wǎng)方法帶來的數(shù)據(jù)冗余，同時在計算（如坡度）效率