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

第四章空間數(shù)據(jù)結(jié)構(gòu)第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第1頁(yè)。

數(shù)據(jù)結(jié)構(gòu)即數(shù)據(jù)的組織形式，是適用于計(jì)算機(jī)存儲(chǔ)、管理、處理的數(shù)據(jù)邏輯表達(dá)。換句話說(shuō)，是指數(shù)據(jù)以什么形式在計(jì)算機(jī)中存儲(chǔ)和處理。

空間數(shù)據(jù)結(jié)構(gòu)是空間邏輯數(shù)據(jù)模型在計(jì)算機(jī)中的組織關(guān)系和編排方式。包括基于矢量模型的矢量數(shù)據(jù)結(jié)構(gòu)、基于柵格模型的柵格數(shù)據(jù)結(jié)構(gòu)和基于不規(guī)則鑲嵌模型的TIN的曲面數(shù)據(jù)結(jié)構(gòu)等。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第2頁(yè)。矢量數(shù)據(jù)結(jié)構(gòu)

矢量數(shù)據(jù)結(jié)構(gòu)是對(duì)矢量數(shù)據(jù)模型進(jìn)行數(shù)據(jù)的組織，通過(guò)記錄坐標(biāo)的方式盡可能精確地表示點(diǎn)、線、多邊形等地理實(shí)體，坐標(biāo)空間設(shè)為連續(xù)，允許任意位置、長(zhǎng)度和面積的精確定義。其精度僅受數(shù)字化設(shè)備的精度和數(shù)值記錄字長(zhǎng)的限制。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第3頁(yè)。矢量數(shù)據(jù)矢量數(shù)據(jù)的類(lèi)型Buildings.PolygonStreams,LineWells,PointRoads,LineZoning, PolygonMAPSHEETS第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第4頁(yè)。

矢量結(jié)構(gòu)允許最復(fù)雜的數(shù)據(jù)以最小的數(shù)據(jù)冗余進(jìn)行存儲(chǔ)，相對(duì)柵格結(jié)構(gòu)來(lái)說(shuō)，數(shù)據(jù)精度高，數(shù)據(jù)存儲(chǔ)的冗余小，是高效的空間數(shù)據(jù)結(jié)構(gòu)。分為實(shí)體數(shù)據(jù)結(jié)構(gòu)和拓?fù)鋽?shù)據(jù)結(jié)構(gòu)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第5頁(yè)。實(shí)體數(shù)據(jù)結(jié)構(gòu)

實(shí)體數(shù)據(jù)結(jié)構(gòu)中，空間數(shù)據(jù)按照基本的空間對(duì)象（點(diǎn)、線或多邊形）為單元進(jìn)行單獨(dú)的組織，其中不包含拓?fù)潢P(guān)系信息，最典型的是所謂的面條（spaghetti）結(jié)構(gòu)，又稱(chēng)為坐標(biāo)序列法。常采用這種數(shù)據(jù)結(jié)構(gòu)的有ArcGIS中的Shape文件和MapInfo的Tab文件等。（49頁(yè)）第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第6頁(yè)。點(diǎn)的表示線的表示面的表示矢量數(shù)據(jù)模型中單一空間實(shí)體的表達(dá)第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第7頁(yè)。坐標(biāo)序列法（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ù)第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第8頁(yè)。坐標(biāo)序列法的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：文件結(jié)構(gòu)簡(jiǎn)單，易于實(shí)現(xiàn)以多邊形為單位的運(yùn)算和顯示缺點(diǎn)：對(duì)于相連的線，交叉點(diǎn)要重復(fù)輸入和存儲(chǔ)；對(duì)于多邊形其公共邊也要重復(fù)輸入和存儲(chǔ)，從而產(chǎn)生數(shù)據(jù)冗余和分析處理不便的問(wèn)題；對(duì)于復(fù)雜多邊形，不能解決多邊形中“島”、“洞”之類(lèi)的鑲套問(wèn)題，“島”或“洞”只能作為單個(gè)的多邊形來(lái)構(gòu)造，沒(méi)有和周?chē)亩噙呅谓㈥P(guān)系；很難檢查多邊形的邊界正確與否，即多邊形的完整性；每個(gè)多邊形自成體系，缺少有關(guān)鄰域的信息，使拓?fù)潢P(guān)系，即相鄰關(guān)系很難跟蹤。適用范圍：制圖及一般查詢，不適合復(fù)雜的空間分析第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第9頁(yè)。4.1.2拓?fù)浣Y(jié)構(gòu)編碼法具有拓?fù)潢P(guān)系的矢量數(shù)據(jù)結(jié)構(gòu)就是拓?fù)鋽?shù)據(jù)結(jié)構(gòu)。拓?fù)鋽?shù)據(jù)模型是一種基于矢量的比較有效的數(shù)據(jù)模型，ArcGIS的Coverage就是一種拓?fù)鋽?shù)據(jù)結(jié)構(gòu)。拓?fù)鋽?shù)據(jù)結(jié)構(gòu)包括樹(shù)狀索引編碼法、雙重獨(dú)立編碼結(jié)構(gòu)、鏈狀雙重獨(dú)立編碼結(jié)構(gòu)等。其實(shí)質(zhì)是通過(guò)地理實(shí)體之間的空間關(guān)系表示來(lái)線和多邊形。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第10頁(yè)?；靖拍罨《危簶?gòu)成多邊形的線稱(chēng)為弧段，每個(gè)弧段可以有許多中間點(diǎn)。節(jié)點(diǎn)：兩條以上弧段相交的點(diǎn)稱(chēng)為節(jié)點(diǎn)島：由一條弧段組成的多邊形稱(chēng)為島或洞。簡(jiǎn)單多邊形：多邊形圖中不含島的多邊形稱(chēng)為簡(jiǎn)單多邊形。復(fù)合多邊形：含島的多邊形稱(chēng)為復(fù)合多邊形，包括為邊界和內(nèi)邊界，島可以看做復(fù)合多邊形的內(nèi)邊界。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第11頁(yè)。1樹(shù)狀索引編碼法（層次索引法、索引式結(jié)構(gòu)）

采用樹(shù)狀索引以減少數(shù)據(jù)冗余并間接增加鄰域信息，方法是對(duì)所有邊界點(diǎn)進(jìn)行數(shù)字化，將坐標(biāo)對(duì)以順序方式存儲(chǔ)，由點(diǎn)索引與邊界線號(hào)相聯(lián)系，以線索引與各多邊形相聯(lián)系，形成樹(shù)狀索引結(jié)構(gòu)第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第12頁(yè)。樹(shù)狀索引編碼法示例圖形數(shù)據(jù)第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第13頁(yè)。樹(shù)狀索引編碼法示例線與多邊形之間的樹(shù)狀索引第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第14頁(yè)。樹(shù)狀索引編碼法示例點(diǎn)與邊界線之間的樹(shù)狀索引第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第15頁(yè)。樹(shù)狀索引編碼法示例形成的文件記錄第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第16頁(yè)。索引式

