柵格數(shù)據(jù)結(jié)構(gòu)課件

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

3/9/20231西北大學(xué)城市與資源學(xué)系數(shù)據(jù)結(jié)構(gòu)即指數(shù)據(jù)組織的形式，是適合于計(jì)算機(jī)存儲(chǔ)、管理和處理的數(shù)據(jù)邏輯結(jié)構(gòu)。對(duì)空間數(shù)據(jù)則是地理實(shí)體的空間排列方式和相互關(guān)系的抽象描述。在地理系統(tǒng)中描述地理要素和地理現(xiàn)象的空間數(shù)據(jù)，主要包括空間位置、拓樸關(guān)系和屬性三個(gè)方面的內(nèi)容。3/9/20232西北大學(xué)城市與資源學(xué)系空間數(shù)據(jù)結(jié)構(gòu)網(wǎng)格數(shù)據(jù)結(jié)構(gòu)(顯式表示

)矢量數(shù)據(jù)結(jié)構(gòu)(隱式表示

)3/9/20233西北大學(xué)城市與資源學(xué)系顯式描述顯式表示：就是柵格中的一系列像元(點(diǎn))，為使計(jì)算機(jī)認(rèn)識(shí)這些像元描述的是某一物體而不是其它物體。注：“c”不一定用c的形式，而可以用顏色、符號(hào)、數(shù)字、灰度值來顯示。則得到椅子的簡單數(shù)據(jù)結(jié)構(gòu)為：

椅子的屬性——符號(hào)／顏色——像元x3/9/20234西北大學(xué)城市與資源學(xué)系隱式表示隱式表示：由一系列定義了始點(diǎn)和終點(diǎn)的線及某種連接關(guān)系來描述，線的始點(diǎn)和終點(diǎn)坐標(biāo)定義為一條表示椅子形式的矢量，線之間的指示字，告訴計(jì)算機(jī)怎樣把這些矢量連接在一起形成椅子，隱式表示的數(shù)據(jù)為：

椅子的屬性——一系列矢量——連接關(guān)系

3/9/20235西北大學(xué)城市與資源學(xué)系柵格數(shù)據(jù)結(jié)構(gòu)

柵格數(shù)據(jù):柵格數(shù)據(jù)結(jié)構(gòu)實(shí)際就是像元陣列，每個(gè)像元由行列確定它的位置。由于柵格結(jié)構(gòu)是按一定的規(guī)則排列的，所表示的實(shí)體位置很容易隱含在網(wǎng)絡(luò)文件的存儲(chǔ)結(jié)構(gòu)中，且行列坐標(biāo)可以很容易地轉(zhuǎn)為其它坐標(biāo)系下的坐標(biāo)。在網(wǎng)絡(luò)文件中每個(gè)代碼本身明確地代表了實(shí)體的屬性或?qū)傩缘木幋a。

柵格數(shù)據(jù)結(jié)構(gòu)就是像元陣列，每個(gè)像元的行列號(hào)確定位置，用像元值表示空間對(duì)象的類型、等級(jí)等特征。每個(gè)柵格單元只能存在一個(gè)值。（a）三角形（b）菱形（c)六邊形3/9/20236西北大學(xué)城市與資源學(xué)系點(diǎn)線面對(duì)于柵格數(shù)據(jù)結(jié)構(gòu)點(diǎn)：為一個(gè)像元線：在一定方向上連接成串的相鄰像元集合。面：聚集在一起的相鄰像元集合。3/9/20237西北大學(xué)城市與資源學(xué)系柵格數(shù)據(jù)結(jié)構(gòu)：坐標(biāo)系與描述參數(shù)Y：列X：行西南角格網(wǎng)坐標(biāo)（XWS，YWS）格網(wǎng)分辨率3/9/20238西北大學(xué)城市與資源學(xué)系柵格數(shù)據(jù)單元值確定CAB百分比法面積占優(yōu)重要性中心點(diǎn)法A連續(xù)分布地理要素C具有特殊意義的較小地物A分類較細(xì)、地物斑塊較小AB為了逼近原始數(shù)據(jù)精度，除了采用這幾種取值方法外，還可以采用縮小單個(gè)柵格單元的面積，增加?xùn)鸥駟卧倲?shù)的方法3/9/20239西北大學(xué)城市與資源學(xué)系柵格數(shù)據(jù)壓縮存儲(chǔ)的編碼方法AAAAARAAARAAARAARAAAAAAAAAGGAAGGGGGGGAGGGAGGAAAAAARAAAARAAARRAAA143258761234567801234567起點(diǎn)行列號(hào)，單位矢量R:(1,5),3,2,2,3,3,2,3鏈?zhǔn)骄幋a游程長度編碼逐行編碼數(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,5,1,R),(1,6,2,A),…NESWNWSEGGGGAGGAAGAAA四叉樹編碼3/9/202310西北大學(xué)城市與資源學(xué)系柵格矩陣（RasterMatrix)

