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

第三章空間數(shù)據(jù)結(jié)構(gòu)與編碼柵格數(shù)據(jù)結(jié)構(gòu)及編碼矢量數(shù)據(jù)結(jié)構(gòu)及編碼矢柵數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換矢柵一體化數(shù)據(jù)結(jié)構(gòu)

空間數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)編碼1.概念

空間數(shù)據(jù)結(jié)構(gòu)：指適合于計算機(jī)系統(tǒng)存儲、管理和處理的地學(xué)圖形的邏輯結(jié)構(gòu)，是地理實體的空間排列方式和相互關(guān)系的抽象描述。

空間數(shù)據(jù)編碼：為實現(xiàn)空間數(shù)據(jù)的計算機(jī)存儲、處理和管理，將空間實體的一定的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為適合計算機(jī)操作的過程。

圖形數(shù)據(jù)屬性數(shù)據(jù)編碼(數(shù)據(jù)結(jié)構(gòu))空間實體數(shù)據(jù)存入計算機(jī)柵格數(shù)據(jù)結(jié)構(gòu)：應(yīng)用與圖像處理系統(tǒng)和GIS中。矢量數(shù)據(jù)結(jié)構(gòu)：主導(dǎo)了CAD系統(tǒng)和有著強(qiáng)大制圖功能的GIS。一、基于規(guī)則格網(wǎng)空間數(shù)據(jù)模型的數(shù)據(jù)結(jié)構(gòu)(柵格數(shù)據(jù)結(jié)構(gòu))（一）概念柵格數(shù)據(jù)結(jié)構(gòu)是最簡單最直觀的空間數(shù)據(jù)結(jié)構(gòu)，又稱網(wǎng)格結(jié)構(gòu)或像元結(jié)構(gòu)。將地球表面劃分為大小均勻緊密相鄰的網(wǎng)格陣列，每個網(wǎng)格作為一個像元或者像素，有行、列號定義，并包含一個代碼，表示該網(wǎng)格的屬性值或者量值，或者僅僅包含指向其它屬性記錄的指針。（一）概念柵格數(shù)據(jù)結(jié)構(gòu)實際就是像元陣列，每個像元由行列確定它的位置。由于柵格結(jié)構(gòu)是按照一定的規(guī)則排列的，所表示的實體的位置很容易隱含在文件的存儲結(jié)構(gòu)中，且行列坐標(biāo)可以很容易的轉(zhuǎn)為其他坐標(biāo)系下的坐標(biāo)。在文件中每個代碼本身明確代表實體的屬性或?qū)傩跃幋a。點用一個柵格單元表示；線狀地物沿線走向的一組相鄰柵格單元表示，每個柵格單元最多只有兩個相鄰單元在線上；面或區(qū)域用記有區(qū)域?qū)傩缘南噜彇鸥駟卧募媳硎荆總€柵格單元可有多于兩個的相鄰單元同屬一個區(qū)域。

點線面（一）概念（二）基本特征點有大小、地理空間離散。大小由行列號決定，劃分程度決定點大小、點數(shù)多少、表達(dá)內(nèi)容的復(fù)雜程度及精度高低。屬性特征顯性表示?？梢灾苯涌吹綄傩?，并多以顏色、代碼或灰度表示。面向位置、感覺微觀

位置由行列號決定，每個位置都有相應(yīng)的數(shù)據(jù)。（三）柵格數(shù)據(jù)的組織不同類型的地理實體分層編排，每層只有單一的類型。一個柵格單元只有一個屬性代碼?？臻g數(shù)據(jù)庫22222aaaaa22土壤植被組織方法（三）柵格數(shù)據(jù)的組織數(shù)據(jù)文件像元1X坐標(biāo)Y坐標(biāo)層1屬性層2屬性...層n屬性像元2…像元n數(shù)據(jù)文件層1X坐標(biāo)Y坐標(biāo)屬性值像元2...像元n層2…層n像元1數(shù)據(jù)文件層1屬性值像元1坐標(biāo)像元2坐標(biāo)…多邊形2...多邊形n層2…層n多邊形1像元n坐標(biāo)（四）柵格結(jié)構(gòu)的建立1、

手工獲取，專題圖上劃分均勻網(wǎng)格，逐個決定其網(wǎng)格代碼。2、掃描儀掃描專題圖的圖像數(shù)據(jù){行、列、顏色（灰度）}，定義顏色與屬性對應(yīng)表，用相應(yīng)屬性代替相應(yīng)顏色，得到（行、列、屬性）再進(jìn)行柵格編碼、存貯，即得該專題圖的柵格數(shù)據(jù)。3、

由矢量數(shù)據(jù)轉(zhuǎn)換而來。4、

遙感影像數(shù)據(jù)，對地面景象的輻射和反射能量的掃描抽樣，并按不同的光譜段量化后，以數(shù)字形式記錄下來的象素值序列。5、