線與多邊形之間的樹(shù)狀索引

點(diǎn)與多邊形之間的樹(shù)狀索引

第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第17頁(yè)。

樹(shù)狀索引編碼消除了相鄰多邊形邊界的數(shù)據(jù)冗余和不一致的問(wèn)題，在簡(jiǎn)化過(guò)于復(fù)雜的邊界線或合并相鄰多邊形時(shí)可不必改造索引表，鄰域信息和島狀信息可以通過(guò)對(duì)多邊形文件的線索引處理得到，但是比較繁瑣，因而給相鄰函數(shù)運(yùn)算，消除無(wú)用邊，處理島狀信息以及檢查拓?fù)潢P(guān)系帶來(lái)一定的困難，而且兩個(gè)編碼表都需要以人工方式建立，工作量大且容易出錯(cuò)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第18頁(yè)。2.雙重獨(dú)立編碼結(jié)構(gòu)

美國(guó)人口調(diào)查局于1980年建立的雙重獨(dú)立地圖編碼系統(tǒng)。簡(jiǎn)稱(chēng)DIME(DualIndependentMapEncoding)，這種結(jié)構(gòu)最適合于城市地理信息系統(tǒng)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第19頁(yè)。

線文件是雙重獨(dú)立編碼結(jié)構(gòu)的基本對(duì)象。線文件由線標(biāo)識(shí)碼、起始節(jié)點(diǎn)、終止節(jié)點(diǎn)、左多邊形和右多邊形組成；節(jié)點(diǎn)文件由節(jié)點(diǎn)的標(biāo)識(shí)碼、節(jié)點(diǎn)坐標(biāo)及與該節(jié)點(diǎn)連接的線的標(biāo)識(shí)碼等；多邊形文件由多邊形標(biāo)識(shí)碼、組成該多邊形的線標(biāo)識(shí)碼組成。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第20頁(yè)。C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7線號(hào)起結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形C1N1N2P2P1C2N3N2P1P4C3N1N3P1?C4N1N4?P2C5N2N5P2P4C6N4N5P3P2第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第21頁(yè)。多邊形：多邊形由一系列的相互連結(jié)的線組成，并通過(guò)其內(nèi)部的唯一標(biāo)識(shí)點(diǎn)來(lái)標(biāo)識(shí)。標(biāo)識(shí)點(diǎn)的標(biāo)識(shí)碼和該多邊形屬性表中的標(biāo)識(shí)碼相一致，由此建立的多邊形空間信息和屬性信息的關(guān)系。多邊形線IDP1C1,C2,C3P2C1,C5,C4P3C6,C7,C8P4C5,C7,C10,C2….C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7面拓?fù)涞谒恼驴臻g數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第22頁(yè)。節(jié)點(diǎn)坐標(biāo)線N1X1,y1C1,C4,C3N2X2,y2C1,C5,C2N3X3,y3C2,C3,C10N4X4,y4C4,C6,C8….C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7點(diǎn)拓?fù)涞谒恼驴臻g數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第23頁(yè)。補(bǔ)充：基于雙重獨(dú)立編碼的拓?fù)錂z查從線文件中，找出與當(dāng)前編輯的多邊形相關(guān)的所有記錄。如對(duì)上例中的P1進(jìn)行檢查，先在線文件中找出與p1有關(guān)的所有記錄：線號(hào)起結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形C1N1N2P2P1C2N3N2P1P4C3N1N3P1?C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第24頁(yè)。補(bǔ)充：基于雙重獨(dú)立編碼的拓?fù)錂z查2.如果P1在左（右）多邊形的位置，將之與處在右（左）多邊形處位置的多邊形號(hào)相交換，同時(shí)也將該記錄的節(jié)點(diǎn)號(hào)位置相應(yīng)的交換；反之，順序不變。線號(hào)起結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形C1N1N2P2P1C2N2N3P4P1C3N3N1?P1C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第25頁(yè)。補(bǔ)充：基于雙重獨(dú)立編碼的拓?fù)錂z查從經(jīng)過(guò)代碼位置轉(zhuǎn)換的記錄中，任取一個(gè)起始節(jié)點(diǎn)作為起點(diǎn)，順序連接各節(jié)點(diǎn)，使得節(jié)點(diǎn)能自行封閉，即

N1N2N3N1。如果不能自動(dòng)封閉，則說(shuō)明出現(xiàn)記錄缺損或多余，線文件有錯(cuò)誤。線號(hào)起結(jié)點(diǎn)終結(jié)點(diǎn)左多邊形右多邊形C1N1N2P2P1C2N2N3P4P1C3N3N1?P1C4N4C8C6P3C7N6C10N3C3N1P1C2N2C1P2C5N5P4P5C9N7第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第26頁(yè)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第27頁(yè)。3.鏈?zhǔn)诫p重獨(dú)立編碼結(jié)構(gòu)

鏈?zhǔn)诫p重獨(dú)立編碼是DIME數(shù)據(jù)結(jié)構(gòu)的一種改進(jìn)。在DIME中，一條邊只能用直線兩端點(diǎn)的序號(hào)及相鄰多邊形表示，而在鏈狀數(shù)據(jù)結(jié)構(gòu)中，將若干條直線段合為一個(gè)弧段（或鏈段），每個(gè)弧段可以有許多中間點(diǎn)。ARCGIS中的Coverage數(shù)據(jù)模型就是采用鏈?zhǔn)诫p重獨(dú)立編碼結(jié)構(gòu)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第28頁(yè)。

拓?fù)浣Y(jié)構(gòu)的特點(diǎn)是:

除結(jié)點(diǎn)外，每個(gè)空間對(duì)象都是由更基本的對(duì)象組成的。只有點(diǎn)的坐標(biāo)是被實(shí)際存儲(chǔ)的，其他復(fù)雜空間對(duì)象的坐標(biāo)信息實(shí)際上是邏輯構(gòu)成的。任一復(fù)雜對(duì)象能分解為一組結(jié)點(diǎn)及其拓?fù)潢P(guān)系的定義。這樣，一個(gè)圖層中存儲(chǔ)的全部坐標(biāo)信息就是結(jié)點(diǎn)的坐標(biāo)，建立其他對(duì)象只是建立對(duì)這些坐標(biāo)的引用。雖然建立拓?fù)浣Y(jié)構(gòu)需要額外的存儲(chǔ)數(shù)據(jù)，但對(duì)坐標(biāo)數(shù)據(jù)的存儲(chǔ)卻沒(méi)有數(shù)據(jù)冗余的問(wèn)題。拓?fù)浣Y(jié)構(gòu)編碼是某些空間分析的基礎(chǔ)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第29頁(yè)。小結(jié)

