空間數(shù)據(jù)結(jié)構(gòu)學(xué)時四叉樹編碼

地理信息系統(tǒng)原理（★第2章空間數(shù)據(jù)結(jié)構(gòu)）2.1空間數(shù)據(jù)模型的類型在GIS中與空間信息有關(guān)的空間數(shù)據(jù)模型主要有兩個基于場(field-based)的空間模型把地理空間的事物和現(xiàn)象作為連續(xù)的變量或體來看待，表示了在二維或者三維空間中，空間實(shí)體的屬性信息被看作是連續(xù)變化的數(shù)據(jù)。AcollectionofspatialdistributionsContinuousdata.Examplesaltitude,rainfall,temperature,cropyield.

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

arealinepointployon柵格數(shù)據(jù)結(jié)構(gòu)實(shí)際上就是象元陣列，即象元按矩陣形式的集合(二維數(shù)組），每個象元是柵格數(shù)據(jù)中最基本的信息存儲單元，其坐標(biāo)位置可以用行號和列號確定。右圖在計算機(jī)內(nèi)是一個4*4階的矩陣。但在外部設(shè)備上，通常是以左上角開始逐行逐列存貯。存貯順序?yàn)椋篈AAAABBBAABBAAAB，當(dāng)每個像元都有唯一一個屬性值時，一層內(nèi)的編碼就需要m行×n列×3(x,y和屬性編碼值)個存儲單元。Row#(Y-coord)regionscellsAAAAABBBAABBAAABColumn#(X-coord)PunctualLinealAreal

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

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

實(shí)數(shù)：如高程值2.2.2柵格數(shù)據(jù)組織方法柵格數(shù)據(jù)以層的方式來組織文件，在柵格數(shù)據(jù)結(jié)構(gòu)中，物體的空間位置就用其在笛卡爾平面網(wǎng)格中的行號和列號坐標(biāo)表示，物體的屬性用象元的取值表示，每個象元在一個網(wǎng)格中只能取值一次，同一象元要表示多重屬性的事物就要用多個笛卡爾平面網(wǎng)格，稱為層。以像元為序。不同層上同一像元位置上的各屬性值表示為一個列數(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)層n2.2.3柵格數(shù)據(jù)存儲編碼直接編碼鏈?zhǔn)骄幋a行程編碼塊式編碼四叉樹編碼

1.直接編碼直接編碼是最簡單最直觀而又非常重要的一種柵格結(jié)構(gòu)編碼方法，通常稱這種編碼為圖像文件或柵格文件。直接編碼就是將柵格數(shù)據(jù)看作一個數(shù)據(jù)矩陣，逐行（或逐列）逐個記錄代碼.33344444333344441333444211333222111132221111222211111222111112221333444442333344443133344424113332225111132226111122227111112228111112222.鏈?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+只在各行（或列）數(shù)據(jù)的代碼發(fā)生變化時依次記錄該代碼以及重復(fù)出現(xiàn)次數(shù)。即按（屬性值,重復(fù)次數(shù)）編碼。3.行程編碼(Run-lengthencoding)逐個記錄各行（或列）代碼發(fā)生變化的位置和相應(yīng)的代碼，即按（位置，屬性值）編碼。如圖按列：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)

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

5.四叉樹編碼(Quadtrees)NWNESESWNWSWSENE(1)四叉樹分割：

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

把2n×2n象元組成的陣列當(dāng)作樹根，樹的高度為n，每個節(jié)點(diǎn)分別代表南西（SW）、南東（SE）、北西（NW）、北東（NE）。四個分支中要么是樹葉、樹叉。樹葉代表一種代碼。樹叉繼續(xù)再分。對一幅2n×2n的柵格陣列，最大深度為n，層次可能為0,1,…,n(3)線性四叉樹編碼:(馬里蘭大學(xué)的GIS系統(tǒng))

