第八章地理信息系統(tǒng)算法

1、 空間數(shù)據(jù)壓縮算法gisgis的內(nèi)部數(shù)據(jù)結(jié)構(gòu)的內(nèi)部數(shù)據(jù)結(jié)構(gòu)矢量結(jié)構(gòu)和柵格結(jié)構(gòu)矢量結(jié)構(gòu)和柵格結(jié)構(gòu) 內(nèi)部數(shù)據(jù)結(jié)構(gòu)：描述地理實(shí)體的數(shù)據(jù)本身的組織方法。內(nèi)部數(shù)據(jù)結(jié)構(gòu)基本上可分為兩大類：矢量結(jié)構(gòu)和柵格結(jié)構(gòu)（也可以稱為矢量模型和柵格模型）（右圖所示）。兩類結(jié)構(gòu)都可用來描述地理實(shí)體的點(diǎn)、線、面三種基本類型。 空間數(shù)據(jù)編碼是空間數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，即將根據(jù)地理信息系統(tǒng)的目的和任務(wù)所搜集的、經(jīng)過審核了的地形圖、專題地圖和遙感影像等資料按特定的數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換為適合于計(jì)算機(jī)存儲(chǔ)和處理的數(shù)據(jù)的過程。由于地理信息系統(tǒng)數(shù)據(jù)量極大，一般采用壓縮數(shù)據(jù)的編碼方式以減少數(shù)據(jù)冗余。一、柵格數(shù)據(jù)結(jié)構(gòu)及其壓縮柵格結(jié)構(gòu)是最簡(jiǎn)單最直接的空間數(shù)據(jù)

2、結(jié)構(gòu)，是指將地球表面劃分為大小均勻緊密相鄰的網(wǎng)格陣列，每個(gè)網(wǎng)格作為一個(gè)象元或象素由行、列定義，并包含一個(gè)代碼表示該象素的屬性類型或量值，或僅僅包括指向其屬性記錄的指針。在柵格結(jié)構(gòu)中：點(diǎn)用一個(gè)柵格單元表示； 線狀地物沿線走向的一組相鄰柵格單元表示， 每個(gè)柵格單元最多只有兩個(gè)相鄰單元 在線上； 面或區(qū)域用記有區(qū)域?qū)傩缘南噜彇鸥駟卧募?合表示，每個(gè)柵格單元可有多于兩個(gè) 的相鄰單元同屬一個(gè)區(qū)域。 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

3、 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 0 6 6 6 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 6 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 7 4 4 4 4 4 4 7 7 7 7 4 7 7 7 4 4 4 4 8 7 7 8 0 8 4 0 8 7 7 8 0 8 8 0 0 8 0 0 8 8 7 8 8 8 8 8 0 0 0 0 8 8 8 8 0 0 0 0 0 8 8 8 （a）點(diǎn) （b）線 （c）面點(diǎn)、線、區(qū)

4、域的格網(wǎng)柵格數(shù)據(jù)的獲取柵格數(shù)據(jù)的獲取 1.遙感方法獲取(航天與航空)；2.圖片掃描獲取(紙介質(zhì)的地圖等掃描)；3.矢量數(shù)據(jù)轉(zhuǎn)換而來；4.由平面上行距,列距固定的點(diǎn)抽樣而來主要包括: (1)中心歸屬法 (2)長(zhǎng)度占優(yōu)法 (3)面積占優(yōu)法柵格數(shù)據(jù)（柵格數(shù)據(jù)（1 1）柵格數(shù)據(jù)（柵格數(shù)據(jù)（2 2）柵格數(shù)據(jù)（柵格數(shù)據(jù)（3 3）上海東方明珠電視塔上海東方明珠電視塔故宮故宮柵格數(shù)據(jù)（柵格數(shù)據(jù)（4 4）spot xs 20m*20m 牡丹水庫band g, r, ir網(wǎng)格資料關(guān)於衛(wèi)星影像柵格數(shù)據(jù)的組織數(shù)據(jù)文件像元1i坐標(biāo)j坐標(biāo)層1屬性值層2屬性值層n屬性值像元2像元n數(shù)據(jù)文件層1像元1i坐標(biāo)j坐標(biāo)屬性值層2層