格網(wǎng)DEM數(shù)據(jù)，當(dāng)屬性值為地面高程，則為格網(wǎng)DEM，通過DEM內(nèi)插得到。一）建立途徑（四）柵格結(jié)構(gòu)的建立二）柵格系統(tǒng)的建立1、

柵格坐標(biāo)系的確定表示具有空間分布特征的地理要素，不論采用什么編碼系統(tǒng)，什么數(shù)據(jù)結(jié)構(gòu)都應(yīng)在統(tǒng)一的坐標(biāo)系統(tǒng)下，而坐標(biāo)系的確定實質(zhì)是坐標(biāo)系原點和坐標(biāo)軸的確定。由于柵格編碼一般用于區(qū)域性GIS，原點的選擇常具有局部性質(zhì)，但為了便于區(qū)域的拼接，柵格系統(tǒng)的起始坐標(biāo)應(yīng)與國家基本比例尺地形圖公里網(wǎng)的交點相一致，并分別采用公里網(wǎng)的縱橫坐標(biāo)軸作為柵格系統(tǒng)的坐標(biāo)軸。（四）柵格結(jié)構(gòu)的建立二）柵格系統(tǒng)的建立2、

柵格單元的尺寸1）原則：應(yīng)能有效地逼近空間對象的分布特征，又減少數(shù)據(jù)的冗余度。格網(wǎng)太大，忽略較小圖斑，信息丟失。2）方法：用保證最小多邊形的精度標(biāo)準(zhǔn)來確定尺寸經(jīng)驗公式：

h為柵格單元邊長

Ai為區(qū)域所有多邊形的面積。每個柵格元素只能取一個值，實際上一個柵格可能對應(yīng)于實體中幾種不同屬性值，存在柵格數(shù)據(jù)取值問題ABC

D（四）柵格結(jié)構(gòu)的建立三）柵格屬性值的確定1、中心點法用處于柵格中心處的地物類型或現(xiàn)象特性決定柵格代碼。中心點法常用于具有連續(xù)分布特性的地理要素，如降雨量分布、人口密度圖等。BDDDBBDCBBCCBBAAABC

D三）柵格屬性值的確定2、面積占優(yōu)法以占矩形區(qū)域面積最大的地物類型或現(xiàn)象特性決定柵格單元的代碼。用于分類較細(xì)，地物類別斑塊較小的情況。

BDDDBBDCBBCCBBAAABC

D三）柵格屬性值的確定3、長度占優(yōu)法將網(wǎng)格中心畫一橫線，用橫線所占最長部分屬性值作為柵格屬性BDDDBBDCBBCCBBAAABC

D三）柵格屬性值的確定4、重要性法突出某些主要屬性，只要在柵格中出現(xiàn)就把該屬性作為柵格屬性DDDDBDDCBBAABBAAABC

D三）柵格屬性值的確定5、百分比法根據(jù)矩形區(qū)域內(nèi)各地理要素所占面積的百分比數(shù)確定單元的取值。DDDDBDDCBBAABBAAABC

D三）柵格屬性值的確定（五）柵格數(shù)據(jù)編碼方式直接?xùn)鸥窬幋a壓縮編碼方法鏈碼（ChainEncoding）游程編碼（Run-lengthEncoding）塊狀編碼（BlockEncoding）四叉樹編碼（QuandtreeEncoding）

（五）柵格數(shù)據(jù)結(jié)構(gòu)類型（1）直接?xùn)鸥窬幋a

最簡單最直觀而又非常重要的一種柵格結(jié)構(gòu)編碼方法。把規(guī)則格網(wǎng)平面作為一個二維矩陣進(jìn)行數(shù)學(xué)表達(dá)，每個柵格是具有行、列位置的矩陣元素，該空間實體屬性編碼值賦予矩陣元素。

逐行或逐列記錄代碼。2221177722221777222222222227777744447777（1）直接?xùn)鸥窬幋a

(1,1,2),(1,2,2),(1,3,2),(1,4,1),(1,5,1),(1,6,7),(1,7,7),(1,8,7),(2,1,2),(2,2,2),(2,3,2),……如果行列號記錄在專門文件中，則只記錄屬性值：（2,2,2,1,1,7,7,7,2,2,2,2,1,7,7,7……）優(yōu)點：1易于實現(xiàn)用循環(huán)語句編程，實現(xiàn)快速運(yùn)算2易于實現(xiàn)空間屬性的分解與分類，易于實現(xiàn)空間分析中疊加等操作缺點：數(shù)據(jù)存儲量大基本要素包括：行，列，屬性值（N，M，Xij）其中行、列值隱性，屬性值顯性。（1）直接?xùn)鸥窬幋a

（2）費爾曼鏈碼（邊界編碼）

將線狀地物或區(qū)域邊界表示為：由某一起始點和某些基本方向上的單位矢量鏈組成。前兩個字母表示起點的行列號，從第三個數(shù)字開始每個數(shù)字表示單位矢量的方向。70162543單位矢量的長度為一個柵格單元，后續(xù)點可能位于前繼點8個基本方向上。（2）費爾曼鏈碼（邊界編碼）