矢量數(shù)據(jù)結(jié)構(gòu)特點(diǎn)：定位明顯，屬性隱含。其定位是根據(jù)坐標(biāo)直接存儲(chǔ)的，無(wú)需任何推算；屬性則一般存于文件頭或數(shù)據(jù)結(jié)構(gòu)中某些特定的位置上。這種特點(diǎn)使得矢量數(shù)據(jù)結(jié)構(gòu)在圖形運(yùn)算的算法總體上比柵格數(shù)據(jù)結(jié)構(gòu)復(fù)雜的多，在疊加運(yùn)算、鄰域搜索等操作時(shí)比較困難，有些甚至難以實(shí)現(xiàn)，但其也有便利和獨(dú)到之處，在計(jì)算長(zhǎng)度、面積、形狀和圖形編輯、幾何變換操作中，矢量結(jié)構(gòu)有很高的效率和精度。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第30頁(yè)。4.2柵格數(shù)據(jù)結(jié)構(gòu)

柵格結(jié)構(gòu)是最簡(jiǎn)單最直接的空間數(shù)據(jù)結(jié)構(gòu)，是指將地球表面劃分為大小均勻緊密相鄰的網(wǎng)格陣列，每個(gè)網(wǎng)格作為一個(gè)象元或象素由行、列定義，并包含一個(gè)代碼表示該象素的屬性類(lèi)型或量值，或僅僅包括指向其屬性記錄的指針。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第31頁(yè)。柵格數(shù)據(jù)編碼方法分為兩大類(lèi)：直接?xùn)鸥窬幋a（完全柵格數(shù)據(jù)結(jié)構(gòu)）壓縮編碼方法（壓縮柵格數(shù)據(jù)結(jié)構(gòu)）鏈碼

游程長(zhǎng)度編碼

塊碼

四叉樹(shù)

二維行程編碼第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第32頁(yè)。4.2.1直接?xùn)鸥窬幋a直接編碼就是將柵格數(shù)據(jù)看作一個(gè)數(shù)據(jù)矩陣，逐行（或逐列）逐個(gè)記錄代碼，可以每行都從左到右逐個(gè)象元進(jìn)行記錄，也可以奇數(shù)行地從左到右而偶數(shù)行地從右向左記錄，為了特定目的還可采用其他特殊的順序第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第33頁(yè)。一些常用的柵格排列順序第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第34頁(yè)。4.2.2壓縮編碼方式

壓縮編碼的目的就是用盡可能少的數(shù)據(jù)量記錄盡可能多的信息，其類(lèi)型分為信息無(wú)損編碼:編碼過(guò)程中沒(méi)有任何信息損失，通過(guò)解碼操作可以完全恢復(fù)原來(lái)的信息 信息有損編碼:為了提高編碼效率，最大限度地壓縮數(shù)據(jù)，在壓縮過(guò)程中損失一部分相對(duì)不太重要的信息，解碼時(shí)這部分難以恢復(fù)

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

另一種游程長(zhǎng)度編碼方案就是逐個(gè)記錄各行（或列）代碼發(fā)生變化的位置和相應(yīng)代碼

第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第41頁(yè)。游程長(zhǎng)度編碼示例按第一種編碼方法（左上角坐標(biāo)，沿行方向），此數(shù)據(jù)游程長(zhǎng)度編碼：（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個(gè)整數(shù)表達(dá)了原始數(shù)據(jù)中的64個(gè)柵格。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第42頁(yè)。游程長(zhǎng)度編碼示例（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ù)游程長(zhǎng)度編碼（左上角坐標(biāo)，沿列方向）：第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第43頁(yè)。游程編碼能否壓縮數(shù)據(jù)量，主要取決于柵格數(shù)據(jù)的性質(zhì)，通?？梢酝ㄟ^(guò)事先測(cè)試，估計(jì)數(shù)據(jù)冗余度Re：

Re=1-Q/mn

式中：Q表示相鄰屬性值變化次數(shù)的累加和

m表示行數(shù)

n表示列數(shù)

當(dāng)Re的值大于1/5時(shí)，表示柵格數(shù)據(jù)的壓縮可取的明顯的效果第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第44頁(yè)。其壓縮效果可以由壓縮比來(lái)表征：

S=m×n/K

式中：K為游程總數(shù)

m表示行數(shù)

n表示列數(shù)

壓縮比越大，表示壓縮效果越好第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第45頁(yè)。游程長(zhǎng)度編碼優(yōu)缺點(diǎn)優(yōu)點(diǎn)壓縮效率較高，且易于進(jìn)行檢索，疊加合并等操作，運(yùn)算簡(jiǎn)單，適用于機(jī)器存儲(chǔ)容量小，數(shù)據(jù)需大量壓縮，而又要避免復(fù)雜的編碼解碼運(yùn)算增加處理和操作時(shí)間的情況

缺點(diǎn)對(duì)于圖斑破碎，屬性和邊界多變的數(shù)據(jù)壓縮效率較低，甚至壓縮后的數(shù)據(jù)量比原始數(shù)據(jù)還大。

第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第46頁(yè)。塊碼（ChainCodes） 塊碼是游程長(zhǎng)度編碼擴(kuò)展到二維的情況，采用方形區(qū)域作為記錄單元，每個(gè)記錄單元包括相鄰的若干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置（行、列號(hào)）和半徑，再加上記錄單位的代碼組成。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第47頁(yè)。塊碼編碼示例其塊碼編碼為：(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)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第48頁(yè)。四叉樹(shù)編碼 四叉樹(shù)編碼將整個(gè)圖像區(qū)逐步分解為一系列僅包含單一類(lèi)型的方形區(qū)域，最小的方形區(qū)域?yàn)橐粋€(gè)柵格象元。

第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第49頁(yè)。四叉樹(shù)編碼

其基本分割方法是將一幅柵格地圖或圖像等分為四部分。逐塊檢查其柵格屬性值(或灰度)。如果某個(gè)子區(qū)的所有柵格值都具有相同的值。則這個(gè)子區(qū)就不再繼續(xù)分割，否則還要把這個(gè)子區(qū)再分割成四個(gè)子區(qū)。這樣依次地分割，直到每個(gè)子塊都只含有相同的屬性值或灰度為止。 第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第50頁(yè)。四叉樹(shù)編碼示例

第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第51頁(yè)。四叉樹(shù)編碼要求

采用四叉樹(shù)編碼時(shí)，為了保證四叉樹(shù)分解能不斷地進(jìn)行下去，要求圖像必須為2n×2n的柵格陣列，對(duì)于非標(biāo)準(zhǔn)尺寸的圖像需首先通過(guò)增加背景的方法將圖像擴(kuò)充為2n×2n的圖像。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第52頁(yè)。