5、n像元2數(shù)據(jù)文件層1多邊形1屬性值像元1坐標(biāo)像元n坐標(biāo)層2層n多邊形n節(jié)省空間節(jié)省空間形式簡(jiǎn)單形式簡(jiǎn)單方便制圖方便制圖柵格數(shù)據(jù)的壓縮算法柵格數(shù)據(jù)文件記錄有3個(gè)基本方式：基于像元、基于層和基于面域。這三種方式都離不開對(duì)像元坐標(biāo)和屬性的記錄。因此基于柵格的空間數(shù)據(jù)壓縮的實(shí)質(zhì)是研究柵格數(shù)據(jù)的編碼，通過編碼盡量減少像元數(shù)量的存儲(chǔ)。其方法有三大類：（1）從減少記錄像元的數(shù)量入手； （2）從減少像元的記錄信息量入手； （3）前兩者的結(jié)合。柵格數(shù)據(jù)的壓縮分為無損壓縮技術(shù)和有損壓縮技術(shù)。（1）無損壓縮技術(shù)是指壓縮過程中沒有任何信息損失，通過解碼操作可以完全恢復(fù)原來的信息；（2）信息有損壓縮是指為了提高壓縮效率

6、，最大限度地壓縮數(shù)據(jù)，在壓縮過程中損失一部分相對(duì)不太重要的信息，解碼時(shí)這部分難以恢復(fù)。 柵格數(shù)據(jù)的壓縮1.直接?xùn)鸥窬幋a直接?xùn)鸥窬幋a 這是最簡(jiǎn)單直觀而又非常重要的一種柵格結(jié)構(gòu)編碼方法，通常稱這種編碼的圖像文件為網(wǎng)格文件或柵格文件，柵格結(jié)構(gòu)不論采用何種壓縮編碼方法，其邏輯原型都是直接編碼網(wǎng)格文件。 直接編碼就是將柵格數(shù)據(jù)看作一個(gè)數(shù)據(jù)矩陣，逐行（或逐列）逐個(gè)記錄代碼，可以每行都從左到右逐個(gè)象元記錄，也可以奇數(shù)行地從左到右而偶數(shù)行地從右向左記錄，為了特定目的還可采用其他特殊的順序。下圖為一些常用的柵格排列順序。 一些常用的柵格排列順序 2.2.鏈?zhǔn)骄幋a（鏈?zhǔn)骄幋a（chain codeschain co

7、des） 鏈?zhǔn)骄幋a又稱為弗里曼鏈碼freeman或邊界鏈碼。多邊形邊界可以表示為：由某一原點(diǎn)開始并按某些基本方向確定的單位矢量鏈?；痉较蚩梢远椋簴|=0，東南=1，南=2，西南=3，西=4，西北=5，北=6，東北=7，8個(gè)基本方向。 s/2w/4wn/5n/6en/7e/0ws/3es/13,1,7,0,1,2,3,4,5,64,1,6,7,0,1,2,3,4,5例子：如果再確定原點(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

8、，6，6。 s/2w/4wn/5n/6en/7e/0ws/3es/1優(yōu)點(diǎn)：優(yōu)點(diǎn)：鏈?zhǔn)竭叴a可以有效地壓縮柵格數(shù)據(jù)，而且對(duì)于估算面積、長(zhǎng)度、轉(zhuǎn)折方向的凹凸度等運(yùn)算十分方便，比較適合于存儲(chǔ)圖形數(shù)據(jù)。缺點(diǎn)：缺點(diǎn)：對(duì)邊界進(jìn)行合并和插入等修改編輯工作比較困難，對(duì)局部的修改將改變整體結(jié)構(gòu)，效率較低，而且由于鏈碼以每個(gè)區(qū)域?yàn)閱挝淮鎯?chǔ)邊界，相鄰區(qū)域的邊界將被重復(fù)存儲(chǔ)而產(chǎn)生冗余。3.3.游程長(zhǎng)度編碼（游程長(zhǎng)度編碼（run-length codesrun-length codes）游程長(zhǎng)度編碼是柵格數(shù)據(jù)壓縮的重要編碼方法。游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程長(zhǎng)度編碼結(jié)構(gòu)是逐行將相鄰?fù)档木W(wǎng)格合并記錄合并后網(wǎng)格的值及合并網(wǎng)