具體編碼過程：起始點的尋找一般遵守從上到下、從左到右的原則。當(dāng)發(fā)現(xiàn)沒有記錄過的點且數(shù)值也不為零時，就是這一條線或邊界的起點，記下該地物的特征碼和行列號；然后按順時針方向?qū)ふ?，找到相鄰的等值點，并按八個方向編碼。如遇到不能閉合的線段，結(jié)束后可返回到起始點再開始尋找下一個線段。已記錄過的柵格單元，可將屬性代碼置零，以免重復(fù)編碼。2850002000008020000002000000020005502055555020555552000550020000000（2）費爾曼鏈碼（邊界編碼）特征碼高程起止行列鏈碼2100m1，44,5,4,5,5,45200m4，72,4,4,6,5,6,7,0,2,2,170162543454545424465670221（2）費爾曼鏈碼（邊界編碼）優(yōu)缺點：數(shù)據(jù)壓縮率強(qiáng)，便于計算長度，面積，轉(zhuǎn)折方向的凸凹度，易于儲存。但難于實現(xiàn)疊置運(yùn)算，不便于合并插入操作。對局部改動涉及到整體結(jié)構(gòu)。適于對曲線和邊界進(jìn)行編碼。（2）費爾曼鏈碼（邊界編碼）（3）游程（行程）編碼

基本思路：對一個柵格圖形，常常有行（列）方向上相鄰的若干柵格單元具有相同的屬性代碼，因而可采用某種方法壓縮那些重復(fù)代碼內(nèi)容。編碼方案：只是在各行（列）柵格單元的代碼發(fā)生變化時依次記錄該代碼以及相同代碼重復(fù)的個數(shù)或者記錄代碼發(fā)生變化的位置。（3）游程（行程）編碼

游程：柵格數(shù)據(jù)矩陣中相鄰并屬性相同的柵格視為一游程，以游程為單位記錄數(shù)據(jù)。2228800058888770第一行：4個游程第二行：3個游程適于對塊狀地物的柵格數(shù)據(jù)進(jìn)行壓縮編碼編碼方式：(gk，lk)gk—柵格屬性值lk—游程終止列號或長度K=1,2,3,4…..m(m<n)分為游程終止編碼和游程長度編碼

（3）游程（行程）編碼

(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)游程終止編碼（3）游程（行程）編碼

（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)游程長度編碼：（3）游程（行程）編碼

特點：屬性的變化愈少，游程愈長，即壓縮比的大小與圖的復(fù)雜程度成反比。

優(yōu)點：數(shù)據(jù)壓縮率高，易于實現(xiàn)疊加，檢索和合并運(yùn)算。缺點：適合類型區(qū)面積較大的專題圖、遙感影像分類集中的分類圖，不適合類型連續(xù)變化或類型區(qū)分散的分類圖。（3）游程（行程）編碼

（4）塊狀編碼是將游程長度編碼擴(kuò)展到二維的情況，采用正方形區(qū)域為單元對塊狀地物的柵格數(shù)據(jù)進(jìn)行編碼，實質(zhì)是把柵格陣列中同一屬性方形區(qū)域各元素映射成一個元素系列。每個記錄單元包含相鄰若干柵格，數(shù)據(jù)結(jié)構(gòu)由初始位置和半徑，在加上記錄單元的代碼組成。編碼方式：（行號，列號，半徑，代碼）0225555522222555000003332222335500233355003333530003333300003333（1，1，1，0），（1，2，2，2），（1，4，1，5），（1，5，1，5），（1，6，2，5），（1，8，1，5）；（2，1，1，2），（2，4，1，2），（2，5，1，2），（2，8，1，5）；（3，3，1，2），（3，4，1，2），（3，5，2，3），（3，7，2，5）；（4，1，2，0），（4，3，1，2），（4，4，1，3）；（5，3，1，3），（5，4，2，3），（5，6，1，3），（5，7，1，5），（5，8，1，3）；（6，1，3，0），（6，6，3，3）；（7，4，1，0），（7，5，1，3）；（8，4，1，0），（8，5，1，0）。（4）塊狀編碼特點：1、面狀地物所能包含的正方形越大，多邊形邊界越簡單，塊碼編碼效率超高；2、圖形比較碎，多邊形邊界復(fù)雜的圖形，數(shù)據(jù)壓縮率低；3、利于計算面積、合并插入等操作。（4）塊狀編碼（5）四叉樹編碼（QuadtreeCode）四叉樹概述：四叉樹又稱為四元樹或四分樹，是最有效的柵格數(shù)據(jù)壓縮編碼方法之一，絕大部分圖形操作和運(yùn)算都可以直接在四叉樹結(jié)構(gòu)上實現(xiàn)，四叉樹編碼即壓縮了數(shù)據(jù)量，又可大大提高圖形操作的效率。1、基本思想：將2n×2n象元組成的圖像(不足的用背景補(bǔ)上)按四個象限進(jìn)行遞歸分割，并判斷屬性是否單一，單一：不分。不單一：遞歸分割。最后得到一顆四分叉的倒向樹。（5）四叉樹編碼（QuadtreeCode）2、四叉樹的樹形表示：用一倒立樹表示分割和分割結(jié)果。根：整個區(qū)域高：深度、分幾級，幾次分割葉：不能再分割的塊樹叉：還需分割的塊。0123AAAAABBBAABBAABB000004440004444400444488004448882244888822248888222288882222888800004404440444848244824221）常規(guī)四叉樹及編碼原始柵格四叉樹圖1）常規(guī)四叉樹及編碼四叉樹編碼的樹狀表示NWNESWSE004482220000444444484442(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16)(17)(18)(19)(20)(21)(22)(23)(24)0層1層2層3層記錄這棵樹的葉結(jié)點外，中間結(jié)點，結(jié)點之間的聯(lián)系用指針聯(lián)系，每個結(jié)點需要6個變量：父結(jié)點指針、四個子結(jié)點的指針和本結(jié)點的屬性值。對一幅2N