生成四叉樹(shù)主要有兩種方法，即自上而下（top-down）和自下而上（bottton-up）。由上而下的方法運(yùn)算量大，耗時(shí)較長(zhǎng)。因而實(shí)踐中可以采用從下而上的方法建立四叉樹(shù)編碼。對(duì)柵格數(shù)據(jù)按Morton碼的順序進(jìn)行檢測(cè)：如果每相鄰四個(gè)柵格值相同則進(jìn)行合并，逐次往上遞歸合并，直到符合四叉樹(shù)的原則為止。這種方法重復(fù)計(jì)算較少，運(yùn)算速度較快。

四叉樹(shù)的生成第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第53頁(yè)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第54頁(yè)。四叉樹(shù)結(jié)構(gòu)的編碼方式四叉樹(shù)結(jié)構(gòu)按其編碼的方法不同分為常規(guī)四叉樹(shù)和線性四叉樹(shù)：常規(guī)四叉樹(shù)：除了記錄葉結(jié)點(diǎn)之外，還要記錄中間結(jié)點(diǎn)。結(jié)點(diǎn)之間借助指針聯(lián)系，每個(gè)結(jié)點(diǎn)需要用六個(gè)量表達(dá)：四個(gè)葉結(jié)點(diǎn)指針，一個(gè)父結(jié)點(diǎn)指針和一個(gè)結(jié)點(diǎn)的屬性或灰度值。這些指針不僅增加了數(shù)據(jù)貯存量，而且增加了操作的復(fù)雜性。常規(guī)四叉樹(shù)主要在數(shù)據(jù)索引和圖幅索引等方面應(yīng)用。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第55頁(yè)。四叉樹(shù)結(jié)構(gòu)的編碼方式線性四叉樹(shù)：

只存貯最后葉結(jié)點(diǎn)的信息。包括葉結(jié)點(diǎn)的位置（莫頓碼值）、深度和本結(jié)點(diǎn)的屬性或灰度值。所謂深度是指處于四叉樹(shù)的第幾層上。由深度可推知子區(qū)的大小。線性四叉樹(shù)葉結(jié)點(diǎn)的編號(hào)需要遵循一定的規(guī)則，這種編號(hào)稱(chēng)為地址碼，它隱含了葉結(jié)點(diǎn)的位置和深度信息。最常用的地址碼是二進(jìn)制或十進(jìn)制的Morton碼。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第56頁(yè)。美國(guó)馬里蘭大學(xué)地理信息系統(tǒng)中采用的編碼方式：

該方法記錄了葉子結(jié)點(diǎn)的地址和值，值就是子區(qū)域的代碼，而地址碼包括兩個(gè)部分，由32位來(lái)表示（二進(jìn)制），最右邊4位記錄該葉子結(jié)點(diǎn)的深度，即處于四叉樹(shù)的第幾層上，有了深度即可推知子區(qū)域的大??；從右邊第5位開(kāi)始2n個(gè)字節(jié)記錄葉子結(jié)點(diǎn)的路徑，用以描述葉子結(jié)點(diǎn)的位置，0，1，2，3分別表示SW,SE,NW,NE；其余各位用0補(bǔ)齊。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第57頁(yè)。上圖空白處葉子結(jié)點(diǎn)5，深度為3；路徑為3，0，0；用馬里蘭大學(xué)的編碼方式可以記為：0…….0（22位）；110000（6位）；0011（四位）第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第58頁(yè)。柵格數(shù)據(jù)編碼練習(xí)第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第59頁(yè)。二維行程編碼

在生成線性四叉樹(shù)之后，仍然存在前后葉節(jié)點(diǎn)的值相同的情況，因而可以進(jìn)一步壓縮數(shù)據(jù)，將前后值相同的葉節(jié)點(diǎn)合并，行程新的線性列表。（見(jiàn)P101圖）第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第60頁(yè)。柵格數(shù)據(jù)壓縮存儲(chǔ)的編碼方法AAAAARAAARAAARAARAAAAAAAAAGGAAGGGGGGGAGGGAGGAAAAAARAAAARAAARRAAA143258761234567801234567起點(diǎn)行列號(hào)，單位矢量R:(1,5),3,2,2,3,3,2,3鏈?zhǔn)骄幋a游程長(zhǎng)度編碼逐行編碼數(shù)據(jù)結(jié)構(gòu):行號(hào),屬性,重復(fù)次數(shù)1,A,4,R,1,A,4塊狀編碼正方形區(qū)域?yàn)橛涗泦卧獢?shù)據(jù)結(jié)構(gòu):初始位置,半徑,屬性(1,1,3,A),(1,4,1,A),(1,5,1,R),(1,6,2,A),…NESWNWSEGGGGAGGAAGAAA四叉樹(shù)編碼第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第61頁(yè)。常見(jiàn)柵格壓縮編碼方法總結(jié)：鏈碼的壓縮效率較高，已經(jīng)近矢量結(jié)構(gòu)，對(duì)邊界的運(yùn)算比較方便，但不具有區(qū)域的性質(zhì)，區(qū)域空間分析運(yùn)算困難。游程長(zhǎng)度編碼既可以在很大程度上壓縮數(shù)據(jù)，又最大限度地保留了原始柵格結(jié)構(gòu)，編碼解碼十分容易。但對(duì)破碎數(shù)據(jù)處理效果不好。塊碼和四叉樹(shù)編碼具有區(qū)域性質(zhì)，又具有可變的分辨率，有較高的壓縮效率，但運(yùn)算效率是其瓶頸。其中四叉樹(shù)編碼可以直接進(jìn)行大量圖形圖像運(yùn)算，效率較高，是很有前途的方法。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第62頁(yè)。其他壓縮編碼方式

還有很多編碼方法，如傅立葉變換、小波變換、余弦變換等，常常用于遙感原始數(shù)據(jù)的壓縮。由于它們多數(shù)是有損壓縮，一般不用于需要進(jìn)行分析的柵格數(shù)據(jù)。在四叉樹(shù)基礎(chǔ)上發(fā)展而來(lái)的八叉樹(shù)目前也是研究熱點(diǎn)之一。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第63頁(yè)。小結(jié)