9、格的長(zhǎng)度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。游程長(zhǎng)度編碼結(jié)構(gòu)的建立方法是：將柵格矩陣的數(shù)據(jù)序列x1,x2,xn，映射為相應(yīng)的二元組序列（ai,pi）,i=1,2,k,且kn。其中，a為屬性值，p為游程，k為游程序號(hào)。 面域柵格矩陣結(jié)構(gòu)二元映射序號(hào)二元組序列1（a，2 ）2（ b，3）3（ a，1 ）4（ c，3 ）5（ a，1 ）6（ d，1 ）7游程長(zhǎng)度編碼表示柵格矩陣數(shù)據(jù)游程長(zhǎng)度編碼表示柵格矩陣數(shù)據(jù)游程編碼能否壓縮數(shù)據(jù)量，主要決定于柵格數(shù)據(jù)的性質(zhì)，通常可通過事先測(cè)試，估算圖層的數(shù)據(jù)冗余度re: re=1-q/mn 式中，q為圖層內(nèi)相鄰屬性值變化次數(shù)的累加和；m為圖層網(wǎng)格的行數(shù)；n為

10、圖層網(wǎng)格的列數(shù)。當(dāng)re的值大于1/5的情況下，表明柵格數(shù)據(jù)的壓縮可取得明顯的效果。其壓縮效果，可由壓縮比s=n/k來表征，即壓縮比的值愈大，表示壓縮效果愈明顯。特點(diǎn)：游程長(zhǎng)度編碼在柵格壓縮時(shí)，數(shù)據(jù)量沒有明顯增加，壓縮效率較高，且易于檢索，疊加合并等操作，運(yùn)算簡(jiǎn)單，適用于機(jī)器存儲(chǔ)容量小，數(shù)據(jù)需大量壓縮，而又要避免復(fù)雜的編碼解碼運(yùn)算增加處理和操作時(shí)間的情況。4.4.塊式編碼塊式編碼(block codes)(block codes)塊式編碼是將游程擴(kuò)大到兩維情況，把多邊形范圍劃分成若干具有同一屬性的正方形，然后對(duì)各個(gè)正方形進(jìn)行編碼。塊式編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置（行列號(hào)）、半徑和屬性代碼組成。m m

11、 r m m m m mm m r r m r m mm r r r r r r mm r r r r r r mm r r r r r r mm r r r r r r mm m r r r r r mm m m r r m m mm m r m m m m m1 2 3 4 5 6 7 8m m r r m r m mm r r r r r r mm r r r r r r mm r r r r r r mm r r r r r r mm m m r r m m mm m r r r r r mm m r m m m m m1 2 3 4 5 6 7 8m m r r m r m mm r

12、 r r r r r mm r r r r r r mm r r r r r r mm r r r r r r mm m m r r m m mm m r r r r r m1，1，2，m；1，3，1，r；1，4，1，m；1，5，1，m；1，6，1，m；1，7，2，m2，3，2，r；2，5，1，m；2，6，1，r3，1，1，m；3，2，1，r；3，5，3，r；3，8，1，m4，1，1，m；4，2，3，r;4，8，1，m5，1，1，m；5，8，1，m特點(diǎn)：塊碼具有可變的分辨率，即當(dāng)代碼變化小時(shí)圖塊大，就是說在區(qū)域圖斑內(nèi)部分辨率低；反之，分辨率高以小塊記錄區(qū)域邊界地段，以此達(dá)到壓縮的目的。因此塊碼

13、與游程長(zhǎng)度編碼相似，隨著圖形復(fù)雜程度的提高而降低效率，就是說圖斑越大，壓縮比越高；圖斑越碎，壓縮比越低。塊碼在合并、插入、檢查延伸性、計(jì)算面積等操作時(shí)有明顯的優(yōu)越性。然而在某些操作時(shí)，則必須把游程長(zhǎng)度編碼和塊碼解碼，轉(zhuǎn)換為基本柵格結(jié)構(gòu)進(jìn)行。5.5.差分映射法差分映射法所謂差分映射法，就是選擇某一參照值對(duì)有關(guān)柵格的屬性值進(jìn)行求差運(yùn)算，根據(jù)差值得到一個(gè)新的柵格數(shù)據(jù)層。參照值的選擇有多種方式：（1）分行選?。簞t可選為該行首列的屬性值，也可選為該行的 屬性平均值； （2）全區(qū)選?。簞t可選為首行首列的屬性值，也可選為全區(qū)的 屬性平均值。如下圖所示：1201201501501502002002001301