×2N的柵格陣列，最大深度為N，可能有的層次為0，1，2，…，N，最大層數(shù)為N+1.那么，每層的柵格寬度為：

2（最大深度-當(dāng)前層次）反映了所在葉結(jié)點表示的正方形集合的大小。1）常規(guī)四叉樹及編碼缺點：所占空間比較大，不僅要記錄每個結(jié)點，還要記錄一個前趨結(jié)點和四個后繼點，以及反映結(jié)點之間聯(lián)系，對柵格數(shù)據(jù)進(jìn)行運(yùn)算時，還要作遍歷樹結(jié)點的運(yùn)算，增加操作復(fù)雜性。1）常規(guī)四叉樹及編碼指針不僅增加了數(shù)據(jù)的存儲量，還增加了操作的復(fù)雜性：如層次數(shù)（分割次數(shù)）由從父結(jié)點移到根結(jié)點的次數(shù)來確定，結(jié)點所代表的圖像塊的位置需要從根節(jié)點開始逐步推算下來。所以，常規(guī)四叉樹并不廣泛用于存儲數(shù)據(jù)，其價值在于建立索引文件，進(jìn)行數(shù)據(jù)檢索。2)線性四叉樹及編碼以四叉樹的方式組織數(shù)據(jù)，但不以四叉樹方式存儲數(shù)據(jù)。通過編碼四叉樹的葉結(jié)點表示數(shù)據(jù)的層次和空間關(guān)系。葉結(jié)點具有一個反映位置的關(guān)鍵字，亦稱位置碼。實質(zhì)是把原來大小相等的柵格集合轉(zhuǎn)換成大小不等的正方形集合，對不同尺寸和位置的正方形集合賦予一個位置碼。2)線性四叉樹及編碼

只存貯最后葉結(jié)點信息。包括：結(jié)點號、結(jié)點位置、深度、本節(jié)點的屬性或灰度值象限劃分：

0123(19)0(18)0(12)0(11)0(16)(15)(17)0(14)(13)(10)1（9）1(7)(6)(5)(4)（3）1（8）0（2）0（1）0

00000000000000001100000011110000111110001111000000000000000000002)線性四叉樹及編碼2）線性四叉樹及編碼（1）基于深度和層次碼的線性四叉樹編碼

它通過記錄葉結(jié)點的深度碼和層次碼來描述葉結(jié)點的位置，2N為層次碼。如圖中葉結(jié)點（7）的編碼為：層次碼深度碼（4位）第一層第二層第三層0011110011置碼十進(jìn)制值=243+相應(yīng)的屬性代碼值898001011100018962001011110019834001011010017819001111001116803001111001015787001111000114771001111000013706001010110012642001010100011578001010010010514001010000092570001100000824300110011117227001100111062110011001101519500110011004130001000100036600100001002200100000001十進(jìn)制碼二進(jìn)制碼葉結(jié)點號（2）基于四進(jìn)制的線性四叉樹編碼對每個柵格進(jìn)行編碼得表a。檢查相鄰4個m碼的屬性值，如相同進(jìn)行合并，除去最低值，。經(jīng)過一次檢測后，再檢測上層相鄰四個塊編碼的屬性值，如相同再合并。循環(huán)到?jīng)]有能合并的子塊為止，得表b。首先將柵格陣列的行列值分別轉(zhuǎn)換成二進(jìn)制碼，得二進(jìn)制行號Ib,列號Jb，然后求出四進(jìn)制四叉樹碼