柵格數(shù)據(jù)結(jié)構(gòu)屬性明顯，定位隱含：屬性明顯數(shù)據(jù)中直接記錄了數(shù)據(jù)屬性或指向數(shù)據(jù)屬性的指針，因而我們可以直接得到地物的屬性代碼定位隱含所在位置則根據(jù)行列號(hào)轉(zhuǎn)換為相應(yīng)的坐標(biāo)，也就是說(shuō)定位是根據(jù)數(shù)據(jù)在數(shù)據(jù)集中的位置得到的。柵格結(jié)構(gòu)是按一定的規(guī)則排列的，所表示的實(shí)體的位置很容易隱含在格網(wǎng)文件的存儲(chǔ)結(jié)構(gòu)中第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第64頁(yè)。柵格模型矢量模型優(yōu)點(diǎn)：（1）數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單；（2）空間數(shù)據(jù)的疊置和組合十分容易方便；（3）各類(lèi)空間分析都很易于進(jìn)行；（4）數(shù)學(xué)模擬方便；（5）技術(shù)開(kāi)發(fā)費(fèi)用低。優(yōu)點(diǎn)：（1）表示地理數(shù)據(jù)的精度較高；（2）嚴(yán)密的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)量?。唬?）用網(wǎng)絡(luò)連接法能完整地描述拓?fù)潢P(guān)系；（4）圖形輸出精確美觀；（5）圖形數(shù)據(jù)和屬性數(shù)據(jù)的恢復(fù)、更新、綜合都能實(shí)現(xiàn)。缺點(diǎn)：（1）圖形數(shù)據(jù)量大；（2）用大像元減少數(shù)據(jù)量時(shí)，可識(shí)別的現(xiàn)象結(jié)構(gòu)將損失大量信息；（3）地圖輸出不精美；（4）難以建立網(wǎng)絡(luò)連接關(guān)系；（5）投影變換花的時(shí)間多。缺點(diǎn)：（1）數(shù)據(jù)結(jié)構(gòu)復(fù)雜；（2）矢量多邊形地圖或多邊形網(wǎng)很難用疊置方法與柵格圖進(jìn)行組合；（3）顯示和繪圖費(fèi)用高，特別是高質(zhì)量繪圖、彩色繪圖和暈線圖等；（4）數(shù)學(xué)模擬比較困難；（5）技術(shù)復(fù)雜，多邊形內(nèi)的空間分析不容易實(shí)現(xiàn)?！?.3矢量數(shù)據(jù)結(jié)構(gòu)與柵格數(shù)據(jù)結(jié)構(gòu)比較矢量數(shù)據(jù)模型與柵格數(shù)據(jù)模型比較第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第65頁(yè)。從應(yīng)用領(lǐng)域來(lái)看——柵格結(jié)構(gòu)和矢量結(jié)構(gòu)都有一定的局限性。一般來(lái)說(shuō)，大范圍小比例尺的自然資源、環(huán)境、農(nóng)業(yè)、林業(yè)、地質(zhì)等區(qū)域問(wèn)題的研究，城市總體規(guī)劃階段的戰(zhàn)略性布局研究等使用柵格模型比較合適；城市分區(qū)或詳細(xì)規(guī)劃、土地管理、公共事業(yè)管理等方面應(yīng)用矢量模型比較合適。從數(shù)據(jù)來(lái)源來(lái)看——對(duì)于一個(gè)與遙感相結(jié)合的地理信息系統(tǒng)來(lái)說(shuō)，柵格結(jié)構(gòu)是必不可少的，因?yàn)檫b感影像是以像元為單位的，可以直接將原始數(shù)據(jù)或經(jīng)處理的影像數(shù)據(jù)納入柵格結(jié)構(gòu)的地理信息系統(tǒng)；而對(duì)地圖數(shù)字化、拓?fù)錂z測(cè)、矢量繪圖等，矢量數(shù)據(jù)結(jié)構(gòu)又是必不可少的。※矢量數(shù)據(jù)結(jié)構(gòu)與柵格數(shù)據(jù)結(jié)構(gòu)的選擇在GIS建立過(guò)程中，應(yīng)根據(jù)應(yīng)用的目的和應(yīng)用的特點(diǎn)、可能獲取的數(shù)據(jù)精度以及地理信息系統(tǒng)軟件和硬件的配置情況選擇合適的數(shù)據(jù)結(jié)構(gòu)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第66頁(yè)。矢量與柵格一體化（了解）

為了發(fā)揮矢量和柵格數(shù)據(jù)結(jié)構(gòu)各自的特點(diǎn)，在兩種數(shù)據(jù)的基礎(chǔ)上發(fā)展了矢量—柵格一體化數(shù)據(jù)結(jié)構(gòu)（unifieddatastructure),這種空間數(shù)據(jù)結(jié)構(gòu)的思想是通過(guò)同時(shí)記錄多邊形邊界和邊界中間包含的柵格地址，實(shí)現(xiàn)既保持矢量數(shù)據(jù)的特征又具有柵格數(shù)據(jù)的性質(zhì)。

基本思想：為了提高點(diǎn)、線和邊界的表示精度，一般將點(diǎn)所在格網(wǎng)或線、邊界通過(guò)的格網(wǎng)細(xì)分，根據(jù)精度要求可分為按照256×256或16×16將基本格網(wǎng)細(xì)分。基本格網(wǎng)和細(xì)分格網(wǎng)都采用線性四叉數(shù)編碼，采樣點(diǎn)和線目標(biāo)與基本格網(wǎng)的交點(diǎn)用兩個(gè)十進(jìn)制Morton碼表示。一、矢量與柵格一體化的概念第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第67頁(yè)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第68頁(yè)。為了建立矢量與柵格一體化數(shù)據(jù)結(jié)構(gòu)，要對(duì)點(diǎn)、線、面目標(biāo)數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)要求作如下的統(tǒng)一約定:對(duì)點(diǎn)狀目標(biāo)，因?yàn)闆](méi)有形狀和面積，在計(jì)算機(jī)內(nèi)部只需要表示該點(diǎn)的一個(gè)位置數(shù)據(jù)及與結(jié)點(diǎn)關(guān)聯(lián)的弧段信息。對(duì)線狀目標(biāo)，它有形狀，但沒(méi)有面積，在計(jì)算機(jī)內(nèi)部需用一組元子來(lái)填滿整個(gè)路徑，并表示該弧段相關(guān)的拓?fù)湫畔?。?duì)面狀目標(biāo)，它既有形狀，又有面積，在計(jì)算機(jī)內(nèi)部需表示由元子填滿路徑的組邊界和由邊界組成的緊湊空間。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第69頁(yè)。4.4不規(guī)則鑲嵌數(shù)據(jù)結(jié)構(gòu)4.4.1Voronio數(shù)據(jù)結(jié)構(gòu)（見(jiàn)教材106頁(yè)）4.1.2TIN數(shù)據(jù)結(jié)構(gòu)

