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

第二章空間數(shù)據(jù)結(jié)構(gòu)第一頁，共五十四頁，編輯于2023年，星期四2.1空間數(shù)據(jù)模型的類型在GIS中與空間信息有關(guān)的空間數(shù)據(jù)模型主要有兩個(gè)基于場(chǎng)(field-based)的空間模型把地理空間的事物和現(xiàn)象作為連續(xù)的變量或體來看待，表示了在二維或者三維空間中，空間實(shí)體的屬性信息被看作是連續(xù)變化的數(shù)據(jù)。AcollectionofspatialdistributionsContinuousdata.Examplesaltitude,rainfall,temperature,cropyield.

第二頁，共五十四頁，編輯于2023年，星期四有毒氣體擴(kuò)散分析第三頁，共五十四頁，編輯于2023年，星期四

基于對(duì)象(object-based)的模型強(qiáng)調(diào)了離散對(duì)象,將研究的整個(gè)地理空間看成一個(gè)空間域，地理實(shí)體和現(xiàn)象作為獨(dú)立的對(duì)象分布在該空間域中，根據(jù)它們的邊界線以及它們的組成或者與它們相關(guān)的其它對(duì)象，可以詳細(xì)地描述離散對(duì)象。任何現(xiàn)象，無論大小，都可以被確定為一個(gè)對(duì)象(Object)，且假設(shè)它可以從概念上與其鄰域現(xiàn)象相分離。在歐氏（Euclidean）空間中主要有點(diǎn)對(duì)象、線對(duì)象、多邊形對(duì)象和體。composedofidentifiableentitiesDiscretedata.Examplesroads,rivers,landparcels,islandboreholes第四頁，共五十四頁，編輯于2023年，星期四地理信息系統(tǒng)兩種數(shù)據(jù)類型是通過兩種空間數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)：柵格（raster）and矢量（vector）。柵格數(shù)據(jù)模型是典型的基于域的模型。矢量數(shù)據(jù)模型是典型的基于對(duì)象的空間數(shù)據(jù)模型。cells(grid)pixels(image)Field-baseddataObject-baseddataRastermodelVectormodellllllpointslinespolygons第五頁，共五十四頁，編輯于2023年，星期四2.2柵格數(shù)據(jù)數(shù)據(jù)結(jié)構(gòu)將工作區(qū)域的平面表象按一定分解力作行和列的規(guī)則劃分，形成許多格網(wǎng)，每個(gè)網(wǎng)格單元稱為象素(pixel)。根據(jù)所表示實(shí)體的表象信息差異，各象元可用不同的“灰度值”來表示。若每個(gè)象元規(guī)定N比特，則其灰度值范圍可在0到2N—1之間；把白～灰色～黑的連續(xù)變化量化成8比特（bit），其灰度值范圍就允許在0～255之間；若每個(gè)象元只規(guī)定1比特，則灰度值僅為0和1，這就是所謂二值圖像。點(diǎn)實(shí)體在柵格數(shù)據(jù)中表示為一個(gè)像元；線實(shí)體則表示為在一定方向上連接成串的相鄰像元集合；面實(shí)體由聚集在一起的相鄰像元集合表示。

第六頁，共五十四頁，編輯于2023年，星期四arealinepointployon第七頁，共五十四頁，編輯于2023年，星期四柵格數(shù)據(jù)結(jié)構(gòu)實(shí)際上就是象元陣列，即象元按矩陣形式的集合(二維數(shù)組），柵格中的每個(gè)象元是柵格數(shù)據(jù)中最基本的信息存儲(chǔ)單元，其坐標(biāo)位置可以用行號(hào)和列號(hào)確定。右圖在計(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ǔ)單元。Row#(Y-coord)regionscellsAAAAABBBAABBAAABColumn#(X-coord)第八頁，共五十四頁，編輯于2023年，星期四PunctualLinealAreal

Surficial0-d1-d2-d3-d+12014012331122112311333332RealworldVeryFinegridMediumgridCoarsegrid分辯率（resolution）Resolutionisdependentonthegridcellsize..Changingtheresolutionaffectsclassification,area,perimeter,accuracy,etc...

第九頁，共五十四頁，編輯于2023年，星期四中心歸屬法：每個(gè)柵格單元的值以網(wǎng)格中心點(diǎn)對(duì)應(yīng)的面域?qū)傩灾荡_定。面積占優(yōu)法：每個(gè)柵格單元的值以在該網(wǎng)格單元中占據(jù)最大面積的屬性長度占優(yōu)法：每個(gè)柵格單元的值以網(wǎng)格中線的大部分長度所對(duì)應(yīng)的面域的屬性值來確定。重要性法：根據(jù)柵格內(nèi)不同地物的重要性程度，選取特別重要的空間實(shí)體決定對(duì)應(yīng)的柵格單元值.2.2.1柵格數(shù)據(jù)取值方法第十頁，共五十四頁，編輯于2023年，星期四柵格數(shù)據(jù)的值整數(shù)值：如土壤分類字母：蔬菜類型、土地分區(qū)