MQ=2*Ib+Jb2）線性四叉樹及編碼333332323322233232223222111331330321320231230221220110313312303302213212203202101311310301300211210201200100133132123122033032023022011131130121120031030021020010113112103102013012003002001111110101100011010001000000111110101100011010001000列號行號表a333223223033023130130021200330320310300210100表b000000100屬性值1101100100屬性值21201033032031030020100四進(jìn)制碼191817161514131211葉結(jié)點號103393283173036302530143003232221四進(jìn)制碼葉結(jié)點號四進(jìn)制的線性四叉樹編碼四進(jìn)制線性四叉樹編碼的特點：優(yōu)點是便于實現(xiàn)行列值及其編碼之間的轉(zhuǎn)換；缺點是存儲開銷大，且一般軟件都不支持四進(jìn)制。（2）基于四進(jìn)制的線性四叉樹編碼2）線性四叉樹及編碼（3）基于十進(jìn)制的線性四叉樹編碼編碼：將二進(jìn)制的行列號按位交錯排列，可得到四叉樹葉結(jié)點的二進(jìn)制地址碼，進(jìn)而將二進(jìn)制碼轉(zhuǎn)成十進(jìn)制碼，得到四叉樹編碼。001110行號=011010=列號MD=142）線性四叉樹及編碼表a經(jīng)自下而上歸并得表b。依次檢查表a中四個相鄰葉結(jié)點的屬性代碼是否相同。若相同則歸并成一個父結(jié)點，記下地址及代碼。否則不予歸并。然后再歸并更高一層父結(jié)點，如此循環(huán)，直到不能歸并為止。（3)基于十進(jìn)制的線性四叉樹編碼2）線性四叉樹及編碼636259584746434211161605756454441401105554515039383534101535249483736333210031302726151411100112928252413129801023221918763200121201716541000011111010110001101000100060564440515052494836321514131281640表a表b060056052051050049148044040136132016115114013012180400屬性值MD碼值屬性值MD碼值0491480401320161140121800四叉樹游程編碼特點：比四進(jìn)制節(jié)省儲存空間，且前后兩個MD碼之間差代表了葉結(jié)點的大小，還可進(jìn)一步利用游程編碼對數(shù)據(jù)進(jìn)行壓縮。優(yōu)點：具有可變分辨率，能精確表示圖形的細(xì)節(jié)部分，編碼效率高；具有區(qū)域性質(zhì)，適合于圖形圖像的分析運(yùn)算；便于島的分析。(3)基于十進(jìn)制的線性四叉樹編碼2）線性四叉樹及編碼（三）四叉樹優(yōu)缺點優(yōu)點：1）對于團(tuán)塊圖像，四叉樹表示法占用空間比網(wǎng)絡(luò)法要少得多，四叉樹表示法基本上是一種非冗余表示法。2）四叉樹具有可變率或多重分辯率的特點使得它有很好的應(yīng)用前景，適用于處理凝聚性或呈塊狀分布的空間數(shù)據(jù)，特別適用于處理分布不均勻的塊狀空間數(shù)據(jù)，但不適用于連續(xù)表面（如地形）或線狀地物。此外，目前應(yīng)用四叉樹還存下列問題：1)矢/柵正反變換還不理想。2)

建立四叉樹耗費機(jī)時很多。3)

四叉樹雖可修改，但很費事（具體的數(shù)據(jù)結(jié)構(gòu)中會提到）（三）四叉樹優(yōu)缺點4)

四叉樹未能直接表示物體間的拓?fù)潢P(guān)系。5)

與非樹表示法比較，四叉樹表示法的缺點在于轉(zhuǎn)換的不穩(wěn)定性或叫滑動變異例如，兩個圖像的差異僅由于平移，就會構(gòu)成極為不同的四叉樹，因而很難根據(jù)四叉樹來判斷這兩個圖像是否全同，故不利于做形狀分析和模式識別，

A0A1A4A5A2

B3B6B7A8A9B12B13A10A11B14B15AAAAABBBAABBAABB6)一個物體的圖像在構(gòu)成四叉樹時會被分割到若干個象限中，使它失去了內(nèi)在的相關(guān)性。AAAAABBBAABBAABB二、矢量數(shù)據(jù)結(jié)構(gòu)-概念（一）概念矢量結(jié)構(gòu)是表達(dá)空間數(shù)據(jù)的另一種常見數(shù)據(jù)結(jié)構(gòu)，通過記錄坐標(biāo)的方式盡可能精確地表示點、線、多邊形等地理實體。二、矢量數(shù)據(jù)結(jié)構(gòu)-（二）基本特征點無大小、地理空間連續(xù)。

屬性特征隱性表示。幾何位置、屬性數(shù)據(jù)、拓?fù)潢P(guān)系分別存儲。指向地物、感覺宏觀

幾何實體無論大小，每個實體均勻一條數(shù)據(jù)記錄存儲，一條記錄指向一個地物。二、矢量數(shù)據(jù)結(jié)構(gòu)-（三）編碼內(nèi)容唯一標(biāo)識符空間位置：（x,y）坐標(biāo)對拓?fù)潢P(guān)系

屬性特征時間特征

二、矢量數(shù)據(jù)結(jié)構(gòu)-（三）編碼內(nèi)容（3.1）點實體編碼內(nèi)容點實體包括單獨一對（x,y）坐標(biāo)定位的一切地理或制圖實體。點是空間上不能再分的地理實體，可以是具體的或抽象的。