14、30170170170230230230135135135180180180250250140140140200200200200270145145145210210210210210柵格數(shù)據(jù)示例120 0 303030808080130 0 404040100 100 100135 0 0454545115 115140 0 060606060130145 0 06565656565數(shù)據(jù)差分映射結(jié)果行號(hào)第一列第一列第一列第一列第一列第一列第一列第一列前后前后前后前后前后前后前后前后11121212121212121222212121212121213222121212121212142221

15、21212121212252221212121212121總99105105105105105105106差分映射前后柵格數(shù)據(jù)記錄長(zhǎng)度對(duì)比結(jié)論：由上表可見，所需字節(jié)數(shù)由原來的79減少為 44，減少44.3%。6.6.四叉樹編碼四叉樹編碼(quadtree encoding)(quadtree encoding)四叉樹又稱四元樹或四分樹，是最有效的柵格數(shù)據(jù)壓縮編碼方法之一。四分樹將整個(gè)圖像區(qū)域逐步分解為一系列方形區(qū)域，且每一個(gè)方形區(qū)域具有單一的屬性。最小區(qū)域?yàn)橐粋€(gè)象元。區(qū)域分割原則： 將欲分解區(qū)域等分為四個(gè)象限，再根據(jù)各個(gè)象限的象元值是否單一決定要不要再分。如果單一則不再分割，否則同法再分，直到

16、所有象限的象元屬性值相同為止。(a) 四叉樹分割(a)(a)的的四叉樹四叉樹編碼編碼 其中最上面的那個(gè)結(jié)點(diǎn)叫做根結(jié)點(diǎn)，它對(duì)應(yīng)整個(gè)圖形。總共有4層結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)象限，如2層4個(gè)結(jié)點(diǎn)分別對(duì)應(yīng)于整個(gè)圖形的四個(gè)象限，排列次序依次為南西（sw）、南東（se）、北西（nw）和北東（ne），不能再分的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)（又稱葉子結(jié)點(diǎn)），可能落在不同的層上，該結(jié)點(diǎn)代表的子象限具有單一的代碼，所有終止結(jié)點(diǎn)所代表的方形區(qū)域覆蓋了整個(gè)圖形。從上到下，從左到右為葉子結(jié)點(diǎn)編號(hào)如圖所示，共有40個(gè)葉子結(jié)點(diǎn)，也就是原圖被劃分為40個(gè)大小不等的方形子區(qū)，圖的最下面的一排數(shù)字表示各子區(qū)的代碼。 由上面圖形的四叉樹分解可見

17、，四叉樹中象限的尺寸是大小不一的，位于較高層次的象限較大，深度小即分解次數(shù)少，而低層次上的象限較小，深度大即分解次數(shù)多，這反映了圖上某些位置單一地物分布較廣而另一些位置上的地物比較復(fù)雜，變化較大。正是由于四叉樹編碼能夠自動(dòng)地依照?qǐng)D形變化而調(diào)整象限尺寸，因此它具有極高的壓縮效率。采用四叉樹編碼時(shí)，為了保證四叉樹分解能不斷地進(jìn)行下去，要求圖像必須為 的柵格陣列，n為極限分割數(shù)，n+1為四叉樹的最大高度或最大層數(shù)，上圖為22的柵格，因此最多劃分三次，最大層數(shù)為4，對(duì)于非標(biāo)準(zhǔn)尺寸的圖像需首先通過增加背景的方法將圖像擴(kuò)充為 的圖像。 為了使計(jì)算機(jī)既能以最小的冗余存儲(chǔ)圖像對(duì)應(yīng)的四叉樹，又能方便地完成各種圖

18、形圖像操作，專家們已提出了多種編碼方式，下面介紹美國(guó)馬里蘭大學(xué)地理信息系統(tǒng)中采用的編碼方式，該方法記錄了終止結(jié)點(diǎn)（或葉子結(jié)點(diǎn)）的地址和值，值就是子區(qū)的代碼，其中地址包括兩個(gè)部分，共32位（二進(jìn)制），最右邊4位記錄該葉子結(jié)點(diǎn)的深度，即處于四叉樹的第幾層上，有了深度可以推知子區(qū)的大小；地址由從根結(jié)點(diǎn)到該葉子結(jié)點(diǎn)的路徑表示，0，1，2，3分別表示sw、se、nw、ne，從右邊第5位開始2n字節(jié)記錄這些方向。n2n2n2n2 如上圖表示的第六個(gè)結(jié)點(diǎn)深度為3，第一層處于sw象限，記為0；第二層處于ne象限，記為3，第三層處于nw象限，記為2，表示為二進(jìn)制為： 0000 000(22位)；001110（6