實(shí)數(shù)：如高程值第十一頁，共五十四頁，編輯于2023年，星期四2.2.2柵格數(shù)據(jù)組織方法柵格數(shù)據(jù)以層的方式來組織文件，在柵格數(shù)據(jù)結(jié)構(gòu)中，物體的空間位置就用其在笛卡爾平面網(wǎng)格中的行號(hào)和列號(hào)坐標(biāo)表示，物體的屬性用象元的取值表示，每個(gè)象元在一個(gè)網(wǎng)格中只能取值一次，同一象元要表示多重屬性的事物就要用多個(gè)笛卡爾平面網(wǎng)格，每個(gè)笛卡爾平面網(wǎng)格表示一種屬性或同一屬性的不同特征，這種平面稱為層。第十二頁，共五十四頁，編輯于2023年，星期四以像元為序。不同層上同一像元位置上的各屬性值表示為一個(gè)列數(shù)組。以層為基礎(chǔ)。每一層又以像元為序記錄它的坐標(biāo)和屬性值。以層為基礎(chǔ)。但每一層內(nèi)則以多邊形為序記錄多邊形的屬性值和充滿多邊形的各像元的坐標(biāo)。柵格數(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)層n第十三頁，共五十四頁，編輯于2023年，星期四2.2.3柵格數(shù)據(jù)存儲(chǔ)編碼直接編碼鏈?zhǔn)骄幋a行程編碼塊式編碼四叉樹編碼

第十四頁，共五十四頁，編輯于2023年，星期四1.直接?xùn)鸥窬幋a直接?xùn)鸥窬幋a是最簡單最直觀而又非常重要的一種柵格結(jié)構(gòu)編碼方法，通常稱這種編碼為圖像文件或柵格文件。直接編碼就是將柵格數(shù)據(jù)看作一個(gè)數(shù)據(jù)矩陣，逐行（或逐列）逐個(gè)記錄代碼.3334444433334444133344421133322211113222111122221111122211111222133344444233334444313334442411333222511113222611112222711111222811111222第十五頁，共五十四頁，編輯于2023年，星期四2.鏈?zhǔn)骄幋a(ChainCodes)1(N)0(E)3(S)2(W)

+

02

1

02

1

03

3

03

32

2

3

24

3

0

3

05

1

0

12

0

1202

33

032223

2

3

221243

2

3

2212

2

12221213又稱弗里曼鏈碼（Freeman1961），多邊形邊界可以表示為由某一原點(diǎn)開始并按某些基本方向確定的單位矢量鏈?；痉较颍簴|=0，南=3，西=2，北=1第十六頁，共五十四頁，編輯于2023年，星期四3.行程編碼(Run-lengthencoding)

按行（或列）記錄相同代碼的始末象元的列號(hào)（或行號(hào)）和相應(yīng)的代碼，下圖可沿行方向進(jìn)行行程編碼：

第十七頁，共五十四頁，編輯于2023年，星期四只在各行（或列）數(shù)據(jù)的代碼發(fā)生變化時(shí)依次記錄該代碼以及相同代碼重重的個(gè)數(shù)。即按（屬性值和重復(fù)個(gè)數(shù)）編碼。第十八頁，共五十四頁，編輯于2023年，星期四逐個(gè)記錄各行（或列）代碼發(fā)生變化的位置和相應(yīng)的代碼，即按（位置，屬性值）編碼。第十九頁，共五十四頁，編輯于2023年，星期四4.塊式編碼(Blockencoding)1x1:

(0,2,1,1)

(0,3,1,1)(0,4,1,1)

(2,1,1,1)

(3,1,1,1)

(4,0,1,1)

(4,1,1,1)

(5,0,1,1)(5,5,1,1)

(6,0,1,1)

(6,8,1,1)

(8,3,1,1)

(11,8,1,1)

(12,8,1,1)

(14,3,1,1)

(14,4,1,1)2x2:

(3,7,2,2)

(4,9,2,2)