TIN模型的數(shù)據(jù)存儲(chǔ)方式比柵格數(shù)據(jù)復(fù)雜，它不僅要存儲(chǔ)每個(gè)點(diǎn)的高程，還要存儲(chǔ)其平面坐標(biāo)、節(jié)點(diǎn)連接的拓?fù)潢P(guān)系，三角形及鄰接三角形等關(guān)系。TIN模型在概念上類(lèi)似于多邊形網(wǎng)絡(luò)的矢量拓?fù)浣Y(jié)構(gòu)，對(duì)于每個(gè)三角形、邊和節(jié)點(diǎn)都對(duì)應(yīng)一個(gè)記錄，如下：第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第70頁(yè)。三角形記錄包括三個(gè)指向它三個(gè)邊的記錄的指針；三角形頂點(diǎn)鄰接三角形ⅠabcⅡⅢⅡcdaⅠⅣⅢbecⅠⅤⅣⅣcedⅡⅢⅧⅤebgⅢⅥⅩⅥbhgⅤⅦ……………………第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第71頁(yè)。邊有四個(gè)指針字段，包括兩個(gè)指向相鄰三角形的指針和它的兩個(gè)頂點(diǎn)的記錄的指針；邊頂點(diǎn)相鄰三角形1abⅠ2acⅠⅡ3bcⅠⅢ……………第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第72頁(yè)。每個(gè)節(jié)點(diǎn)包括三個(gè)坐標(biāo)值的字段，分別存儲(chǔ)X,Y,Z坐標(biāo)。頂點(diǎn)xyzabcde第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第73頁(yè)?！?/p>

柵格數(shù)據(jù)模型和TIN數(shù)據(jù)模型的比較對(duì)地理空間的劃分：TIN模型為不規(guī)則三角形；而柵格模型為規(guī)則格網(wǎng)；空間對(duì)象的表示：柵格數(shù)據(jù)模型既可以描述連續(xù)變化的地理現(xiàn)象，又可以表示離散的地理現(xiàn)象（點(diǎn)、線、面），而TIN模型只能表示聯(lián)系變化的地理現(xiàn)象；但TIN能精確地表示曲面類(lèi)型地理現(xiàn)象的形狀以及特殊的地形要素，比如山脊、山峰等，而柵格模型不能精確表示；第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第74頁(yè)。表面模型的精度：柵格使用統(tǒng)一的CELL大小來(lái)表示，在地形平坦的地方，存在大量的數(shù)據(jù)冗余，而TIN具有隨坡度變化而不同的點(diǎn)密度，在坡度變化大的地區(qū)點(diǎn)密度較高；柵格模型適合進(jìn)行空間一致性分析、近鄰分析、離散度分析及表面最低成本分析，TIN模型適合進(jìn)行坡度、坡向、體積計(jì)算和視線分析等第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第75頁(yè)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第76頁(yè)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第77頁(yè)。4.5三維空間數(shù)據(jù)模型4.5.1三維空間的目標(biāo)分類(lèi)4.5.2八叉樹(shù)數(shù)據(jù)結(jié)構(gòu)4.5.3四面體格網(wǎng)第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第78頁(yè)。

在三維空間中，可將空間地物按維數(shù)分成零維（點(diǎn)），一維（線）、二維（面）和三維（體）四大類(lèi)。

零維空間：有點(diǎn)狀地物和用來(lái)表示與弧段的關(guān)聯(lián)關(guān)系的結(jié)點(diǎn)兩類(lèi)目標(biāo)。一維空間：有“拓樸弧段”、“無(wú)拓樸弧段”和線狀地物。其中“拓樸弧段”可以是構(gòu)成多邊形的邊界線也可是構(gòu)成各類(lèi)網(wǎng)線（如水系網(wǎng)、交通網(wǎng)、城市地下管網(wǎng)）的網(wǎng)線段。二維空間：主要有三類(lèi)目標(biāo)，一個(gè)是構(gòu)成面狀地物的拓樸面片；第二個(gè)是像素，用它可組成面狀要素；第三個(gè)是根據(jù)有限的離散數(shù)據(jù)建立數(shù)字表面模型。三維空間，有由若干個(gè)面片或由數(shù)字立體模型表示體狀地物；以及根據(jù)有限的三維空間離散數(shù)據(jù)建成的數(shù)字立體模型。

第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第79頁(yè)。4.5.1八叉樹(shù)數(shù)據(jù)結(jié)構(gòu)

八叉樹(shù)數(shù)據(jù)結(jié)構(gòu)是三維柵格數(shù)據(jù)的壓縮形式，是二維柵格數(shù)據(jù)中的四叉樹(shù)在三維空間的推廣，該數(shù)據(jù)結(jié)構(gòu)是將所要表示的三維空間V按X、Y、Z三個(gè)方向從中間進(jìn)行分割，把V分割成八個(gè)立方體，然后根據(jù)每個(gè)立方體中所含的目標(biāo)來(lái)決定是否對(duì)各立方體繼續(xù)進(jìn)行八等分的劃分，一直劃分到每個(gè)立方體被一個(gè)目標(biāo)所充滿，或沒(méi)有目標(biāo)，或其大小已成為預(yù)先定義的不可再分的體素為止。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第80頁(yè)。三維空間體V及劃分編碼第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第81頁(yè)。三維空間體V中的物體第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第82頁(yè)。八叉樹(shù)數(shù)據(jù)結(jié)構(gòu)舉例第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第83頁(yè)。八叉樹(shù)編碼

八叉樹(shù)結(jié)構(gòu)就是將空間區(qū)域不斷地分解為八個(gè)同樣大小的子區(qū)域(即將一個(gè)六面的立方體再分解為八個(gè)相同大小的小立方體)，同—區(qū)域的屬性相同。八叉樹(shù)主要用來(lái)解決地理信息系統(tǒng)中的三維問(wèn)題。

第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第84頁(yè)。八叉樹(shù)的主要優(yōu)點(diǎn)在于可以非常方便地實(shí)現(xiàn)有廣泛用途的集合運(yùn)算（例如，可以求兩個(gè)物體的并、交、差等運(yùn)算）而這些恰是其它表示方法比較難以處理或者需要耗費(fèi)許多計(jì)算資源的地方。此外，由于這種方法的有序性及分層性，因而對(duì)顯示精度和速度的平衡，隱線和隱面的消除等，帶來(lái)了很大的方便，特別有用。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第85頁(yè)。4.5.2四面體格網(wǎng)四面體格網(wǎng)（TetrahedralNetwork—TEN）是將目標(biāo)空間用緊密排列但不重疊的不規(guī)則四面體形成的格網(wǎng)來(lái)表示，其實(shí)質(zhì)是2DTIN結(jié)構(gòu)在3D空間上的擴(kuò)展。在概念上首先將2DVoronoi格網(wǎng)擴(kuò)展到3D，形成3DVoronoi多面體，然后將TIN結(jié)構(gòu)擴(kuò)展到3D形成四面體格網(wǎng)（見(jiàn)圖示）。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第86頁(yè)。四面體格網(wǎng)表示三維空間物體的例子第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第87頁(yè)。四面體格網(wǎng)表示三維空間物體的例子的數(shù)據(jù)結(jié)構(gòu)第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第88頁(yè)。四面體格網(wǎng)由點(diǎn)、線、面和體四類(lèi)基本元素組合而成。整個(gè)格網(wǎng)的幾何變換可以變?yōu)槊總€(gè)四面體變換后的組合，這一特性便于許多復(fù)雜的空間數(shù)據(jù)分析。同時(shí)，四面體格網(wǎng)既具有體結(jié)構(gòu)的優(yōu)點(diǎn)，如快速幾何變換、快速顯示，又可以看成是一種特殊的邊界表示，具有一些邊界表示的優(yōu)點(diǎn)，如關(guān)系的快速處理。

