地理空間數據的獲取與處理第三部分

主要內容第六章空間數據的處理方法第六章空間數據的處理方法◆圖形屏幕編輯的基本操作算法介紹糾正數據采集錯誤的重要手段——圖形編輯的基本功能、要求。◆空間數據拓撲關系的自動生成介紹矢量數據拓撲關系建立的基本步驟和要點。◆空間數據的壓縮編碼方法介紹矢量數據和柵格數據的壓縮處理。◆空間數據的格式轉換◆矢量和柵格數據的轉換6.1圖形屏幕編輯的基本操作算法點的捕捉線的捕捉面的捕捉圖形編輯的關鍵是點、線、面的捕捉，即如何根據光標的位置找到需要編輯的要素，以及圖形編輯的數據組織。點的捕捉設光標點為A(x,y)，圖幅上某一點狀要素的坐標為S(X，Y)，則可設一捕捉半徑D(通常為3～5個象素)。d<D則選中，若有多個點，則要求出距A(x,y)的最近點。線的捕捉設光標點坐標為S(x,y)，D為捕捉半徑，線的坐標為(x1,y1),(x2,y2),…(xn,yn)。通過計算S到該線的每個直線段的距離di(如左圖所示)，若min(d1,d2,…dn-1)＜D，則認為光標S捕捉到了該條線。在計算前，用最小矩形，跳過圖右的線條。?S(x,y)(X1,Y2)(X1,Y)(X1,Y’)面的捕捉面的捕捉實際上就是判斷光標點S(x,y)是否在多邊形內，若在多邊形內則說明捕捉到。判斷點是否在多邊形內的算法主要有垂線法或轉角法。垂線法先進行圖右的判斷（在線框內外），再做奇偶點數的判斷。奇在內，偶在外。垂線、水平線、斜線的結果均相同，垂線或水平線運算方便。對于點在面的邊界上，可以對點的坐標加微量解決。若精度要求高，不允許加微量，可以先解決點是否在面邊界的判斷，再使用垂線法。6.2空間數據拓撲關系的自動生成歐拉定理點線拓撲關系的建立多邊形矢量數據拓撲關系自動建立多數情況下拓撲關系的建立可由GIS軟件自動生成。特殊情況下，需要人工對拓撲關系進行人工修改，如建立管網或路網數據的分析網絡時，就需要對結點、管段的方向等進行編輯。掃描后的柵格數據矢量化后的數字線劃圖矢量數據的常見錯誤公共邊界的處理

12211矢量數據拓撲關系在空間數據的查詢與分析中非常重要，矢量數據拓撲關系自動建立的算法是GIS中的關鍵算法之一。歐拉定理對于多邊形圖形，n、a、b分別表示結點數、弧段數、多邊形數則：c=n-a+b或c+a=n+bc+弧=點+面c為常數，其取值為：c=2包含外多邊形c=1不包含外多邊形點線拓撲關系的建立記錄結點——弧段表弧段——結點表弧段入庫時，檢測結點表，若存在記錄點號；否則產生新的點號，再記錄多邊形的四種基本圖形

獨立公共邊島復合多邊形矢量數據拓撲關系的自動建立鏈的組織結點匹配閉合檢查建立多邊形概念過程島的判斷確定多邊形的屬性鏈的組織1找出在鏈的中間相交(左圖)，而不是在端點相交(右圖)的情況，自動切成新鏈。鏈的組織2原來的兩條鏈變成了四條鏈。再把鏈按一定順序存儲，如按最大或最小的x或y坐標的順序，這樣查找和檢索都比較方便，然后把鏈按順序編號。鏈的生成結點匹配結點匹配是指把一定限差內的鏈的端點作為一個結點，其坐標值取多個端點的平均值。然后，對結點順序編號。X=(x1+x2+x3)/3;Y=(y1+y2+y3)/3去除懸線