(5,7,2,2)

(7,7,2,2)

(8,2,2,2)

(9,7,2,2)

(12,4,2,2)

(13,2,2,2)

(14,6,2,2)3x3:

(5,3,3,3)

(11,7,3,3)4x4:

(1,5,4,4)

把多邊形范圍劃分成由象元組成的正方形，然后對(duì)各個(gè)正方形進(jìn)行編碼。塊式編碼數(shù)據(jù)結(jié)構(gòu)中包括3個(gè)數(shù)字：塊的初始位置（行、列號(hào)）和塊的大?。▔K包括的象元數(shù)），再加上記錄單元的代碼組成。

第二十頁，共五十四頁，編輯于2023年，星期四5.四叉樹編碼(Quadtrees)NWNESESWNWSWSENE(1)四叉樹分割：

將圖像區(qū)域按大小相同的象限4等分，每個(gè)象限又可根據(jù)一定規(guī)則判斷是否繼續(xù)等分為次一層的4個(gè)象限。子象限只含一種屬性代碼，則停止繼續(xù)分割。圖像區(qū)域的柵格陣列應(yīng)為2n×2n(2)四叉樹結(jié)構(gòu)：

把2n×2n象元組成的陣列當(dāng)作樹的根節(jié)點(diǎn)，樹的高度為n，每個(gè)節(jié)點(diǎn)分別代表南西（SW）、南東（SE）、北西（NW）、北東（NE）。四個(gè)分支中要么是樹葉、樹叉。樹葉代表一種代碼。樹叉繼續(xù)再分。第二十一頁，共五十四頁，編輯于2023年，星期四第二十二頁，共五十四頁，編輯于2023年，星期四(3)線性四叉樹編碼：

記錄每個(gè)葉結(jié)點(diǎn)的地址和值，值就是子區(qū)的屬性代碼，其中地址包括兩部分，共32位（二進(jìn)制）最右邊4位記錄該葉結(jié)點(diǎn)的深度，左邊的28位記錄路徑，從右邊第5位往左記錄從葉節(jié)點(diǎn)到根結(jié)點(diǎn)的路徑。0，1，2，3分別表示SW，SE，NW，NE。第10號(hào)結(jié)點(diǎn)編碼為：

0000……00001101|0011第二十三頁，共五十四頁，編輯于2023年，星期四(4)十進(jìn)制Morton碼的編碼行號(hào)5=0101列號(hào)7=0111Morton碼=00110111=55第二十四頁，共五十四頁，編輯于2023年，星期四

這樣就可將用行列表示的二維圖像，用Morton碼寫成一維數(shù)據(jù)，通過Morton碼就可知道象元的位置。

把一幅2n×2n的圖像壓縮成線性四叉樹的過程為：按Morton碼把圖象讀入一維數(shù)組。相鄰的四個(gè)象元比較，一致的合并，只記錄第一個(gè)象元的Morton碼。比較所形成的大塊，相同的再合并，直到不能合并為止。

對(duì)用上述線性四叉樹的編碼方法所形成的數(shù)據(jù)還可進(jìn)一步用游程長度編碼壓縮。壓縮時(shí)只記錄第一個(gè)象元的Morton碼。第二十五頁，共五十四頁，編輯于2023年，星期四例：四叉樹Morton碼編碼結(jié)果

第二十六頁，共五十四頁，編輯于2023年，星期四