第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第89頁(yè)。

矢量數(shù)據(jù)結(jié)構(gòu)和柵格數(shù)據(jù)結(jié)構(gòu)的相互轉(zhuǎn)換是地理信息系統(tǒng)的基本功能之一，目前已經(jīng)發(fā)展了許多高效的轉(zhuǎn)換算法。但是從柵格到矢量數(shù)據(jù)的轉(zhuǎn)換，特別是掃描圖像的自動(dòng)識(shí)別，仍然是研究的重點(diǎn)。4.6矢量數(shù)據(jù)結(jié)構(gòu)與柵格數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換（教材P164）第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第90頁(yè)。

對(duì)于點(diǎn)實(shí)體，每個(gè)實(shí)體都僅由一個(gè)坐標(biāo)對(duì)表示，其結(jié)構(gòu)的轉(zhuǎn)換不存在太大的技術(shù)問(wèn)題。在這重點(diǎn)講解一下線實(shí)體和多邊形實(shí)體向柵格格式轉(zhuǎn)換的過(guò)程。如下：4.6.1矢量格式向柵格格式的轉(zhuǎn)換第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第91頁(yè)。線實(shí)體向柵格格式的轉(zhuǎn)換

由于GIS中線實(shí)體是由順次連接一組坐標(biāo)點(diǎn)形成的折線段表達(dá)的，所以，線的柵格化可以分解為對(duì)做成線實(shí)體的折線段的柵格化。對(duì)于線段的柵格化，先使用點(diǎn)柵格化的方法，柵格化線段的兩個(gè)端點(diǎn)，然后再柵格化線段的中間部分。而對(duì)于線段中間的部分的柵格化，需要分兩種情況來(lái)處理:

第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第92頁(yè)。

設(shè)線段兩端點(diǎn)的坐標(biāo)分別為(x1,y1)和(x2,y2),柵格化后所隊(duì)形的行列號(hào)分別為（I1,J1)(I2,J2).則行差為△I=︱I1-I2︱，列差為△J=︱J1-J2︱。分兩種情況處理：一是列差大于行差△J>△I的情況，二是行差大于列差△I

>△J的情況，運(yùn)用掃描線算法實(shí)現(xiàn)。當(dāng)△J>△I時(shí)，平行于y軸做每一列柵格的中心線，稱(chēng)為掃描線。求每一條掃描線與線段的交點(diǎn)，按點(diǎn)柵格化的方法將交點(diǎn)轉(zhuǎn)換為柵格坐標(biāo)。當(dāng)△I

>△J時(shí)，同理。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第93頁(yè)?！鱆>△I△I>△J第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第94頁(yè)。多邊形矢量格式向柵格格式的轉(zhuǎn)換

內(nèi)部點(diǎn)擴(kuò)散算法射線算法和掃描算法邊界代數(shù)算法第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第95頁(yè)。1內(nèi)部點(diǎn)擴(kuò)散法每個(gè)面域多邊形中選擇一個(gè)內(nèi)部點(diǎn)（擴(kuò)散種子）；從種子點(diǎn)開(kāi)始向8個(gè)鄰域柵格擴(kuò)散，分別判斷8個(gè)柵格是否在多邊形的邊界上，有兩種結(jié)果，一是在邊界上，則這個(gè)柵格不再作為種子；二是不再邊界上，這個(gè)柵格將作為新的種子新的種子與原有種子一起繼續(xù)參與擴(kuò)撒運(yùn)算重復(fù)（2）（3），直到所有種子點(diǎn)填滿該多邊形為止。

擴(kuò)散算法程序設(shè)計(jì)比較復(fù)雜，需要在柵格陣列中進(jìn)行搜索，占用內(nèi)存很大。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第96頁(yè)。2射線算法射線算法可逐點(diǎn)判別數(shù)據(jù)柵格點(diǎn)在某多邊形之外或在多邊形內(nèi)，由待判點(diǎn)向圖外某點(diǎn)引射線，判斷該射線與某多邊形所有邊界相交的總次數(shù)，如相交偶數(shù)次，則待判點(diǎn)在該多邊形的外部，如為奇數(shù)次，則待判點(diǎn)在該多邊形內(nèi)部。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第97頁(yè)。射線算法要計(jì)算與多邊形交點(diǎn)，因此運(yùn)算量大。另一個(gè)比較麻煩的問(wèn)題是射線與多邊形相交時(shí)有些特殊情況如相切、重合等，會(huì)影響交點(diǎn)的個(gè)數(shù)，必須予以排除，由此造成算法的不完善，并增加了編程的復(fù)雜性。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第98頁(yè)。3掃描算法掃描算法是射線算法的改進(jìn)，通常情況下，沿柵格陣列的行方向掃描，在每?jī)纱斡龅蕉噙呅芜吔琰c(diǎn)的兩個(gè)位置之間的柵格，屬于該多邊形。掃描算法省去了計(jì)算射線與多邊形交點(diǎn)的大量運(yùn)算，大大提高了效率，但一般需要預(yù)留一個(gè)較大的數(shù)組以存放邊界點(diǎn)，而且掃描線與多邊形邊界相交的幾種特殊情況仍然存在，需要加以判別。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第99頁(yè)。4邊界代數(shù)算法邊界代數(shù)多邊形填充算法（BoundaryAlgebraFilling，簡(jiǎn)稱(chēng)BAF），是任伏虎等設(shè)計(jì)并在微機(jī)地理信息系統(tǒng)上實(shí)現(xiàn)的一種基于積分思想的矢量格式向柵格格式轉(zhuǎn)換算法。適合記錄拓?fù)潢P(guān)系的多邊形矢量數(shù)據(jù)轉(zhuǎn)換為柵格數(shù)據(jù)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第100頁(yè)。事實(shí)上，每幅地圖都是由多個(gè)多邊形區(qū)域組成的。如果把不屬于任何多邊形的區(qū)域（包括無(wú)窮遠(yuǎn)點(diǎn)）看成一個(gè)編號(hào)為零的特殊區(qū)域，則每一條邊界弧段都與兩個(gè)不同編號(hào)的多邊形相鄰，按邊界弧段的前進(jìn)方向分別稱(chēng)為左、右多邊形。對(duì)圖3－24所示的3個(gè)多邊形的6條邊，有如表3－5所示的多邊形編號(hào)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第101頁(yè)。表3-5線號(hào)與左右多邊形號(hào)的對(duì)應(yīng)關(guān)系線號(hào)左多邊形右多邊形Ⅰ0n1Ⅱn20Ⅲn3n2Ⅳn1n2Ⅴn30Ⅵn3n1n2n1n3第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第102頁(yè)。邊界代數(shù)算法的基本思想：對(duì)每幅地圖的全部具有左右多邊形編號(hào)的邊界弧段，沿其前進(jìn)的方向逐個(gè)搜索，當(dāng)邊界上行時(shí)，將邊界線位置與左圖框之間的網(wǎng)格點(diǎn)加上一個(gè)值=（左多邊形編號(hào)）-（右多邊形編號(hào)）；當(dāng)邊界線下行時(shí)，將邊界線位置與左圖框的柵格點(diǎn)加上一個(gè)值=（右多邊形編號(hào)）-（左多邊形編號(hào)），而不管邊界線的排列順序。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第103頁(yè)。射線算法單個(gè)多邊形的轉(zhuǎn)換多個(gè)多邊形的轉(zhuǎn)換