19、位）；0011（4位） 每層象限位置由兩位二進(jìn)制數(shù)表示，共6位，十進(jìn)制整數(shù)為227。這樣，記錄了各個(gè)葉子的地址，再記上相應(yīng)代碼值，就記錄了這個(gè)圖像，并可在此編碼基礎(chǔ)上進(jìn)行多種圖像操作。事實(shí)上，葉結(jié)點(diǎn)的地址可以直接由子區(qū)左下角的行列坐標(biāo)，按二進(jìn)制按位交錯(cuò)得到。如對(duì)于6號(hào)葉子結(jié)點(diǎn)，在以圖像左下角為原點(diǎn)的行列坐標(biāo)系中，其左下角行、列坐標(biāo)為（3，2），表示為二進(jìn)制分別為011和010，按位交錯(cuò)就是001110，正是6號(hào)地塊。特點(diǎn)：四叉樹編碼具有可變的分辨率，并且有區(qū)域性質(zhì)，壓縮數(shù)據(jù)靈活，許多運(yùn)算可以在編碼數(shù)據(jù)上直接實(shí)現(xiàn)，大大地提高了運(yùn)算效率，是優(yōu)秀的柵格壓縮編碼之一。u鏈?zhǔn)骄幋a的壓縮效率較高，已經(jīng)近矢

20、量結(jié)構(gòu)，對(duì)邊界的運(yùn)算比較方便，但不具有區(qū)域的性質(zhì)，區(qū)域運(yùn)算困難；u游程長(zhǎng)度編碼既可以在很大程度上壓縮數(shù)據(jù)，又最大限度地保留了原始柵格結(jié)構(gòu)，編碼解碼十分容易；u塊碼和四叉樹碼具有區(qū)域性質(zhì)，又具有可變的分辨率，有較高的壓縮效率，四叉樹編碼可以直接進(jìn)行大量圖形圖像運(yùn)算，效率較高，是很有前途的方法。幾種編碼的比較二、矢量數(shù)據(jù)結(jié)構(gòu)及其壓縮定義：通過記錄坐標(biāo)的方式盡可能精確地表示地理實(shí)體，即地理實(shí)體的形狀和位置是由一組所在的坐標(biāo)參考系中坐標(biāo)確定的。矢量數(shù)據(jù)結(jié)構(gòu)是人們較為習(xí)慣的一種表示空間數(shù)據(jù)的方法特點(diǎn)：定位明顯、屬性隱含，其定位是根據(jù)坐標(biāo)直接存儲(chǔ)的，而屬性則一般存于文件頭或數(shù)據(jù)結(jié)構(gòu)中某些特定的位置上，這種

21、特點(diǎn)使得其圖形運(yùn)算的算法總體上比柵格數(shù)據(jù)結(jié)構(gòu)復(fù)雜的多，有些甚至難以實(shí)現(xiàn)，當(dāng)然有些地方也有所便利和獨(dú)到之處，在計(jì)算長(zhǎng)度、面積、形狀和圖形編輯、幾何變換操作中，矢量結(jié)構(gòu)有很高的效率和精度，而在疊加運(yùn)算、鄰域搜索等操作時(shí)則比較困難。在gis中，地理實(shí)體的空間特征首先抽象為點(diǎn)、線、面、體四種基本類型，而這些特征可以用顏色、符號(hào)、注記來區(qū)分，并由圖例、圖符和描述性文本來解釋。矢量數(shù)據(jù)（矢量數(shù)據(jù)（1 1）矢量數(shù)據(jù)（矢量數(shù)據(jù)（2 2）矢量數(shù)據(jù)（矢量數(shù)據(jù)（3 3）矢量+柵格（1）矢量+柵格（2） 矢量數(shù)據(jù)結(jié)構(gòu)獲取方法矢量數(shù)據(jù)結(jié)構(gòu)獲取方法 (1) 手工數(shù)字化法； (2) 手扶跟蹤數(shù)字化法； (3) 數(shù)據(jù)結(jié)構(gòu)轉(zhuǎn)換

