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

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

4、域的格網(wǎng)柵格數(shù)據(jù)的獲取柵格數(shù)據(jù)的獲取 1.遙感方法獲取(航天與航空)；2.圖片掃描獲取(紙介質(zhì)的地圖等掃描)；3.矢量數(shù)據(jù)轉(zhuǎn)換而來；4.由平面上行距,列距固定的點抽樣而來主要包括: (1)中心歸屬法 (2)長度占優(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é)省空間形式簡單形式簡單方便制圖方便制圖柵格數(shù)據(jù)的壓縮算法柵格數(shù)據(jù)文件記錄有3個基本方式：基于像元、基于層和基于面域。這三種方式都離不開對像元坐標(biāo)和屬性的記錄。因此基于柵格的空間數(shù)據(jù)壓縮的實質(zhì)是研究柵格數(shù)據(jù)的編碼，通過編碼盡量減少像元數(shù)量的存儲。其方法有三大類：（1）從減少記錄像元的數(shù)量入手； （2）從減少像元的記錄信息量入手； （3）前兩者的結(jié)合。柵格數(shù)據(jù)的壓縮分為無損壓縮技術(shù)和有損壓縮技術(shù)。（1）無損壓縮技術(shù)是指壓縮過程中沒有任何信息損失，通過解碼操作可以完全恢復(fù)原來的信息；（2）信息有損壓縮是指為了提高壓縮效率

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

7、des） 鏈?zhǔn)骄幋a又稱為弗里曼鏈碼freeman或邊界鏈碼。多邊形邊界可以表示為：由某一原點開始并按某些基本方向確定的單位矢量鏈?；痉较蚩梢远椋簴|=0，東南=1，南=2，西南=3，西=4，西北=5，北=6，東北=7，8個基本方向。 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例子：如果再確定原點為像元(10，1)，則該多邊形邊界按順時針方向的鏈?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)點：優(yōu)點：鏈?zhǔn)竭叴a可以有效地壓縮柵格數(shù)據(jù)，而且對于估算面積、長度、轉(zhuǎn)折方向的凹凸度等運算十分方便，比較適合于存儲圖形數(shù)據(jù)。缺點：缺點：對邊界進行合并和插入等修改編輯工作比較困難，對局部的修改將改變整體結(jié)構(gòu)，效率較低，而且由于鏈碼以每個區(qū)域為單位存儲邊界，相鄰區(qū)域的邊界將被重復(fù)存儲而產(chǎn)生冗余。3.3.游程長度編碼（游程長度編碼（run-length codesrun-length codes）游程長度編碼是柵格數(shù)據(jù)壓縮的重要編碼方法。游程指相鄰?fù)稻W(wǎng)格的數(shù)量，游程長度編碼結(jié)構(gòu)是逐行將相鄰?fù)档木W(wǎng)格合并記錄合并后網(wǎng)格的值及合并網(wǎng)