閉合檢查檢查多邊形是否閉合可以通過判斷一條鏈的端點是否有與之匹配的端點來進行。懸掛鏈不需參加多邊形拓撲，可以作一標記，使之不參加下一階段拓撲建立多邊形的工作。建立多邊形概念1順時針方向構多邊形。順時針方向構多邊形是指多邊形在鏈的右側概念2最靠右邊的鏈最靠右邊的鏈是指從鏈的一個端點出發，在這條鏈的方向上最右邊的第一條鏈。如圖，a的最右邊的鏈為d。找最靠右邊的鏈可通過計算鏈的方向和夾角實現求最右線段的方法1、從起始點Pi出發，到達結點P0，設方位角P0Pi為起始方位角f1；2、求終結點P0到其他節點的方位角：f2f3…….fn；3、用f(i+1)-f(i)求解夾角P(i)P0P(i+1)，，形成夾角串jj1j2……jn；4、jj1j2……jn中最大者為最右方向，其鏈為下一條發展鏈。概念3用多邊形面積判斷方向用面積值判斷方向（需將絕對號去除）建立多邊形的基本過程1、順序取一個結點為起始結點，至該點上所有鏈均用2次止；取過該結點的任一條鏈作為起始鏈。2、取這條鏈的另一結點，找這個結點上，靠這條鏈最右邊的鏈，作為下一條鏈。3、是否回到起點：是，已形成一多邊形，記錄之，并轉4；否，轉2。4、取起始點上開始的，剛才所形成多邊形的最后一條邊反向作為新的起始鏈，轉2；若這條鏈已用過兩次，即已成為兩個多邊形的邊，則轉1。島的判斷島的判斷即指找出多邊形互相包含的情況，即尋找多邊形的連通邊界。找出所有比該正面積多邊形面積小的負面積多邊形；用外接矩形法去掉不可能包含的多邊形；取負面積多邊形上的一點，看是否在正面積多邊形內。

單多邊形被追蹤兩次