解碼時(shí)，據(jù)Morton碼，可知象元在圖像中位置。從左上角，本Morton碼和下一個(gè)Morton碼之差即為象元個(gè)數(shù)。知道了象元的個(gè)數(shù)和象元的位置就可恢復(fù)出圖像了。第二十七頁，共五十四頁，編輯于2023年，星期四NWNESENWSWSEChainCodes:AdvantagesCompactEasyestimationofareasandperimetersdetectssharpturnsDisadvantagesOverlaydifficultRedundancyofboundariesmaynotalwayscompressRLE(Run-lengthencoding)AdvantagesGenerallyefficientandcompactDisadvantagesDatawithhighspatialvariabilitymaynotcompressneighbourhoodoperationdifficult第二十八頁，共五十四頁，編輯于2023年，星期四Blockencoding:AdvantagesefficientforlargeregionsgoodforoverlayinggoodfordeterminingshapeQuadtrees:Advantagesvariableresolutiongoodforneighbourhood operationsdetailedalgorithms (Samet,Dyer,…)Problemsshapeanalysisdifficult第二十九頁，共五十四頁，編輯于2023年，星期四2.3矢量數(shù)據(jù)結(jié)構(gòu)2.3.1矢量數(shù)據(jù)概念2.3.2矢量數(shù)據(jù)編碼內(nèi)容2.3.3拓?fù)潢P(guān)系理論2.3.4拓?fù)鋽?shù)據(jù)結(jié)構(gòu)第三十頁，共五十四頁，編輯于2023年，星期四2.3.1矢量數(shù)據(jù)概念矢量數(shù)據(jù)就是代表地圖圖形的各離散點(diǎn)平面坐標(biāo)（x，y）的有序集合。Point-simpleprimitiveLine-chainofpointsArea-closedchainofpoints第三十一頁，共五十四頁，編輯于2023年，星期四Points,linesandpolygonsPointscanrepresent:avertexanodealabelapointfeaturePolygonscanrepresent:anareafeatureaclosedringoflinesLinescanrepresent:aboundaryofapolygonanetworklinkingpointfeaturesalinearfeature第三十二頁，共五十四頁，編輯于2023年，星期四2.3.2矢量數(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ǔ)方法第三十三頁，共五十四頁，編輯于2023年，星期四1.點(diǎn)實(shí)體

第三十四頁，共五十四頁，編輯于2023年，星期四2.線實(shí)體

唯一標(biāo)識(shí)碼線標(biāo)識(shí)碼起始點(diǎn)終止點(diǎn)坐標(biāo)對(duì)序列顯示信息非幾何屬性線實(shí)體3.面實(shí)體

多邊形矢量編碼，不但要表示位置和屬性，更重要的是能表達(dá)區(qū)域的拓?fù)涮卣?，如形狀、鄰域和層次結(jié)構(gòu)等，以便使這些基本的空間單元可以作為專題圖的資料進(jìn)行顯示和操作。

第三十五頁，共五十四頁，編輯于2023年，星期四2.3.3空間關(guān)系的理論

空間關(guān)系可以是由空間實(shí)體的幾何特性(包括空間物體的地理位置與形狀)引起的空間關(guān)系，如距離、方位、連通性、相似性等；也可以是由空間實(shí)體的幾何特性和非幾何特性(包括度量屬性如高程值、坡度值、氣溫值等，名稱屬性如地名、物體名稱等)共同引起的空間關(guān)系，如空間分布現(xiàn)象的統(tǒng)計(jì)相關(guān)、空間自相關(guān)、空間相互作用、空間依賴等；還有一種是完全由空間實(shí)體的非幾何屬性所導(dǎo)出的空間關(guān)系，如由兩個(gè)城市的人口數(shù)的比較所產(chǎn)生的大小關(guān)系、時(shí)間上的先后關(guān)系、等級(jí)上的高低關(guān)系以及成因上的因果關(guān)系等都屬于此類關(guān)系。

第三十六頁，共五十四頁，編輯于2023年，星期四

這里，我們限定，空間關(guān)系是指空間實(shí)體之間存在的在一定區(qū)域上構(gòu)成的，由空間實(shí)體的幾何特征(位置、形狀)引起的，與空間特性有關(guān)的各種聯(lián)系.主要空間關(guān)系有：拓?fù)潢P(guān)系、順序關(guān)系和度量關(guān)系。空間關(guān)系是GIS的重要理論問題之一，在GIS空間數(shù)據(jù)建模、空間查詢、空間分析、空間推理、制圖綜合、地圖理解等過程中起著重要的作用。第三十七頁，共五十四頁，編輯于2023年，星期四Spatial-attributeanattributeisassociatedwitheachspatialentity(eg.User-IDinArcInfo)Spatial-spatialtherelationshipbetweenthespatialprimitives(eg.points,lines,polygons)ofafeaturespatialtopologyAttribute-attributetherelationshipbetweenvariousattributesaccomplishedbyusingjoinoperationsinarelationaldatabasePrimaryattributeDirectlyrelatedtotheentitySecondaryattributeIndirectrelationshipthroughjoin第三十八頁，共五十四頁，編輯于2023年，星期四1.Spatial-spatial