記錄每個葉結(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號結(jié)點(diǎn)編碼為： 0000……00001101|0011通過記錄葉結(jié)點(diǎn)的深度碼和層次碼來描述葉結(jié)點(diǎn)的位置(4)十進(jìn)制Morton碼的編碼行號5=0101列號7=0111Morton碼=00110111=55這樣就可將用行列表示的二維圖像，用Morton碼寫成一維數(shù)據(jù)，通過Morton碼就可知象元位置。

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

對用上述線性四叉樹的編碼方法所形成的數(shù)據(jù)還可進(jìn)一步用游程長度編碼壓縮。壓縮時只記錄第一個象元的Morton碼。例：四叉樹Morton碼編碼結(jié)果

解碼時，據(jù)Morton碼，可知象元在圖像中位置。從左上角，本Morton碼和下一個Morton碼之差即為象元個數(shù)。知道了象元的個數(shù)和象元的位置就可恢復(fù)出圖像了。課堂練習(xí)：1、柵格數(shù)據(jù)如何進(jìn)行取值？2、柵格數(shù)據(jù)存儲壓縮編碼方法主要有哪幾種？每種方法是如何編碼的？3、寫出4*4圖像對應(yīng)的Morton碼2.1矢量數(shù)據(jù)結(jié)構(gòu)2.1.1矢量數(shù)據(jù)概念2.1.2矢量數(shù)據(jù)編碼內(nèi)容2.1.3地理關(guān)系的類型2.1.3拓?fù)潢P(guān)系理論2.1.4拓?fù)鋽?shù)據(jù)結(jié)構(gòu)2.1.1基本概念矢量數(shù)據(jù)就是代表地圖圖形的各離散點(diǎn)平面坐標(biāo)（x，y）的有序集合。Point-simpleprimitiveLine-chainofpointsArea-closedchainofpointsPoints,linesandpolygonsPointscanrepresent:avertexanodealabelapointfeaturePolygonscanrepresent:anareafeatureaclosedringoflinesLinescanrepresent:aboundaryofapolygonanetworklinkingpointfeaturesalinearfeature2.1.2矢量數(shù)據(jù)結(jié)構(gòu)存儲方式

標(biāo)識碼屬性碼空間對象編碼唯一連接空間和屬性數(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)號文件線:點(diǎn)號串面:點(diǎn)號串點(diǎn)號XY1112223344………n5566存儲方法1.點(diǎn)實(shí)體

2.線實(shí)體

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

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

2.1.3空間關(guān)系的理論

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

Spatial-spatial

relationship鄰接相交重合相離包含點(diǎn)—點(diǎn)點(diǎn)—線點(diǎn)—面線—面面—面線—線

這里，我們限定，空間關(guān)系是指空間實(shí)體之間存在的在一定區(qū)域上構(gòu)成的，由空間實(shí)體的幾何特征(位置、形狀)引起的，與空間特性有關(guān)的各種聯(lián)系.主要空間關(guān)系有：拓?fù)潢P(guān)系、順序關(guān)系和度量關(guān)系?？臻g關(guān)系是GIS的重要理論問題之一，在GIS空間數(shù)據(jù)建模、空間查詢、空間分析、空間推理、制圖綜合、地圖理解等過程中起著重要的作用。

早期人們認(rèn)為GIS空間關(guān)系主要分為順序關(guān)系、度量關(guān)系、拓?fù)潢P(guān)系三大類。

Egenhofer指出空間關(guān)系(或空間介詞)表達(dá)了空間數(shù)據(jù)之間的一種約束，其中度量關(guān)系對空間數(shù)據(jù)的約束最為強(qiáng)烈,而順序關(guān)系次之,拓?fù)潢P(guān)系最弱。

度量關(guān)系屬于定量關(guān)系，拓?fù)渑c順序關(guān)系則屬于定性關(guān)系。但是定性的關(guān)系與定量的關(guān)系之間并不是絕對的，而是可以互相轉(zhuǎn)化的。

這里重點(diǎn)介紹空間拓?fù)潢P(guān)系。