p1p2p3記錄多邊形多邊形的記錄格式可由節點或鏈構成ID，n，[P]，AID，n，[L]，A確定多邊形的屬性在追蹤出每個多邊形的坐標后，經常需確定該多邊形的屬性。如果多邊形有內點，則可以把內點與多邊形匹配后，把內點的屬性賦于多邊形。思考：若無內點，能否記錄多邊形的屬性？如果沒有內點，則必須通過人機交互，對每個多邊形賦屬性。拓撲處理注意事項1）可以根據實際數據的情況和使用目的，選擇不同的拓撲處理選項組合；2）如果需要進行拓撲錯誤檢查，必須選擇弧段求交，弧段求交是進行后續拓撲處理的基礎。3）線數據集經過拓撲處理后，原來數據集的線對象將會在各線對象交點處被打斷，而生成新的線對象，如用戶還需繼續使用原來的線數據集，可以在拓撲處理前對線數據集先進行備份，以保護原數據集；4）弧段求交操作得到的是一個真正的節點，而合并臨近點操作有時卻得到一個假節點，因此合并臨近點操作后可能還要繼續做合并假節點操作；5）線數據集必須關閉才能進行拓撲處理；6）拓撲處理的結果與拓撲容限大小的設置有關。中間數據集重名延伸長懸線1延伸長懸線26.3空間數據的壓縮編碼方法矢量數據的壓縮矢量數據壓縮的目的是刪除冗余數據，減少數據的存貯量，節省存貯空間，加快后繼處理的速度。柵格數據的壓縮柵格數據壓縮的目的是刪除冗余數據，減少數據的存貯量，節省存貯空間，但在處理時會增大運算量。是用時間換空間。矢量數據的壓縮道格拉斯——普克法(Douglas—Peucker)道格拉斯——普克法對每一條曲線的首末點虛連一條直線，求所有點與直線的距離，并找出最大距離值dmax。用dmax與限差D相比：若dmax＜D，這條曲線上的中間點全部舍去；若dmax≥D，保留dmax對應的坐標點，并以該點為界，把曲線分為兩部分，對這兩部分重復使用該方法垂距法每次順序取曲線上的三個點，計算中間點與其它兩點連線的垂線距離d，并與限差D比較。若d＜D，則中間點去掉；若d≥D，則中間點保留。然后順序取下三個點繼續處理，直到這條線結束。光欄法定義一個扇形區域，通過判斷曲線上的點在扇形外還是在扇形內，確定保留還是舍去。設曲線上的點列為｛pi｝，i＝1，2，…，n，光欄口經d可根據壓縮量確定幾種方法的比較標準既能精確地表示圖形，又能最大限度地淘汰不必要的點，那就是一種好的算法。可以依據簡化后曲線的總長度、總面積、坐標平均值等與原始曲線的相應數據的對比來判別。分析大多數情況下道格拉斯——普克法的壓縮算法較好，但必須在對整條曲線數字化完成后才能進行，且計算量較大；光欄法的壓縮算法也很好，并且可在數字化時實時處理，每次判斷下一個數字化的點，且計算量較小；垂距法算法簡單，速度快，但有時會將曲線的彎曲極值點p值去掉而失真。柵格數據的壓縮JPG27KBMP529K柵格的壓縮和編碼直接柵格編碼鏈碼(chainEncoding)游程長編碼(Run_lengthEncoding)塊碼四叉樹編碼(quarter_treeEncoding)直接柵格編碼將柵格數據當成數據矩陣，逐行(或逐列)記錄代碼，每行都從左到右記錄，也可奇數行從左到右，偶數行從右到左。為了特定的目的還可采用其他特殊的順序。圖右：AAAAABBBAABBAABB同時記錄行、列數特點是處理方便，但沒有壓縮。AAAAABBBAABBAABB直接柵格編碼0，2，2，5，5，5，5，5；2，2，2，2，2，5，5，5；2，2，2，2，3，3，5，5；0，0，2，3，3，3，5，5；0，0，3，3，3，3，5，3；0，0，0，3，3，3，3，3；0，0，0，0，3，3，3，3；0，0，0，0，0，3，3，3。柵格數據的組織方法無論如何取值，在計算機中，如果矩陣的每個元素用一個雙字節表示，則一個圖層的全柵格數據所需要的存儲空間為m（行）×n（列）×2（字節）。如：一個面積為100km2的區域，如果網格邊長取為1m，每個網格用一個雙字節表示，則一個圖層的要素就占用？兆字節的存儲空間。200因此，柵格數據的壓縮是柵格數據結構要解決的重要任務。是將原始柵格陣列中屬性值相同的連續若干個柵格單元映射為一個游程，每個游程的數據結構為（A，P）整數對。其中，A代表屬性值，P代表該游程最右端柵格的列號。游程長度(行程)編碼按行掃描，將相鄰等值的象元合并記錄。右圖編碼為A4A1B3A2B2A2B2。若在行與行之間不間斷地連續編碼，則為A5B3A2B2A2B2。對于游程長度編碼，區域越大，數據的相關性越強，則壓縮越大。其特點是，壓縮效率較高，疊加、合并等運算簡單，編碼和解碼運算快AAAAABBBAABBAABB游程長度編碼只在各行（或列）數據的代碼發生變化時依次記錄該代碼以及相同代碼重復的個數；沿行方向進行編碼：(0，1），（2，2），（5，5）；（2，5），（5，3）；（2，4），（3，2），（5，2）；（0，2），（2，1），（3，3），（5，2）；（0，2），（3，4），（5，1），（3，1）；（0，3），（3，5）；（0，4），（3，4）；（0，5），（3，3）。游程長度編碼逐個記錄各行（或列）代碼發生變化的位置和相應代碼（1,0），（2,2），（4,5）（1,2），（6,5）（1,2），（5,3），（7,5）（1,0），（3,2），（4,3），（7,5）（1,0），（3,3），（7,5），（8,3）（1,0），（4,3）（1,0），（5,3）（1,0），（6,3）四叉樹編碼

四叉樹編碼是最有效的柵格數據壓縮編碼方法之一，在GIS中有廣泛的應用。其基本思路為：將2n×2n象元組成的圖像(不足的用背景補上)所構成的二維平面按四個象限進行遞歸分割，直到子象限的數值單調為止，最后得到一顆四分叉的倒向樹，該樹最高為n級。用一倒立樹表示這種分割和分割結果。根：整個區域高：深度、分幾級，幾次分割葉：不能再分割的塊樹叉：還需分割的塊每個樹叉均有4個分叉，叫四叉樹。四叉樹編碼四叉樹分解，各子象限大小不完全一樣，但都是同代碼柵格單元組成的子塊，其中最上面的一個結點叫做根結點，它對應于整個圖形。不能再分的結點稱為葉子結點，可能落在不同的層上，該結點代表子象限單一的代碼，所有葉子結點所代表的方形區域覆蓋了整個圖形。從上到下，從左到右為葉子結點編號，最下面的一排數字表示各子區的代碼。為了保證四叉樹分解能不斷的進行下去，要求圖形必須為2n×2n的柵格陣列。n為極限分割次數，n＋1是四叉樹最大層數或最大高度8*8四叉樹編碼①②③④⑤⑥⑦⑧⑨⑩1112131415161718192021222324252627282930313233363738393435400000333033333530022232222022225255533355西南東南西北東北四叉樹編碼法的優點：1）容易而有效地計算多邊形的數量特征；2）陣列各部分的分辯率是可變的，邊界復雜部分四叉樹較高即分級多，分辯率也高，而不需表示許多細節的部分則分級少，分辯率低，因而既可精確表示圖形結構又可減少存貯量；3）柵格到四叉樹及四叉樹到簡單柵格結構的轉換比其它壓縮方法容易；4）多邊形中嵌套異類小多邊形的表示較方便。練習0231練習由直接柵格編碼轉換成四叉樹編碼的樹狀表示333331111111333331111111333111144441333111444444332221114441322221111411222221111111222221111111222222111111222222111111答案3331111031331111411311441332221444103211141122211122221110210000000000用Morton碼表示四叉樹地址Morton碼表示的葉結點Morton碼的轉換Morton碼—葉節點碼葉節點碼—Morton碼Morton碼—行列值行列值—Morton碼四叉樹地址和Morton碼Morton碼—葉節點碼將十進制Morton碼轉為二進制碼39——100111將二進制Morton碼每二位轉為十進制數100111213葉節點碼—Morton碼將葉節點碼逐位轉為二進制213100111將二進制葉節點碼轉為Morton碼100111——391*25+0*24+0*23+1*22+1*21+1*2032+0+0+4+2+1=39Morton碼—行列值將Morton碼39轉為二進制100111將二進制的Morton碼奇偶分開100111101011將奇偶分別變成十進制的行列10101153行列值—Morton碼將十進制的行列分別變成二進制53101011將二進制的行列值奇偶合并得Morton碼101011100111將二進制Morton碼變為十進制1*25+0*24+0*23+1*22+1*21+1*2032+0+0+4+2+1=39十進制地址碼——Morton碼例如，對于第5行、第7列的Moton碼為：行數=5(0101)；列數=7(0111)

Morton=00110111=55這樣，在一個2n×2n的圖像中，每個像元點都給出一個Morton碼。十進制和二進制的轉換十進制轉二進制：

用2輾轉相除至結果為0，

將余數從下向上倒序寫就是二進制值例如302轉二進制

302/2=151余0

151/2=75余1

75/2=37余1

37/2=18余1

18/2=9余0

9/2=4余1

4/2=2余0

2/2=1余01/2=0余1

故十進制302=二進制100101110二進制轉十進制

從最后一位開始算，依次列為第0、1、2...位、第n位的數（0或1）乘以2的n次方，得到的結果相加就是十進制值。例如:01101011.轉十進制:

第0位:1乘2的0次方=1

1乘2的1次方=2

0乘2的2次方＝0

1乘2的3次方＝8

0乘2的4次方＝0

1乘2的5次方＝32

1乘2的6次方＝64

0乘2的7次方＝0

然后：1＋2＋0＋8＋0＋32＋64＋0＝107．

二進制01101011＝十進制107十進制和二進制的轉換6.4空間數據的格式轉換數據格式轉換的內容空間定位、空間關系、屬性信息轉換的方式通過外部數據交換文件轉換通過標準空間數據文件轉換通過標準API函數轉換6.5矢量和柵格數據的轉換矢量─柵格轉換由于矢量數據的點到柵格數據的點只是簡單的坐標變換，線和面(多邊形)的矢量數據向柵格數據的轉換是主要內容。柵格─矢量轉換柵格數據到矢量數據轉換的一般過程為：二值化、二值圖像的預處理、細化、追蹤、拓撲化矢量─柵格轉換點的柵格化IJ、xyI=1+[(y頂-y)/Dy]；J=1+[x/Dx]

21,12A:1.7,4.5B:19,10.6y頂=12Dx=Dy=3yA=1+[(12-4.5)/3]=1+[2.5]=3xA=1+[1.7/3]=1+[0.56]=1線的柵格化方法

線是由多個直線段組成的，因此，線的柵格化的核心就是直線段如何由矢量數據轉換為柵格數據。⑴DDA法(數字微分分析法)直線段的兩端點坐標轉換到柵格數據的坐標系后為(xA,yA),(xB,yB)。設(xA,yA),(xB,yB)與柵格網的交點為(xi,yi)，則:直線生成算法直線生成:求與直線段充分接近的像素集當直線作為一系列像素位置生成時產生的階梯效果天津大學計算機科學與技術學院直線方程直線的斜率截矩方程:給定線段的兩個端點,可以計算斜率m和y軸截矩b:生成直線的常用算法 均假定所畫直線的斜率k∈[0，1]。DDA畫線算法 DDA（DigitalDifferentialAnalyzer）畫線算法也稱數值微分法，是一種增量算法。它的算法實質是用數值方法解微分方程，通過同時對x和y各增加一個小增量，計算下一步的x、y值。DDA算法數值微分算法(DigitalDifferentialAnalyzer)條件：待掃描轉換的直線段：斜率：直線方程：,算法步驟：劃分區間[x0,x1]:

計算縱坐標：DDA算法取整：算法復雜度:加法+取整DDA算法其他斜率情況:交換x和y的位置步長dx或dy取-1不足之處：取整操作和浮點運算仍十分耗時 已知一條直線段L（P0,P1）,其端點坐標為：P0(x0,y0),P1(x1,y1)。可計算出直線的斜率k為： 假定端點坐標均為整數，取直線起點P0(x0,y0)作為初始坐標。畫線過程從x的左端點x0開始，向x右端點步進，每步x遞增1，y遞增k（即直線斜率）；取像素點（x，round（y））作為當前點的坐標。數值微分(DDA)法

假定直線的起點、終點分別為：（x0,y0),(x1,y1)，且都為整數。