Raster數(shù)據(jù)是二維表面上地理數(shù)據(jù)的離散量化值，每一層的pixel值組成像元陣列（即二維數(shù)組），其中行、列號(hào)表示它的位置。

例如影像：AAAA

ABBB

AABB

AAAB

在計(jì)算機(jī)內(nèi)是一個(gè)4*4階的矩陣。但在外部設(shè)備上，通常是以左上角開始逐行逐列存貯。如上例存貯順序?yàn)椋篈AAAABBBAABBAAAB

當(dāng)每個(gè)像元都有唯一一個(gè)屬性值時(shí)，一層內(nèi)的編碼就需要m行×n列×3(x,y和屬性編碼值)個(gè)存儲(chǔ)單元。數(shù)字地面模型就屬此種情況。3/9/202311西北大學(xué)城市與資源學(xué)系鏈?zhǔn)骄幋a(ChainCodes)又稱為弗里曼鏈碼(Freeman)或邊界鏈碼?；痉较蚩啥x為：東＝0，東南＝l，南二2，西南＝3，西＝4，西北＝5，北＝6，東北＝7等八個(gè)基本方向。如果再

確定原點(diǎn)為像元(10，1)，則該多邊形邊界按順時(shí)針方向的鏈?zhǔn)骄幋a為：

10，l，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。

3/9/202312西北大學(xué)城市與資源學(xué)系游程長度編碼(Run—LengthCodes)游程長度編碼是按行幀序存儲(chǔ)多邊形內(nèi)的各個(gè)像元的列號(hào)，即在某行上從左至右存儲(chǔ)屬該多邊形的始末像元的列號(hào)。問：對(duì)左圖的進(jìn)行游程長度編碼。3/9/202313西北大學(xué)城市與資源學(xué)系塊式編碼(BlockCodes)塊式編碼是將游程長度編碼擴(kuò)大到二維的情況，把多邊形范圍劃分成由像元組成的正方形，然后對(duì)各個(gè)正方形進(jìn)行編碼。如圖：塊式編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置(行號(hào)，列號(hào))和半徑，再加上記錄單元的代碼組成。根據(jù)這一編碼原則，上述多邊形只需17個(gè)單位正方形。9個(gè)4單位的正方形和1個(gè)16單位的正方形就能完整表示，總共要57個(gè)數(shù)據(jù)，其中27對(duì)坐標(biāo)，3個(gè)塊的半徑。3/9/202314西北大學(xué)城市與資源學(xué)系四叉樹編碼(QuadtreeEncoding)四叉樹編碼又稱為四分樹、四元樹編碼。它是一種更有效地壓編數(shù)據(jù)的方法。它將2n×2n像元陣列連續(xù)進(jìn)行4等分，一直分到正方形的大小正好與象元的大小相等為止（如下圖），而塊狀結(jié)構(gòu)則用四叉樹描述，習(xí)慣上稱為四叉樹編碼。3/9/202315西北大學(xué)城市與資源學(xué)系八叉樹編碼八叉樹結(jié)構(gòu)就是將空間區(qū)域不斷地分解為八個(gè)同樣大小的子區(qū)域(即將一個(gè)六面的立方體再分解為八個(gè)相同大小的小立方體)，同—區(qū)域的屬性相同。八叉樹主要用來解決地理信息系統(tǒng)中的三維問題。