relationship鄰接相交重合相離包含點(diǎn)—點(diǎn)點(diǎn)—線點(diǎn)—面線—面面—面線—線第三十九頁，共五十四頁，編輯于2023年，星期四2.拓?fù)潢P(guān)系拓?fù)渌芯康氖菐缀螆D形的一些性質(zhì)，它們?cè)趫D形被彎曲、拉大、縮小或任意的變形下保持不變，只要在變形過程中不使原來不同的點(diǎn)重合為同一個(gè)點(diǎn)，又不產(chǎn)生新點(diǎn)。換句話說，這種變換的條件是：在原來圖形的點(diǎn)與變換了圖形的點(diǎn)之間存在著一一對(duì)應(yīng)的關(guān)系，并且鄰近的點(diǎn)還是鄰近的點(diǎn)。這樣的變換叫做拓?fù)渥儞Q。第四十頁，共五十四頁，編輯于2023年，星期四

幾何與拓?fù)涞南鄬?duì)關(guān)系幾何（Geometry）是與點(diǎn)的位置有關(guān)。拓?fù)洌╰opology）是與點(diǎn)的空間關(guān)系有關(guān)Note: Geometryhaschanged Topologyisidentical第四十一頁，共五十四頁，編輯于2023年，星期四

拓?fù)溆幸粋€(gè)形象說法——橡皮幾何學(xué)。因?yàn)槿绻麍D形都是用橡皮做成的，就能把許多圖形進(jìn)行拓?fù)渥儞Q。例如：一個(gè)橡皮圈能變形成一個(gè)圓圈或一個(gè)方圈。但是一個(gè)橡皮圈不能由拓?fù)渥儞Q成為一個(gè)阿拉伯?dāng)?shù)字8。因?yàn)椴话讶ι系膬蓚€(gè)點(diǎn)重合在一起，圈就不會(huì)變成8。拓?fù)淇臻g關(guān)系是指拓?fù)渥儞Q下的拓?fù)洳蛔兞浚負(fù)潢P(guān)系是指網(wǎng)結(jié)構(gòu)元素結(jié)點(diǎn)、弧段、面域之間的空間關(guān)系，主要表現(xiàn)為下列三種關(guān)系：拓?fù)溧徑雨P(guān)系（Adjacency

）、拓?fù)潢P(guān)聯(lián)關(guān)系（Incidence

）、拓?fù)浒P(guān)系（Enclosure）。第四十二頁，共五十四頁，編輯于2023年，星期四(1)鄰接關(guān)系（Adjacency）：拓?fù)溧徑又复嬖谟诳臻g圖形的同類元素之間的拓?fù)潢P(guān)系。第四十三頁，共五十四頁，編輯于2023年，星期四(2)關(guān)聯(lián)關(guān)系（Incidence）：拓?fù)潢P(guān)聯(lián)指存在于空間圖形的不同類元素之間的拓?fù)潢P(guān)系。

第四十四頁，共五十四頁，編輯于2023年，星期四(3)包含關(guān)系（Enclosure）：一種要素不相識(shí)包含另一種要素第四十五頁，共五十四頁，編輯于2023年，星期四2.3.4矢量數(shù)據(jù)結(jié)構(gòu)1.面條數(shù)據(jù)結(jié)構(gòu)（spaghetti）

2.索引式數(shù)據(jù)結(jié)構(gòu)3.DIME數(shù)據(jù)結(jié)構(gòu)4.ArcInfotopology第四十六頁，共五十四頁，編輯于2023年，星期四只記錄空間對(duì)象的位置坐標(biāo)和屬性信息，不記錄拓?fù)潢P(guān)系。存儲(chǔ)：獨(dú)立存儲(chǔ)：物體以獨(dú)立的實(shí)體存貯，不存貯點(diǎn)、線、面原始空間關(guān)系，只存幾何特征。空間對(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ù)雜的空間分析1.面條數(shù)據(jù)結(jié)構(gòu)（spaghetti）

第四十七頁，共五十四頁，編輯于2023年，星期四一幅地圖可以劃分成許多多邊形，每個(gè)多邊形由一條或若干條弧段組成，每條弧段由一串有序的x，y坐標(biāo)對(duì)組成，每條弧段的兩端點(diǎn)為結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)連接兩條以上的弧段，多邊形矢量編碼主要用于表示空間圖形為多邊形的面狀要素，每個(gè)多邊形在數(shù)據(jù)庫中是相互獨(dú)立、分開存儲(chǔ)的。第四十八頁，共五十四頁，編輯于2023年，星期四2.索引式線與點(diǎn)之間的樹狀索引

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

第四十九頁，共五十四頁，編輯于2023年，星期四點(diǎn)號(hào)坐標(biāo)1X1,y12X2,y2.31X31,y31線號(hào)起點(diǎn)終點(diǎn)點(diǎn)號(hào)a151，2，3，4，5b585，6，7，8j243124，25，26，27，28，