22、法。矢量數(shù)據(jù)基本類型矢量數(shù)據(jù)基本類型 ； (1) 點(diǎn) (2) 線 (3) 面 矢量數(shù)據(jù)基本類型矢量數(shù)據(jù)基本類型- -點(diǎn)點(diǎn) 點(diǎn)點(diǎn)是點(diǎn)狀物或者是可以用點(diǎn)是點(diǎn)狀物或者是可以用點(diǎn)( (由單獨(dú)一對(duì)由單獨(dú)一對(duì)坐標(biāo)定位）的一切地理或制圖實(shí)體，坐標(biāo)定位）的一切地理或制圖實(shí)體，有特定有特定的位置。圖件的比例尺決定了能否把現(xiàn)實(shí)世的位置。圖件的比例尺決定了能否把現(xiàn)實(shí)世界的現(xiàn)象表示為點(diǎn)特征界的現(xiàn)象表示為點(diǎn)特征。它有可能是點(diǎn)狀地物、面狀地物的中心點(diǎn)、線狀地它有可能是點(diǎn)狀地物、面狀地物的中心點(diǎn)、線狀地物的交點(diǎn)、定位點(diǎn)、注記等。物的交點(diǎn)、定位點(diǎn)、注記等。 例子：水基準(zhǔn)點(diǎn)、建筑物、井、觀測(cè)點(diǎn)、高程點(diǎn)例子：水基準(zhǔn)點(diǎn)、建筑物、井

23、、觀測(cè)點(diǎn)、高程點(diǎn) 在在gisgis中點(diǎn)有幾種類型。線的起點(diǎn)、終點(diǎn)、交點(diǎn)（三條中點(diǎn)有幾種類型。線的起點(diǎn)、終點(diǎn)、交點(diǎn)（三條以上坐標(biāo)鏈的交匯點(diǎn)）、面的首尾點(diǎn)我們稱之為結(jié)點(diǎn)以上坐標(biāo)鏈的交匯點(diǎn)）、面的首尾點(diǎn)我們稱之為結(jié)點(diǎn)（nodenode），而線的中間部分稱為中間點(diǎn)（角點(diǎn)），而線的中間部分稱為中間點(diǎn)（角點(diǎn)vertexvertex）。）。 實(shí)體點(diǎn)實(shí)體點(diǎn)(entity point)(entity point)：用來代表一個(gè)實(shí)體；：用來代表一個(gè)實(shí)體； 注記點(diǎn)注記點(diǎn)(text point)(text point)：用于定位注記；：用于定位注記； 內(nèi)點(diǎn)內(nèi)點(diǎn)(label point)(label point)：用于

24、記錄多邊形的屬性，存：用于記錄多邊形的屬性，存在于多邊形內(nèi)；在于多邊形內(nèi)； 結(jié)點(diǎn)結(jié)點(diǎn)(node)(node)：表示線的終點(diǎn)和起點(diǎn)、：表示線的終點(diǎn)和起點(diǎn)、交點(diǎn)交點(diǎn)； 中間點(diǎn)中間點(diǎn)( (角點(diǎn)，角點(diǎn)，vertexvertex) )：表示線段和弧段的內(nèi)部點(diǎn)。：表示線段和弧段的內(nèi)部點(diǎn)。 矢量數(shù)據(jù)基本類型矢量數(shù)據(jù)基本類型- -點(diǎn)點(diǎn)線有方向，線有方向，兩個(gè)結(jié)點(diǎn)之間的線又叫弧段（兩個(gè)結(jié)點(diǎn)之間的線又叫弧段（arcarc）。）?；《翁卣骺捎脕矶ㄎ缓兔枋鰞牲c(diǎn)之間連線的地理弧段特征可用來定位和描述兩點(diǎn)之間連線的地理信息信息。 線線是對(duì)線狀地物或地物運(yùn)動(dòng)軌跡的全部或部分的是對(duì)線狀地物或地物運(yùn)動(dòng)軌跡的全部或部分的描述，可

25、以定義為由直線元素組成的各種線性要素，描述，可以定義為由直線元素組成的各種線性要素，直線元素由兩對(duì)以上的坐標(biāo)定義。最簡(jiǎn)單的線實(shí)體只直線元素由兩對(duì)以上的坐標(biāo)定義。最簡(jiǎn)單的線實(shí)體只存儲(chǔ)它的起止點(diǎn)坐標(biāo)、屬性、顯示符等有關(guān)數(shù)據(jù)。存儲(chǔ)它的起止點(diǎn)坐標(biāo)、屬性、顯示符等有關(guān)數(shù)據(jù)。 矢量數(shù)據(jù)基本類型矢量數(shù)據(jù)基本類型- -線線由一系列坐標(biāo)點(diǎn)表示，有以下特征：由一系列坐標(biāo)點(diǎn)表示，有以下特征： 實(shí)體長(zhǎng)度：從起點(diǎn)到終點(diǎn)的總長(zhǎng)；實(shí)體長(zhǎng)度：從起點(diǎn)到終點(diǎn)的總長(zhǎng)； 彎曲度：用于表示象道路拐彎時(shí)彎曲的程度；彎曲度：用于表示象道路拐彎時(shí)彎曲的程度； 方向性：如水流從上游到下游，公路則有單雙向之方向性：如水流從上游到下游，公路則有單

26、雙向之分；分；線實(shí)體包括：線段、邊界、鏈、網(wǎng)絡(luò)、多邊形線等。線實(shí)體包括：線段、邊界、鏈、網(wǎng)絡(luò)、多邊形線等。 矢量數(shù)據(jù)基本類型矢量數(shù)據(jù)基本類型- -線線復(fù)雜的多邊形內(nèi)可以有復(fù)雜的多邊形內(nèi)可以有“島（洞）島（洞）”（一種特殊的?。ㄒ环N特殊的弧段，這種弧段坐標(biāo)鏈頭尾相接，獨(dú)立圍成一個(gè)封閉的段，這種弧段坐標(biāo)鏈頭尾相接，獨(dú)立圍成一個(gè)封閉的區(qū)域?；《蔚亩它c(diǎn)總是結(jié)點(diǎn)，而島弧段端點(diǎn)并非是三區(qū)域。弧段的端點(diǎn)總是結(jié)點(diǎn)，而島弧段端點(diǎn)并非是三條或三條以上坐標(biāo)鏈的交匯點(diǎn)，這種端點(diǎn)稱為島結(jié)條或三條以上坐標(biāo)鏈的交匯點(diǎn)，這種端點(diǎn)稱為島結(jié)點(diǎn)）。點(diǎn)）。 面（多邊形面（多邊形polygonpolygon）是對(duì)面狀地理實(shí)體的表示，）

27、是對(duì)面狀地理實(shí)體的表示，由一個(gè)封閉的坐標(biāo)點(diǎn)序列外加內(nèi)點(diǎn)表示。但由一個(gè)封閉的坐標(biāo)點(diǎn)序列外加內(nèi)點(diǎn)表示。但多邊形多邊形矢量編碼，不但要標(biāo)識(shí)位置和屬性，更重要的是表矢量編碼，不但要標(biāo)識(shí)位置和屬性，更重要的是表達(dá)拓?fù)涮卣鬟_(dá)拓?fù)涮卣? ,如形狀、鄰域和層次結(jié)構(gòu)等。多邊形由如形狀、鄰域和層次結(jié)構(gòu)等。多邊形由一條或一條以上首尾相連的弧段組成。一個(gè)弧段總一條或一條以上首尾相連的弧段組成。一個(gè)弧段總是被兩個(gè)而且只被兩個(gè)多邊形所共有。是被兩個(gè)而且只被兩個(gè)多邊形所共有。 矢量數(shù)據(jù)基本類型矢量數(shù)據(jù)基本類型- -面（多邊形）面（多邊形）多邊形有以下特征：多邊形有以下特征： 面積范圍；面積范圍； 周長(zhǎng)；周長(zhǎng)； 獨(dú)立性或與其