二、矢量數(shù)據(jù)結(jié)構(gòu)-（三）編碼內(nèi)容（3.1）點實體二、矢量數(shù)據(jù)結(jié)構(gòu)-（三）編碼內(nèi)容（3.2）線實體由直線元素構(gòu)成的各種線性要素。線實體主要用來表示線狀地物符號線和多邊形邊界，有時也稱為“弧”、“鏈”、“串”等。

線實體編碼基本內(nèi)容二、矢量數(shù)據(jù)結(jié)構(gòu)-（三）編碼內(nèi)容（3.3）多邊形區(qū)域?qū)嶓w中，具有名稱屬性和分類屬性，多用多邊形表示

。多邊形矢量編碼不但要表示位置和屬性，更為重要的是要能表達(dá)區(qū)域的拓?fù)湫再|(zhì)。

二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼編碼方法：無拓?fù)潢P(guān)系的編碼方法：僅記錄空間目標(biāo)的位置和屬性信息，而不記錄拓?fù)潢P(guān)系。拓?fù)潢P(guān)系的編碼方法：不僅記錄空間目標(biāo)的位置和屬性信息，而且記錄拓?fù)潢P(guān)系。二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼（4.1）坐標(biāo)序列法以多邊形為單元進(jìn)行組織。由多邊形邊界的x,y坐標(biāo)對集合組成。邊界坐標(biāo)數(shù)據(jù)與多邊形單元實體一一對應(yīng)，各個多邊形的邊界都有單獨編碼和數(shù)字化。二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼（4.1）坐標(biāo)序列法10：x1,y1；x2,y2；x3,y3；x4,y4；x5,y5；x6,y6；x7,y7；x8,y8；x9,y9；x10,y10；x11,y11；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；30：x33,y33；x34,y34；x35,y35；x36,y36；x37,y37；x38,y38；x39,y39；x40,y40；40：x19,y19；x20,y20；x21,y21；x28,y28；x29,y29；x30,y30；x31,y31；x32,y32；50：x21,y21；x22,y22；x23,y23；x8,y8；x7,y7；x6,y6；x24,y24；x25,y25；x26,y26；x27,y27；x28,y28；二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼（4.1）坐標(biāo)序列法

優(yōu)點：編碼容易、數(shù)字化操作簡單、數(shù)據(jù)編排直觀。缺點：多邊形之間公共邊界數(shù)字化兩遍，數(shù)據(jù)冗余存儲，多邊形邊界容易出現(xiàn)間隙或重疊。缺少的多邊形的鄰域信息和圖形的拓?fù)潢P(guān)系。島作為一個單獨的圖形，沒有建立與外界多邊形的聯(lián)系。二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼（4.2）樹狀索引結(jié)構(gòu)編碼采用樹狀索引，以減少數(shù)據(jù)冗余并間接增加鄰域信息。具體方法：對所有邊界點進(jìn)行數(shù)字化，將坐標(biāo)對以順序方式存儲，由點索引與邊界號相聯(lián)系，以線索引與各多邊形相聯(lián)系，形成樹狀索引結(jié)構(gòu)。二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼（4.2）樹狀索引結(jié)構(gòu)編碼數(shù)據(jù)記錄形式：多邊形文件多邊形與線索引文件線文件邊界線與點索引文件點文件點文件：點號—x,y坐標(biāo)線文件：線號—起點—終點—點號序列多邊形文件：多邊形號—邊界線號序列例：P148-P149索引式

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

點與邊界線之間的樹狀索引

二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼（4.2）樹狀索引結(jié)構(gòu)編碼

優(yōu)點：數(shù)據(jù)冗余小、編排直觀、鄰域信息和島狀信息可以得到一定處理。缺點：運(yùn)算繁瑣。鄰接與包含關(guān)系處理困難。編碼表要人工建立，工作量大、易出錯。二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼（4.3）雙重獨立結(jié)構(gòu)編碼（DIME）采用拓?fù)渚幋a結(jié)構(gòu)，以線文件為編碼主體。數(shù)據(jù)記錄形式：點文件：點號—x,y坐標(biāo)線文件：線號—起點—終點—左多邊形號—右多邊形號特點：

數(shù)據(jù)冗余進(jìn)一步縮小，數(shù)據(jù)檢核、更新和檢索方便，能自動生產(chǎn)多邊形文件。