3/9/202316西北大學(xué)城市與資源學(xué)系柵格數(shù)據(jù)組織3/9/202317西北大學(xué)城市與資源學(xué)系柵格數(shù)據(jù)組織柵格數(shù)據(jù)文件像元1X坐標(biāo)Y坐標(biāo)層2屬性值層1屬性值…層n屬性值…像元2像元n柵格數(shù)據(jù)文件層1像元1層2…X,Y,屬性值像元2X,Y,屬性值……像元nX,Y,屬性值層n柵格數(shù)據(jù)文件層1多邊形1層2…屬性值像元1坐標(biāo)…多邊形N像元n坐標(biāo)層n3/9/202318西北大學(xué)城市與資源學(xué)系柵格數(shù)據(jù)結(jié)構(gòu)特點(diǎn)離散的量化柵格值表示空間對(duì)象位置隱含,屬性明顯數(shù)據(jù)結(jié)構(gòu)簡單,易于遙感數(shù)據(jù)結(jié)合,但數(shù)據(jù)量大幾何和屬性偏差面向位置的數(shù)據(jù)結(jié)構(gòu),難以建立空間對(duì)象之間的關(guān)系3/9/202319西北大學(xué)城市與資源學(xué)系abc345abcac距離:7/4(5)面積:7(6)幾何偏差屬性偏差如以像元邊線計(jì)算則為7，以像元為單金大會(huì)則為4。三角形的面積為6個(gè)平方單位，而右圖中則為7個(gè)平方單位，這種誤差隨像元的增大而增加。

3/9/202320西北大學(xué)城市與資源學(xué)系矢量數(shù)據(jù)結(jié)構(gòu)矢量數(shù)據(jù)結(jié)構(gòu)是通過記錄坐標(biāo)的方式，盡可能地將點(diǎn)、線、面地理實(shí)體表現(xiàn)得精確無誤。其坐標(biāo)空間假定為連續(xù)空間，不必象柵格數(shù)據(jù)結(jié)構(gòu)那樣進(jìn)行量化處理。因此矢量數(shù)據(jù)能更精確地定義位置、長度和大小。

除數(shù)學(xué)上的精確坐標(biāo)假設(shè)外，矢量數(shù)據(jù)存儲(chǔ)是以隱式關(guān)系以最小的存儲(chǔ)空間存儲(chǔ)復(fù)雜的數(shù)據(jù)。3/9/202321西北大學(xué)城市與資源學(xué)系矢量數(shù)據(jù)結(jié)構(gòu)編碼的基本內(nèi)容

矢量數(shù)據(jù)結(jié)構(gòu)通過記錄空間對(duì)象的坐標(biāo)及空間關(guān)系來表達(dá)空間對(duì)象的位置。點(diǎn)：空間的一個(gè)坐標(biāo)點(diǎn)；線：多個(gè)點(diǎn)組成的弧段；面：多個(gè)弧段組成的封閉多邊形；3/9/202322西北大學(xué)城市與資源學(xué)系矢量數(shù)據(jù)結(jié)構(gòu)編碼的基本內(nèi)容

標(biāo)識(shí)碼屬性碼空間對(duì)象編碼唯一連接空間和屬性數(shù)據(jù)數(shù)據(jù)庫獨(dú)立編碼點(diǎn):(x,y)線:(x1,y1),(x2,y2),…,(xn,yn)面:(x1,y1

),(x2,y2

),…,(x1,y1

)點(diǎn)位字典點(diǎn):點(diǎn)號(hào)文件線:點(diǎn)號(hào)串面:點(diǎn)號(hào)串點(diǎn)號(hào)XY1112223344………n5566存儲(chǔ)方法3/9/202323西北大學(xué)城市與資源學(xué)系點(diǎn)實(shí)體3/9/202324西北大學(xué)城市與資源學(xué)系線實(shí)體面實(shí)體多邊形矢量編碼，不但要表示位置和屬性，更重要的是能表達(dá)區(qū)域的拓?fù)涮卣?，如形狀、鄰域和層次結(jié)構(gòu)等，以便使這些基本的空間單元可以作為專題圖的資料進(jìn)行顯示和操作。