28、它地物相鄰：如北京及周邊省市；獨(dú)立性或與其它地物相鄰：如北京及周邊省市；內(nèi)部區(qū)域內(nèi)部區(qū)域簡(jiǎn)單多邊形簡(jiǎn)單多邊形復(fù)雜多邊形復(fù)雜多邊形 矢量數(shù)據(jù)基本類型矢量數(shù)據(jù)基本類型- -面（多邊形）面（多邊形）矢量數(shù)據(jù)的壓縮矢量數(shù)據(jù)的壓縮包括兩個(gè)方面的內(nèi)容：(1)在不擾亂拓?fù)潢P(guān)系的前提下，對(duì)采樣點(diǎn)數(shù)據(jù)進(jìn)行合理的抽稀；(2)對(duì)矢量坐標(biāo)數(shù)據(jù)重新進(jìn)行編碼，以減少所需要的存儲(chǔ)空間。注注: :矢量數(shù)據(jù)的壓縮往往是不可逆的，數(shù)據(jù)壓縮后數(shù)據(jù)量變小了， 但數(shù)據(jù)的精度降低了。矢量數(shù)據(jù)壓縮的目的是刪除冗余數(shù)據(jù)，減少數(shù)據(jù)的存貯量，節(jié)省存貯空間，加快后繼處理的速度。下面介紹幾種常用的矢量數(shù)據(jù)的壓縮算法，以及它們之間的異同點(diǎn)。1.1.間