(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)柵格交點表示象素點位置。。。。數值微分(DDA)法基本思想已知過端點P0(x0,y0),P1(x1,y1)的直線段Ly=kx+b直線斜率為這種方法直觀，但效率太低，因為每一步需要一次浮點乘法和一次舍入運算。

數值微分(DDA)法計算yi+1=kxi+1+b =kxi+b+kx =yi+kx當x=1; yi+1=yi+k即：當x每遞增1，y遞增k(即直線斜率)；注意上述分析的算法僅適用于k

≤1的情形。在這種情況下，x每增加1,y最多增加1。當k

1時，必須把x，y地位互換數值微分(DDA)法增量算法：在一個迭代算法中，如果每一步的x、y值是用前一步的值加上一個增量來獲得，則稱為增量算法。DDA算法就是一個增量算法。⑵Bresenham算法該算法原來是為繪圖機設計的，同樣適合于柵格化。該算法的基本思路為：若直線的斜率為1∕2≤△y∕△x≤1，則下一點取(1，1)點，若0≤△y∕△x＜1∕2，則下一點取(1，0)點。根據直線的斜率，把直線分為8個卦限。以斜率在第一卦限為例，其余卦限的情況類似。Bresenham

算例斜率為1∕3，起始點：e＝－1∕2，即e’＝－3，取點①第2點：e＝－1∕2+1∕3＝－1∕6，e’＝－3＋2△y＝－1取點②第3點：e＝－1∕6+1∕3=1∕6，即e’＝－1＋2＝1，取點③，且e＝－5/6,e’=－3；第4點：e＝1∕6+1∕3=1∕2＞0，即e’＝－5＋2＝－3，取點④因e≥1∕2，所以，e＝1∕2－1＝－1∕2。⒉面(多邊形)的柵格化方法⑴內部點擴散法由一個內部的種子點，向其4個方向的鄰點擴散。判斷新加入的點是否在多邊形邊界上，如果是，不作為種子點，否則當作新的種子點，直到區域填滿，無種子點為止。該算法比較復雜，而且可能造成阻塞而造成擴散不能完成，此外若多邊形不完全閉合時，會擴散出去。區域是指已經表示成點陣形式的填充圖形，它是像素集合。4-鄰接點和8-鄰接點

四個方向運動八個方向運動四連通區域八連通區域區域連通方式對填充結果的影響4連通區域邊界填充算法的填充結果8連通區域邊界填充算法的填充結果⑵掃描法按掃描線的順序，計算多邊形與掃描線的相交區間，再用相應的屬性值填充這些區間，即完成了多邊形的柵格化。這種算法的缺點是計算量較大。⑶邊填充算法對于每一條掃描線和每條多邊形邊上的交點，將該掃描線上交點右方的所有象素取原屬性值之補。對多邊形的每條邊作此處理，多邊形的方向任意。邊填充算法2上行時，左側加-a；下行時左側減-a。⒊柵格

矢量轉換多邊形邊界