1.圖論（Graphtheory）在圖論中，點(diǎn)叫做0-cells，線叫做1-cells，

區(qū)叫做2-cells。1-cells連接0-cells

形成2-cells。3.拓?fù)潢P(guān)系拓?fù)渌芯康氖菐缀螆D形的一些性質(zhì)，它們在圖形被彎曲、拉大、縮小或任意的變形下保持不變，只要在變形過程中不使原來不同的點(diǎn)重合為同一個點(diǎn)，又不產(chǎn)生新點(diǎn)。換句話說，這種變換的條件是：在原來圖形的點(diǎn)與變換了圖形的點(diǎn)之間存在著一一對應(yīng)的關(guān)系，并且鄰近的點(diǎn)還是鄰近的點(diǎn)。這樣的變換叫做拓?fù)渥儞Q。幾何與拓?fù)涞南鄬﹃P(guān)系幾何（Geometry）是與點(diǎn)的位置有關(guān)。拓?fù)洌╰opology）是與點(diǎn)的空間關(guān)系有關(guān)Note: Geometryhaschanged Topologyisidentical

拓?fù)溆幸粋€形象說法——橡皮幾何學(xué)。因?yàn)槿绻麍D形都是用橡皮做成的，就能把許多圖形進(jìn)行拓?fù)渥儞Q。例如：一個橡皮圈能變形成一個圓圈或一個方圈。但是一個橡皮圈不能由拓?fù)渥儞Q成為一個阿拉伯?dāng)?shù)字8。因?yàn)椴话讶ι系膬蓚€點(diǎn)重合在一起，圈就不會變成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）。(1)鄰接關(guān)系（Adjacency）：

同類拓?fù)湓刂g的關(guān)系

TwotopologicalentitiesofthesamekindshareatopologicalentityofanotherkindTwo0cellsshareacommon1cell(0/0cell)Two1cellsshareacommon0cell(1/1cell)Two2cellsshareacommon1cell(2/2cell)(2)關(guān)聯(lián)關(guān)系（Incidence）：

不同類拓?fù)湓刂g的關(guān)系

ManytopologicalentitiesofthesamekindconvergeonanentityofanotherkindMany1cellsconvergeonacommon0cell(1/0cellincidence)Many0cellsconvergeonacommon1cell(0/1cellincidence)Many2cellsconvergeonacommon1cell(2/1cellincidence)(3)包含關(guān)系（Enclosure）：不同級的元素之間的拓?fù)潢P(guān)系

拓?fù)涞?/p>

Endpoint(point,arc)點(diǎn)是弧的端點(diǎn)Simple-nonself-intersection(arc)非自交的弧On-boundary(point,region)溫哥華在加拿大和美國的邊界上Inside(point,region)明尼阿波利斯市在明尼蘇達(dá)州內(nèi)Outside(point,region)麥迪遜市在明尼蘇達(dá)州之外Open(region)加拿大的內(nèi)部是個開域（不包括其邊界）Close(region)Carleton郡是個閉域（包括其邊界）Connected(region)瑞士是個連通域，而日本不是連通域Inside(point,loop)點(diǎn)在環(huán)中Crosses(arc,region)路（?。┐┻^森林（區(qū)域）Touches(region,region)明尼蘇達(dá)州是威斯康星州的鄰州Touches(arc,region)土地覆蓋（區(qū)）和土地利用（區(qū)）相重疊非拓?fù)涞?/p>

Euclidean-distancepoint,point兩點(diǎn)間的距離Direction(point,point)麥迪遜市在明尼阿波利斯市的東面Length(arc)單位向量的長度是1個單位Perimeter(area)單位正方形的周長是4個單位Area(region)單位正方形的面積是1個平方單位