29、隔取點(diǎn)法：間隔取點(diǎn)法：每隔k個(gè)點(diǎn)取一點(diǎn)，或舍去那些離已選點(diǎn)比規(guī)定距離更近的點(diǎn)，但首、末點(diǎn)一定要保留。如下圖所示。特點(diǎn)：這種方法可大量壓縮數(shù)字化儀用連續(xù)方法獲取的點(diǎn)列中的點(diǎn)、曲率顯著變化的點(diǎn)，但不一定能恰當(dāng)?shù)乇Ａ舴较蛏锨曙@著變化的點(diǎn)。由(a)舍去每?jī)牲c(diǎn)中一點(diǎn)得(a)和由(b)的僅僅保留與已選點(diǎn)距離超過臨界值的點(diǎn)得(b)(a)(a)臨界值(b)(b)2.2.垂距法和偏角法垂距法和偏角法這兩種方法都是按垂距或偏角的限差，選取符合或超過限差的點(diǎn)，其過程如圖所示。垂 距 算 法4123123412341234124原來的線對(duì)點(diǎn)2測(cè)試距離大于規(guī)定的限差2點(diǎn)保留對(duì)點(diǎn)3測(cè)試距離大于規(guī)定的限差3點(diǎn)舍去化簡(jiǎn)后的

30、線限差4123123412341234124原來的線對(duì)點(diǎn)2測(cè)試角度大于規(guī)定的限差2點(diǎn)保留對(duì)點(diǎn)3測(cè)試角度大于規(guī)定的限差3點(diǎn)舍去化簡(jiǎn)后的線限差偏 角 算 法這兩種方法雖然不能同時(shí)考慮相鄰點(diǎn)間的方向和距離，且有可能舍去不該舍去的點(diǎn)，但較前一種方法有進(jìn)步。3.3.道格拉斯道格拉斯普克法普克法(douglaspeucker)(douglaspeucker) 道格拉斯普克法示意圖 基本思路是：對(duì)每一條曲線的首末點(diǎn)虛連一條直線，求所有點(diǎn)與直線的距離，并找出最大距離值dmax，用dmax與限差d相比：若dmaxd，這條曲線上的中間點(diǎn)全部舍去；若dmaxd，保留dmax對(duì)應(yīng)的坐標(biāo)點(diǎn)，并以該點(diǎn)為界，把曲線分為兩部

31、分，對(duì)這兩部分重復(fù)使用該方法。4.4.光欄法光欄法 光欄法原理圖示 光欄法的基本思想是：定義一個(gè)扇形區(qū)域，通過判斷曲線上的點(diǎn)在扇形外還是在扇形內(nèi)，確定保留還是舍去。設(shè)曲線上的點(diǎn)列為pi，i1，2，n，光欄口經(jīng)為d，可根據(jù)壓縮量的大小自己定義，則光欄法的實(shí)施步驟可描述為： 1、連接p1和p2點(diǎn)，過p2點(diǎn)作一條垂直于p1p2的直線，在該垂線上取兩點(diǎn)a1和a2，使a1p2a2p2d2，此時(shí)a1和a2為“光欄”邊界點(diǎn)，p1與a1、p1與a2的連線為以p1為頂點(diǎn)的扇形的兩條邊，這就定義了一個(gè)扇形(這個(gè)扇形的口朝向曲線的前進(jìn)方向，邊長(zhǎng)是任意的)。通過p1并在扇形內(nèi)的所有直線都具有這種性質(zhì)，即p1p2上各點(diǎn)到這些直線的垂距