9、格的長度，其目的是壓縮柵格數(shù)據(jù)量，消除數(shù)據(jù)間的冗余。游程長度編碼結(jié)構(gòu)的建立方法是：將柵格矩陣的數(shù)據(jù)序列x1,x2,xn，映射為相應(yīng)的二元組序列（ai,pi）,i=1,2,k,且kn。其中，a為屬性值，p為游程，k為游程序號。 面域柵格矩陣結(jié)構(gòu)二元映射序號二元組序列1（a，2 ）2（ b，3）3（ a，1 ）4（ c，3 ）5（ a，1 ）6（ d，1 ）7游程長度編碼表示柵格矩陣數(shù)據(jù)游程長度編碼表示柵格矩陣數(shù)據(jù)游程編碼能否壓縮數(shù)據(jù)量，主要決定于柵格數(shù)據(jù)的性質(zhì)，通常可通過事先測試，估算圖層的數(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來表征，即壓縮比的值愈大，表示壓縮效果愈明顯。特點：游程長度編碼在柵格壓縮時，數(shù)據(jù)量沒有明顯增加，壓縮效率較高，且易于檢索，疊加合并等操作，運算簡單，適用于機器存儲容量小，數(shù)據(jù)需大量壓縮，而又要避免復(fù)雜的編碼解碼運算增加處理和操作時間的情況。4.4.塊式編碼塊式編碼(block codes)(block codes)塊式編碼是將游程擴大到兩維情況，把多邊形范圍劃分成若干具有同一屬性的正方形，然后對各個正方形進行編碼。塊式編碼的數(shù)據(jù)結(jié)構(gòu)由初始位置（行列號）、半徑和屬性代碼組成。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特點：塊碼具有可變的分辨率，即當(dāng)代碼變化小時圖塊大，就是說在區(qū)域圖斑內(nèi)部分辨率低；反之，分辨率高以小塊記錄區(qū)域邊界地段，以此達到壓縮的目的。因此塊碼

13、與游程長度編碼相似，隨著圖形復(fù)雜程度的提高而降低效率，就是說圖斑越大，壓縮比越高；圖斑越碎，壓縮比越低。塊碼在合并、插入、檢查延伸性、計算面積等操作時有明顯的優(yōu)越性。然而在某些操作時，則必須把游程長度編碼和塊碼解碼，轉(zhuǎn)換為基本柵格結(jié)構(gòu)進行。5.5.差分映射法差分映射法所謂差分映射法，就是選擇某一參照值對有關(guān)柵格的屬性值進行求差運算，根據(jù)差值得到一個新的柵格數(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é)果行號第一列第一列第一列第一列第一列第一列第一列第一列前后前后前后前后前后前后前后前后11121212121212121222212121212121213222121212121212142221

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

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

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

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

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

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

21、特點使得其圖形運算的算法總體上比柵格數(shù)據(jù)結(jié)構(gòu)復(fù)雜的多，有些甚至難以實現(xiàn)，當(dāng)然有些地方也有所便利和獨到之處，在計算長度、面積、形狀和圖形編輯、幾何變換操作中，矢量結(jié)構(gòu)有很高的效率和精度，而在疊加運算、鄰域搜索等操作時則比較困難。在gis中，地理實體的空間特征首先抽象為點、線、面、體四種基本類型，而這些特征可以用顏色、符號、注記來區(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) 點 (2) 線 (3) 面 矢量數(shù)據(jù)基本類型矢量數(shù)據(jù)基本類型- -點點 點點是點狀物或者是可以用點是點狀物或者是可以用點( (由單獨一對由單獨一對坐標(biāo)定位）的一切地理或制圖實體，坐標(biāo)定位）的一切地理或制圖實體，有特定有特定的位置。圖件的比例尺決定了能否把現(xiàn)實世的位置。圖件的比例尺決定了能否把現(xiàn)實世界的現(xiàn)象表示為點特征界的現(xiàn)象表示為點特征。它有可能是點狀地物、面狀地物的中心點、線狀地它有可能是點狀地物、面狀地物的中心點、線狀地物的交點、定位點、注記等。物的交點、定位點、注記等。 例子：水基準(zhǔn)點、建筑物、井、觀測點、高程點例子：水基準(zhǔn)點、建筑物、井

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

24、記錄多邊形的屬性，存：用于記錄多邊形的屬性，存在于多邊形內(nèi)；在于多邊形內(nèi)； 結(jié)點結(jié)點(node)(node)：表示線的終點和起點、：表示線的終點和起點、交點交點； 中間點中間點( (角點，角點，vertexvertex) )：表示線段和弧段的內(nèi)部點。：表示線段和弧段的內(nèi)部點。 矢量數(shù)據(jù)基本類型矢量數(shù)據(jù)基本類型- -點點線有方向，線有方向，兩個結(jié)點之間的線又叫弧段（兩個結(jié)點之間的線又叫弧段（arcarc）。）。弧段特征可用來定位和描述兩點之間連線的地理弧段特征可用來定位和描述兩點之間連線的地理信息信息。 線線是對線狀地物或地物運動軌跡的全部或部分的是對線狀地物或地物運動軌跡的全部或部分的描述，可

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

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

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

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

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

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

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