3/9/202325西北大學(xué)城市與資源學(xué)系簡單的矢量數(shù)據(jù)結(jié)構(gòu)—面條結(jié)構(gòu)（實(shí)體式）只記錄空間對(duì)象的位置坐標(biāo)和屬性信息，不記錄拓?fù)潢P(guān)系。存儲(chǔ)：獨(dú)立存儲(chǔ)：空間對(duì)象位置直接跟隨空間對(duì)象；點(diǎn)位字典：點(diǎn)坐標(biāo)獨(dú)立存儲(chǔ)，線、面由點(diǎn)號(hào)組成特征無拓?fù)潢P(guān)系，主要用于顯示、輸出及一般查詢公共邊重復(fù)存儲(chǔ)，存在數(shù)據(jù)冗余，難以保證數(shù)據(jù)獨(dú)立性和一致性多邊形分解和合并不易進(jìn)行，鄰域處理較復(fù)雜；處理嵌套多邊形比較麻煩適用范圍：制圖及一般查詢，不適合復(fù)雜的空間分析3/9/202326西北大學(xué)城市與資源學(xué)系簡單的矢量數(shù)據(jù)結(jié)構(gòu)—面條結(jié)構(gòu)（實(shí)體式）多邊形

數(shù)據(jù)項(xiàng)

A

(x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5),(x6,y6),(x7,y7),(x8,y8),(x9,y9),(x1,y1)

B

(x1,y1),(x9,y9),(x8,y8),(x17,y17),(x16,y16),(x15,y15),(x14,y14),(x13,y13),(x12,y12),(x11,y11),(x10,y10),(x1,y1)

C

(x24,y24),(x25,y25),(x26,y26),(x27,y27),(x28,y28),(x29,y29),(x30,y30),(x31,y31),(x24,y24) D

(x19,y19),(x20,y20),(x21,y21),(x22,y22),(x23,y23),(x15,y15),(x16,y16),(x19,y19)

E

(x5,y5),(x18,y18),(x19,y19),(x16,y16),(x17,y17),(x8,y8),(x7,y7),(x6,y6),(x5,y5)3/9/202327西北大學(xué)城市與資源學(xué)系索引式線與多邊形之間的樹狀索引

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

3/9/202328西北大學(xué)城市與資源學(xué)系雙重獨(dú)立式DIME(DuallndependentMapEncoding)線號(hào)左多邊形右多邊形起點(diǎn)終點(diǎn)aOA18bOA21cOB32dOB43eOB54fOC65gOC76hOC87iCA89jCB95kCD1210lCD1112mCD1011nBA92這種數(shù)據(jù)結(jié)構(gòu)除了通過線文件生成面文件外，還需要點(diǎn)文件

3/9/202329西北大學(xué)城市與資源學(xué)系鏈狀雙重獨(dú)立式鏈狀雙重獨(dú)立式數(shù)據(jù)結(jié)構(gòu)是DIME數(shù)據(jù)結(jié)構(gòu)的一種改進(jìn)。在DIME中，一條邊只能用直線兩端點(diǎn)的序號(hào)及相鄰的面域來表示，而在鏈狀數(shù)據(jù)結(jié)構(gòu)中，將若干直線段合為一個(gè)弧段（或鏈段），每個(gè)弧段可以有許多中間點(diǎn)。在鏈狀雙重獨(dú)立數(shù)據(jù)結(jié)構(gòu)中，主要有四個(gè)文件：多邊形文件、弧段文件、弧段坐標(biāo)文件、結(jié)點(diǎn)文件。

3/9/202330西北大學(xué)城市與資源學(xué)系弧段文件弧段號(hào) 起始點(diǎn) 終結(jié)點(diǎn) 左多邊形 右多邊形 a 5 1 O Ab 8 5 E Ac 16 8 E Bd 19 5 O Ee 15 19 O Df 15 16 D Bg 1 15 O Bh 8 1 A Bi 16 19 D Ej 31 31 B C 弧段坐標(biāo)文件弧段號(hào) 點(diǎn)號(hào) a 5,4,3,2,1 b 8,7,6,5 c 16,17,8 d 19,18,5 e 15,23,22,21,20,19 f 15,16, g 1,10,11,12,13,14,15 h 8,9,1 i 16,19 j 31,30,29,28,27,26,25,24,31

鏈狀雙重獨(dú)立式多邊形文件多邊形號(hào) 弧段號(hào) 周長面積中心點(diǎn)坐標(biāo) A h,b,a B g,f,c,h,-j C j D e,i,f E e,i,d,b