第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第104頁(yè)。線號(hào)左多邊形右多邊形Ⅰ0n1Ⅱn20Ⅲn3n2Ⅳn1n2Ⅴn30Ⅵn3n1n2n1n3n2n1n3第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第105頁(yè)。邊界代數(shù)法與其它算法的不同之處在于它不是逐點(diǎn)搜尋判別邊界，而是根據(jù)邊界的拓?fù)湫畔?，通過(guò)簡(jiǎn)單的加減代數(shù)運(yùn)算將拓?fù)湫畔?dòng)態(tài)地賦予各柵格點(diǎn)，實(shí)現(xiàn)了矢量格式到柵格格式的轉(zhuǎn)換。由于不需考慮邊界與搜索軌跡之間的關(guān)系，因此算法簡(jiǎn)單，可靠性好，而且由于僅采用加減代數(shù)運(yùn)算，每條邊界僅計(jì)算一次，免去了公共邊界重復(fù)運(yùn)算，又可不考慮邊界存放的順序，因此運(yùn)算速度快，同時(shí)較少受內(nèi)存容量的限制，特別適用于微機(jī)地理信息系統(tǒng)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第106頁(yè)。

柵格數(shù)據(jù)向矢量數(shù)據(jù)轉(zhuǎn)換的目的有三：①數(shù)據(jù)入庫(kù)；②數(shù)據(jù)壓縮；③矢量制圖；

4.6.2柵格格式向矢量格式的轉(zhuǎn)換第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第107頁(yè)。1）多邊形邊界提?。海ǘ祷?，平滑，細(xì)化）2）邊界線追蹤※3）拓?fù)潢P(guān)系生成4）去除多余點(diǎn)及曲線圓滑

柵格格式向矢量格式的轉(zhuǎn)換的一般需要以下幾個(gè)步驟第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第108頁(yè)。

所謂的二值化，是在一個(gè)設(shè)定的灰度闕值的基礎(chǔ)上，對(duì)掃描獲得的灰度圖像（如256級(jí)灰度）進(jìn)行0或1的簡(jiǎn)化處理，即有無(wú)判斷。算法如下：1）圖像二值化1多邊形邊界提取第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第109頁(yè)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第110頁(yè)。

由于線不光滑以及掃描、攝像系統(tǒng)的分辨率限制，使得一些曲線目標(biāo)帶來(lái)多余的小分支（即毛刺噪聲）；此外，還有空洞和凹陷噪聲（如下圖），就會(huì)造成細(xì)化誤差和失真，這樣最影響最終柵格的跟蹤和矢量化。曲線目標(biāo)越寬，提取骨架和去除輪廓所需的次數(shù)也就越多，因此誤差的影響也越大。2）圖像細(xì)化預(yù)處理二值圖像平滑第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第111頁(yè)。去除毛刺和空洞為了去除毛刺和空洞的影響，可以采用下面兩個(gè)模板進(jìn)行處理。處理過(guò)程如下：按點(diǎn)陣格式掃描圖像上的每一個(gè)像素，只要圖像相應(yīng)區(qū)域與模板（包括模板的90旋轉(zhuǎn)）吻合，則判定為毛刺（或空洞），對(duì)應(yīng)模板中心數(shù)值變給0（空洞模板將模板中心位置值改為1）000010XXXX1X101XXX去除毛刺模板，X為任意值去除空洞模板，X為任意值第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第112頁(yè)。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第113頁(yè)。3）圖像細(xì)化線細(xì)化是處理包含線狀地物二值圖像的一種重要技術(shù)，在地圖掃描處理中，由于地圖上主要信息是不同粗細(xì)和不同形狀的線，必須首先進(jìn)行線細(xì)化，以準(zhǔn)確有效地提取這些線信息，并進(jìn)一步矢量化。線細(xì)化就是不斷去除曲線上不影響連通性的輪廓像素的過(guò)程，對(duì)細(xì)化的一般要求是：保證細(xì)化后曲線的連通性；細(xì)化結(jié)果是原曲線的中心線；保留細(xì)線端點(diǎn)下面介紹幾種典型的細(xì)化方法：第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第114頁(yè)。經(jīng)典的細(xì)化算法對(duì)于二值柵格圖像中每個(gè)像素點(diǎn)P,以及其直接相鄰的8個(gè)像素點(diǎn)，令：N(p)為p的鄰點(diǎn)的數(shù)值的和；圖像像素聯(lián)結(jié)數(shù)T(p)；Pw,PE,PS,PN分別指像素左側(cè)、右側(cè)、下邊、上邊鄰點(diǎn)的數(shù)值第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第115頁(yè)。T(p)=0T(p)=0T(p)=1T(p)=1T(p)=2T(p)=2T(p)=2T(p)=3T(p)=4第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第116頁(yè)。算法步驟如下：對(duì)于柵格圖像中的每一點(diǎn)p做如下操作：第一步：如果將所有被標(biāo)志的柵格點(diǎn)賦值為0，如果沒(méi)有被標(biāo)志的點(diǎn)，則算法結(jié)束第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131頁(yè)，當(dāng)前為第117頁(yè)。第二步：如果將所有被標(biāo)志的柵格點(diǎn)賦值為0，如果沒(méi)有被標(biāo)志的點(diǎn)，則算法結(jié)束轉(zhuǎn)到第一步。第四章空間數(shù)據(jù)結(jié)構(gòu)全文共131