二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼（4.3）雙重獨立結(jié)構(gòu)編碼11k12345678910abcdefhijlgⅠⅡⅢ線號左多邊形右多邊形起點終點aⅠⅡ12bⅠⅡ23cⅠⅡ34….…………k0Ⅰ1011l0Ⅰ114線文件二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼（4.4）鏈狀雙重獨立結(jié)構(gòu)是對DIME方法的一種改進(jìn)。DIME中一條邊只能由直線兩端點及相鄰面域表示，而這種方法可以將若干線段合為一個弧段，每個弧段有許多中間點，其端點則為弧段的交點或起始點。二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼（4.4）鏈狀雙重獨立結(jié)構(gòu)弧段坐標(biāo)文件：一系列點的位置坐標(biāo)組成?；《挝募夯∮涗浗M成（記錄弧的起止點號和左右多邊形號）。多邊形文件：多邊形記錄組成（多邊形號、有關(guān)弧段號，周長、面積、中心點坐標(biāo)、島狀區(qū)域信息）。二、矢量數(shù)據(jù)結(jié)構(gòu)-（四）矢量數(shù)據(jù)結(jié)構(gòu)編碼線號坐標(biāo)AX1,y1;X2,y2;X3,y3;X4,y4BX1,y1;X10,y10;X11,y11;X4,y4CX4,y4;X8,y8;X9,y9;X1,y1DX5,y5;X6,y6;X7,y7;X5,y5線號起點終點左多邊形右多邊形A14ⅠⅡB140ⅠC410ⅡD55ⅡⅢC11k12345678910abcdefhijlgⅠⅡⅢABD多邊形號弧段號起始結(jié)點周長面積中心點坐標(biāo)ⅠA，B1ⅡA，C，D1ⅢD5弧段坐標(biāo)文件弧段文件多邊形文件三、柵格-矢量數(shù)據(jù)一體化結(jié)構(gòu)-比較矢量柵格基本特征點的認(rèn)識點無大小點有大小地圖空間連續(xù)離散數(shù)據(jù)指向地物位置屬性顯示隱式顯式使用效果數(shù)據(jù)結(jié)構(gòu)復(fù)雜簡單數(shù)據(jù)量小大數(shù)據(jù)精度高低輸出效果優(yōu)劣（3.1）兩種數(shù)據(jù)結(jié)構(gòu)的比較三、柵格-矢量數(shù)據(jù)一體化結(jié)構(gòu)-比較矢量柵格數(shù)據(jù)操作幾何變形易難投影變換易難網(wǎng)絡(luò)分析易難數(shù)據(jù)融合難易數(shù)學(xué)分析難易疊加分析難易應(yīng)用范圍數(shù)據(jù)采集、存儲數(shù)據(jù)運(yùn)算、分析三、柵格-矢量數(shù)據(jù)一體化結(jié)構(gòu)-互換（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換一、點的轉(zhuǎn)換矢量結(jié)構(gòu)：（X,Y）坐標(biāo)精度的變化柵格結(jié)構(gòu)：（行，列）

二、線的轉(zhuǎn)換矢量結(jié)構(gòu)點的內(nèi)插柵格結(jié)構(gòu)：數(shù)據(jù)精度降低柵格結(jié)構(gòu)點的壓縮矢量結(jié)構(gòu)：坐標(biāo)精度提高

三、面的轉(zhuǎn)換矢量結(jié)構(gòu)柵格結(jié)構(gòu)：多邊形填充柵格結(jié)構(gòu)矢量結(jié)構(gòu)：矢量化

（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換矢量數(shù)據(jù)的坐標(biāo)是直角坐標(biāo)，原點為圖的左下方；柵格數(shù)據(jù)的坐標(biāo)是行列坐標(biāo)，原點在圖的左上方。在進(jìn)行兩種坐標(biāo)數(shù)據(jù)轉(zhuǎn)換時，通常使直角坐標(biāo)的x，y軸分別同柵格數(shù)據(jù)的行、列平行。

（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換①確定柵格單元的大小矢量數(shù)據(jù)向柵格數(shù)據(jù)轉(zhuǎn)換時，首先必須確定柵格元素的大小，即分辨率。根據(jù)原矢量圖的大小，精度要求、所研究問題的性質(zhì)和存儲空間，確定柵格的分辨率。

（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換②點的轉(zhuǎn)換

點的轉(zhuǎn)換實質(zhì)上是將點的矢量坐標(biāo)轉(zhuǎn)換成柵格數(shù)據(jù)中行列值i和j，從而得到點所在柵格元素的位置。

坐標(biāo)精度的變化（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換③線的轉(zhuǎn)換

曲線可用折線來表示的，也就是當(dāng)折線上取點足夠多時，所畫的折線在視覺上成為曲線。因此，線的變換實質(zhì)上是完成相鄰兩點之間直線的轉(zhuǎn)換。其轉(zhuǎn)換過程不僅包括坐標(biāo)點A，B分別從點矢量數(shù)據(jù)轉(zhuǎn)換成柵格數(shù)據(jù)，還包括求出直線AB所經(jīng)過的中間柵格數(shù)據(jù)。（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換③線的轉(zhuǎn)換具體轉(zhuǎn)換過程：利用上述點轉(zhuǎn)換法，將點A(x1，y1)，B(x2，y2)分別轉(zhuǎn)換成柵格數(shù)據(jù)，求出相應(yīng)的柵格的行、列值。由上述行列值求出直線所在行列值的范圍。確定直線經(jīng)過的中間柵格列值。

（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換③線的轉(zhuǎn)換