3/9/202331西北大學(xué)城市與資源學(xué)系矢量數(shù)據(jù)結(jié)構(gòu)的屬性數(shù)據(jù)表達(dá)屬性特征類型類別特征：是什么說明信息：同類目標(biāo)的不同特征屬性特征表達(dá)類別特征：類型編碼說明信息：屬性數(shù)據(jù)結(jié)構(gòu)和表格屬性表的內(nèi)容取決于用戶圖形數(shù)據(jù)和屬性數(shù)據(jù)的連接通過目標(biāo)識(shí)別符或內(nèi)部記錄號(hào)實(shí)現(xiàn)。3/9/202332西北大學(xué)城市與資源學(xué)系矢量數(shù)據(jù)結(jié)構(gòu)的屬性數(shù)據(jù)表達(dá)點(diǎn)狀對(duì)象目標(biāo)標(biāo)識(shí)目標(biāo)標(biāo)識(shí)地物編碼坐標(biāo)關(guān)聯(lián)的線目標(biāo)精度控制點(diǎn)等級(jí)測量單位測量年限線狀對(duì)象目標(biāo)標(biāo)識(shí)目標(biāo)標(biāo)識(shí)地物編碼坐標(biāo)串起點(diǎn)、終點(diǎn)、左面、右面路面材料等級(jí)修建時(shí)間寬度管養(yǎng)單位…………面狀對(duì)象目標(biāo)標(biāo)識(shí)目標(biāo)標(biāo)識(shí)地物編碼邊界目標(biāo)號(hào)建筑日期所有者建筑面積建筑單位結(jié)構(gòu)……空間對(duì)象地物編碼地物名稱制圖顏色幾何類型制圖符號(hào)編碼屬性表明地物類型特征與制圖屬性3/9/202333西北大學(xué)城市與資源學(xué)系矢量數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)用離散的點(diǎn)描述空間對(duì)象與特征，定位明顯，屬性隱含用拓?fù)潢P(guān)系描述空間對(duì)象之間的關(guān)系面向目標(biāo)操作，精度高，數(shù)據(jù)冗余度小與遙感等圖象數(shù)據(jù)難以結(jié)合輸出圖形質(zhì)量號(hào)，精度高3/9/202334西北大學(xué)城市與資源學(xué)系第三節(jié)兩種數(shù)據(jù)結(jié)構(gòu)的比較與轉(zhuǎn)換矢量數(shù)據(jù)優(yōu)點(diǎn)：表示地理數(shù)據(jù)的精度較高嚴(yán)密的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)量小完整的描述空間關(guān)系圖形輸出精確美觀圖形數(shù)據(jù)和屬性數(shù)據(jù)的恢復(fù)、更新、綜合都能實(shí)現(xiàn)面向目標(biāo)，不僅能表達(dá)屬性，而且能方便的記錄每個(gè)目標(biāo)的具體屬性信息缺點(diǎn)：數(shù)據(jù)結(jié)構(gòu)復(fù)雜矢量疊置較為復(fù)雜數(shù)學(xué)模擬比較困難技術(shù)復(fù)雜，特別是軟硬件柵格數(shù)據(jù)優(yōu)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)簡單空間數(shù)據(jù)的疊置和組合方便各類空間分析很易于進(jìn)行數(shù)學(xué)模擬方便缺點(diǎn)：圖形數(shù)據(jù)量大用大像元減少數(shù)據(jù)量時(shí)，精度和信息量受損地圖輸出不美觀難以建立網(wǎng)絡(luò)連接關(guān)系投影變換比較費(fèi)時(shí)3/9/202335西北大學(xué)城市與資源學(xué)系數(shù)據(jù)結(jié)構(gòu)選擇原則要素還是位置？可獲取的數(shù)據(jù)定位要素的必要精度需要什么類型的要素需要什么類型的拓?fù)潢P(guān)聯(lián)所需空間分析類型生產(chǎn)地圖類型3/9/202336西北大學(xué)城市與資源學(xué)系矢量數(shù)據(jù)向柵格數(shù)據(jù)轉(zhuǎn)換點(diǎn)的變換

3/9/202337西北大學(xué)城市與資源學(xué)系矢量數(shù)據(jù)向柵格數(shù)據(jù)轉(zhuǎn)換矢量線段的變換3/9/202338西北大學(xué)城市與資源學(xué)系矢量數(shù)據(jù)向柵格數(shù)據(jù)轉(zhuǎn)換多邊形數(shù)據(jù)的轉(zhuǎn)換(邊界代數(shù)算法、內(nèi)部點(diǎn)擴(kuò)散法、射線算法）3/9/202339西北大學(xué)城市與資源學(xué)系矢