4.拓?fù)浜头峭負(fù)洳僮髋e例2.1.5矢量數(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.鏈狀雙重獨(dú)立式5.POLYVRT結(jié)構(gòu)6.ArcInfotopology只記錄空間對象的位置坐標(biāo)和屬性信息，不記錄拓?fù)潢P(guān)系。存儲：獨(dú)立存儲：物體以獨(dú)立的實(shí)體存貯，不存貯點(diǎn)、線、面原始空間關(guān)系，只存幾何特征。空間對象位置直接跟隨空間對象；點(diǎn)位字典：點(diǎn)坐標(biāo)獨(dú)立存儲，線、面由點(diǎn)號組成特征無拓?fù)潢P(guān)系，主要用于顯示、輸出及一般查詢公共邊重復(fù)存儲，存在數(shù)據(jù)冗余，難以保證數(shù)據(jù)獨(dú)立性和一致性多邊形分解和合并不易進(jìn)行，鄰域處理較復(fù)雜；處理嵌套多邊形比較麻煩適用范圍：制圖及一般查詢，不適合復(fù)雜的空間分析1.實(shí)體(面條)數(shù)據(jù)結(jié)構(gòu)（spaghetti）

一幅地圖可以劃分成許多多邊形，每個多邊形由一條或若干條弧段組成，每條弧段由一串有序的x，y坐標(biāo)對組成，每條弧段的兩端點(diǎn)為結(jié)點(diǎn)，每個結(jié)點(diǎn)連接兩條以上的弧段，多邊形矢量編碼主要用于表示空間圖形為多邊形的面狀要素，每個多邊形在數(shù)據(jù)庫中是相互獨(dú)立、分開存儲的。直接存儲2.索引式

(點(diǎn)位字典)線與點(diǎn)之間的樹狀索引

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

點(diǎn)號坐標(biāo)1X1,y12X2,y2.31X31,y31線號起點(diǎn)終點(diǎn)點(diǎn)號a151，2，3，4，5b585，6，7，8j243124，25，26，27，28，29，30，31多邊形號邊界線號Aa，b，hBc，f，g，h，j.Eb，c，I，d線點(diǎn)索引文件多邊形線索引文件點(diǎn)坐標(biāo)文件3.DIME結(jié)構(gòu)雙重獨(dú)立地圖編碼，簡稱DIME結(jié)構(gòu)（DualIndependentMapEncoding）。是一種把幾何量度信息（直角坐標(biāo)）與拓?fù)溥壿嬓畔⒔Y(jié)合起來的系統(tǒng)。(美國人口統(tǒng)計系統(tǒng)采用的一種編碼方式)DIME文件的基本元素是連接兩個端點(diǎn)（結(jié)點(diǎn)）的一條線段（街段）、線段始結(jié)點(diǎn)和終結(jié)點(diǎn)標(biāo)識符、伴有這兩個結(jié)點(diǎn)的坐標(biāo)及線段兩側(cè)的區(qū)域代碼（左區(qū)號和右區(qū)號）。根據(jù)結(jié)點(diǎn)標(biāo)識符和結(jié)點(diǎn)坐標(biāo)建立結(jié)點(diǎn)坐標(biāo)文件。根據(jù)結(jié)點(diǎn)、線段、多邊形間的拓?fù)潢P(guān)系建立拓?fù)浣Y(jié)構(gòu)文件。在這種結(jié)構(gòu)中，線段通常被認(rèn)為是直線型的，復(fù)雜的曲線由一系列逼近曲線的直線段來表示。結(jié)點(diǎn)與結(jié)點(diǎn)或者面域與面域之間為鄰接關(guān)系，而結(jié)點(diǎn)與線段或面域與線段之間為關(guān)聯(lián)關(guān)系,。

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

弧段文件弧段號 起始點(diǎn) 終結(jié)點(diǎn) 左多邊形 右多邊形 a 5 1 0 Ab 8 5 E Ac 16 8 E Bd 19 5 0 Ee 15 19 0 Df 15 16 D Bg 1 15 0 Bh 8 1 A Bi 16 19 D Ej 31 31 B C 弧段坐標(biāo)文件弧段號 點(diǎn)號 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ú)立式多邊形文件多邊形號 弧段號 周長