1)求出相應(yīng)i行中心處同直線相交的y值。

2)用直線方程求出對應(yīng)y值的點的x值。

3)從x，y值按公式求出相應(yīng)i行的列值j。

YX（0,0）（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換③線的轉(zhuǎn)換

依據(jù)上述過程，依次求出直線經(jīng)過的每個網(wǎng)格單元，并用直線的屬性值去填充這些網(wǎng)格，就完成了線的轉(zhuǎn)換。整個曲線或多邊形邊界經(jīng)分段連續(xù)運(yùn)算即可以完成轉(zhuǎn)換。于此類似，可以先計算出兩個端點的列值，知道直線要經(jīng)過的列，然后計算各列中心線的Y值，再求出相應(yīng)的行數(shù)I。（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換④面的填充矢量數(shù)據(jù)結(jié)構(gòu)中面域用邊界線表示，面域內(nèi)部是空心的；柵格數(shù)據(jù)結(jié)構(gòu)中整個面域都要用屬性值填充，因此，邊界線轉(zhuǎn)換完以后，必須進(jìn)行面域?qū)傩灾档奶畛?。常用算法?.內(nèi)部點擴(kuò)散算法2.復(fù)數(shù)積分算法3.射線法4.掃描算法5.邊界代數(shù)算法（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換④面的填充—內(nèi)部點擴(kuò)散算法該算法由每個多邊形一個內(nèi)部點（種子點）開始，向其八個方向的鄰點擴(kuò)散，判斷各個新加入點是否在多邊形邊界上，如果是邊界上，則該新加入點不作為種子點，否則把非邊界點的鄰點作為新的種子點與原有種子點一起進(jìn)行新的擴(kuò)散運(yùn)算，并將該種子點賦以該多邊形的編號。

（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換④面的填充—復(fù)數(shù)積分算法對全部柵格陣列逐個柵格單元地判斷該柵格歸屬的多邊形編碼，判別方法是由待判點對每個多邊形的封閉邊界計算復(fù)數(shù)積分，對某個多邊形，如果積分值為2

i，則該待判點屬于此多邊形，賦以多邊形編號，否則在此多邊形外部，不屬于該多邊形。

（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換④面的填充—射線算法射線算法可逐點判斷數(shù)據(jù)柵格點在某多邊形之外或在多邊形內(nèi)，由待判點向圖外某點引射線，判斷該射線與某多邊形所有邊界相交的總次數(shù)，如相交偶數(shù)次，則待判點在該多邊形外部，如為奇數(shù)次，則待判點在該多邊形內(nèi)部

采用射線算法，要注意的是：射線與多邊形邊界相交時，有一些特殊情況會影響交點的個數(shù)，必須予以排除。

射線算法射線算法的特殊情況（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換④面的填充—掃描算法掃描算法是射線算法的改進(jìn)，將射線改為沿柵格陣列,列或行方向掃描線，常用的方法有：平行線掃描法和鉛垂線跌落法。

（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換④面的填充—掃描算法

平行線掃描法：從待檢驗的柵格單元作一平行于x軸的掃描線，當(dāng)與多邊形相交的點數(shù)為偶數(shù)時，則該柵格在多邊形之外，當(dāng)交點為奇數(shù)時，該柵格在多邊形之內(nèi)。有時也會出現(xiàn)極值點的情況，就會出現(xiàn)錯誤判斷。PQRabcdgfeYX（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換④面的填充—掃描算法

鉛垂線跌落法：從待檢驗的柵格單元作一垂直于x軸的直線，檢查它與多邊形邊界交點的點數(shù)，偶數(shù)時在多邊形之外，奇數(shù)時在多邊形之內(nèi)。為了避免錯誤可同時采用這兩種算法，只要一種方法交點為奇數(shù)，該點就在多邊形之內(nèi)。PQRabcdgfeYX（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換④面的填充—邊界代數(shù)算法[任伏虎]⑴單個多邊形初始化柵格陣列，所有單元賦值為0。欲填充多邊形值為a。以柵格行列為參考坐標(biāo)軸，以多邊形邊界上某一點為起始點順時針方向搜索邊界。邊界上行時，左側(cè)同行柵格單元值-a。邊界下行時，左側(cè)同行柵格單元值+a。回到起點，形成柵格多邊形。（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換（3.2）兩種數(shù)據(jù)結(jié)構(gòu)的互換-矢量向柵格轉(zhuǎn)換④面的填充—邊界代數(shù)算法⑵多個多邊形對每幅地圖的全部具有左右多邊形編號的邊界弧段,沿其前進(jìn)的方向逐個搜索,當(dāng)邊界上行時,將邊界線位置與左圖框之間的網(wǎng)格點加上一個值=(左多邊形編號-右多邊形編號);當(dāng)邊界下行時,將邊界線位置與左圖框之間的網(wǎng)格點加上一個值=(右多邊形編號-左多邊形編號);當(dāng)邊界平行柵格行行走時,不做運(yùn)算。（3.2）兩種