1、第三部分第三部分 主要內(nèi)容主要內(nèi)容第六章第六章 空間數(shù)據(jù)的處理方法空間數(shù)據(jù)的處理方法第六章第六章 空間數(shù)據(jù)的處理方法空間數(shù)據(jù)的處理方法圖形屏幕編輯的基本操作算法圖形屏幕編輯的基本操作算法介紹糾正數(shù)據(jù)采集錯誤的重要手段圖形編輯的基本功能、要求?？臻g數(shù)據(jù)拓撲關(guān)系的自動生成空間數(shù)據(jù)拓撲關(guān)系的自動生成介紹矢量數(shù)據(jù)拓撲關(guān)系建立的基本步驟和要點?？臻g數(shù)據(jù)的壓縮編碼方法空間數(shù)據(jù)的壓縮編碼方法介紹矢量數(shù)據(jù)和柵格數(shù)據(jù)的壓縮處理?？臻g數(shù)據(jù)的格式轉(zhuǎn)換空間數(shù)據(jù)的格式轉(zhuǎn)換矢量和柵格數(shù)據(jù)的轉(zhuǎn)換矢量和柵格數(shù)據(jù)的轉(zhuǎn)換6.1 6.1 圖形屏幕編輯的基本操作算法圖形屏幕編輯的基本操作算法點的捕捉點的捕捉線的捕捉線的捕捉面的捕捉面

2、的捕捉圖形編輯的關(guān)鍵是點、線、面的捕捉，即如何根據(jù)光標的位置找到需要編輯的要素，以及圖形編輯的數(shù)據(jù)組織。點的捕捉設(shè)光標點為A(x,y)，圖幅上某一點狀要素的坐標為S(X，Y)，則可設(shè)一捕捉半徑D(通常為35個象素)。dD 則選中，若有多個點，則要求出距A(x,y)的最近點。線的捕捉線的捕捉設(shè)光標點坐標為設(shè)光標點坐標為S(x,y)，D為捕捉半徑，線的坐為捕捉半徑，線的坐標為標為(x1,y1),(x2,y2),(xn,yn)。通過計算。通過計算S到該到該線的每個直線段的距離線的每個直線段的距離di(如左圖所示如左圖所示)，若，若min(d1,d2,dn-1)D，則認為光標，則認為光標S捕捉到了捕捉

3、到了該條線。在計算前，用最小矩形，跳過圖右的該條線。在計算前，用最小矩形，跳過圖右的線條。線條。S(x,y)(X1,Y2)(X1,Y)(X1,Y)面的捕捉面的捕捉面的捕捉實際上就是判斷光標點面的捕捉實際上就是判斷光標點S(x,y)是否是否在多邊形內(nèi)，若在多邊形內(nèi)則說明捕捉到。在多邊形內(nèi)，若在多邊形內(nèi)則說明捕捉到。判斷點是否在多邊形內(nèi)的算法主要有垂線判斷點是否在多邊形內(nèi)的算法主要有垂線法或轉(zhuǎn)角法。法或轉(zhuǎn)角法。垂線法垂線法先進行圖右的判斷（在線框內(nèi)外），再做奇偶點數(shù)的判斷。先進行圖右的判斷（在線框內(nèi)外），再做奇偶點數(shù)的判斷。奇在內(nèi)，偶在外。奇在內(nèi)，偶在外。垂線、水平線、斜線的結(jié)果均相同，垂線或水平

4、線運算方垂線、水平線、斜線的結(jié)果均相同，垂線或水平線運算方便。便。對于點在面的邊界上，可以對點的坐標加微量解決。若精對于點在面的邊界上，可以對點的坐標加微量解決。若精度要求高，不允許加微量，可以先解決點是否在面邊界的度要求高，不允許加微量，可以先解決點是否在面邊界的判斷，再使用垂線法。判斷，再使用垂線法。6.2 6.2 空間數(shù)據(jù)拓撲關(guān)系的自動生成空間數(shù)據(jù)拓撲關(guān)系的自動生成歐拉定理歐拉定理點線拓撲關(guān)系的建立點線拓撲關(guān)系的建立多邊形矢量數(shù)據(jù)拓撲關(guān)系自動建立多邊形矢量數(shù)據(jù)拓撲關(guān)系自動建立多數(shù)情況下拓撲關(guān)系的建立可由GIS軟件自動生成。特殊情況下，需要人工對拓撲關(guān)系進行人工修改，如建立管網(wǎng)或路網(wǎng)數(shù)據(jù)的

5、分析網(wǎng)絡(luò)時，就需要對結(jié)點、管段的方向等進行編輯。掃描后的柵格數(shù)據(jù)矢量化后的數(shù)字線劃圖矢量數(shù)據(jù)的常見錯誤公共邊界的處理公共邊界的處理 12211矢量數(shù)據(jù)拓撲關(guān)系在空間數(shù)據(jù)的查詢與分析中非常重要，矢量數(shù)據(jù)拓撲關(guān)系自動建立的算法是GIS中的關(guān)鍵算法之一。歐拉定理歐拉定理對于多邊形圖形，對于多邊形圖形，n、a、b 分別表示結(jié)點數(shù)、分別表示結(jié)點數(shù)、弧段數(shù)、多邊形數(shù)弧段數(shù)、多邊形數(shù)則：則： c=n-a+b 或或 c+a=n+b c+弧弧=點點+面面c為常數(shù)，其取值為：為常數(shù)，其取值為： c=2 包含外多邊形包含外多邊形 c=1 不包含外多邊形不包含外多邊形點線拓撲關(guān)系的建立點線拓撲關(guān)系的建立記錄記錄 結(jié)點

6、結(jié)點弧段表弧段表 弧段弧段結(jié)點表結(jié)點表弧段入庫時，檢測結(jié)點表，若存在記錄點弧段入庫時，檢測結(jié)點表，若存在記錄點號；否則產(chǎn)生新的點號，再記錄號；否則產(chǎn)生新的點號，再記錄多邊形的四種基本圖形多邊形的四種基本圖形 獨立獨立 公共邊公共邊 島島 復合復合多邊形多邊形矢量數(shù)據(jù)拓撲關(guān)系的自矢量數(shù)據(jù)拓撲關(guān)系的自動建立動建立鏈的組織結(jié)點匹配閉合檢查建立多邊形 概念 過程島的判斷確定多邊形的屬性鏈的組織鏈的組織 1 1找出在鏈的中間相交找出在鏈的中間相交(左圖左圖)，而不是在端點相，而不是在端點相交交(右圖右圖)的情況，自動切成新鏈。的情況，自動切成新鏈。鏈的組織鏈的組織 2原來的兩條鏈變成了四條鏈。再把鏈按一

7、定順序原來的兩條鏈變成了四條鏈。再把鏈按一定順序存儲，如按最大或最小的存儲，如按最大或最小的x或或y坐標的順序，這樣坐標的順序，這樣查找和檢索都比較方便，然后把鏈按順序編號。查找和檢索都比較方便，然后把鏈按順序編號。鏈的生成鏈的生成結(jié)點匹配結(jié)點匹配結(jié)點匹配是指把一定限差內(nèi)的鏈的端點作為一個結(jié)點，其結(jié)點匹配是指把一定限差內(nèi)的鏈的端點作為一個結(jié)點，其坐標值取多個端點的平均值。然后，對結(jié)點順序編號。坐標值取多個端點的平均值。然后，對結(jié)點順序編號。X=(x1+x2+x3)/3 ; Y=(y1+y2+y3)/3X=(x1+x2+x3)/3 ; Y=(y1+y2+y3)/3去除懸線去除懸線 閉閉合合檢檢查

8、查檢查多邊形是否閉合可以通過判斷一條鏈的端檢查多邊形是否閉合可以通過判斷一條鏈的端點是否有與之匹配的端點來進行。點是否有與之匹配的端點來進行。懸掛鏈懸掛鏈不需不需參加多邊形拓撲，可以作一標記，使之不參加參加多邊形拓撲，可以作一標記，使之不參加下一階段拓撲建立多邊形的工作。下一階段拓撲建立多邊形的工作。建立多邊形概念概念1 順時針方向構(gòu)多邊形。順時針方向構(gòu)多邊形。 順時針方向構(gòu)多邊形是指多邊形在鏈的右側(cè)順時針方向構(gòu)多邊形是指多邊形在鏈的右側(cè)概念2 最靠右邊的鏈最靠右邊的鏈是指從鏈的一個端點出發(fā)，在這條鏈的最靠右邊的鏈是指從鏈的一個端點出發(fā)，在這條鏈的方向上最右邊的第一條鏈。如圖，方向上最右邊的第

9、一條鏈。如圖，a的最右邊的鏈為的最右邊的鏈為d。找最靠右邊的鏈可通過計算鏈的方向和夾角實現(xiàn)找最靠右邊的鏈可通過計算鏈的方向和夾角實現(xiàn)求最右線段的方法1、從起始點、從起始點Pi出發(fā)，到達結(jié)出發(fā)，到達結(jié)點點P0，設(shè)方位角，設(shè)方位角P0 Pi為起為起始方位角始方位角f1；2、求終結(jié)點、求終結(jié)點P0到其他節(jié)點的到其他節(jié)點的方位角：方位角： f2 f3 .fn ；3、用、用f(i+1)-f(i)求解夾角求解夾角P(i) P0 P(i+1)，形成夾角串，形成夾角串 j j1 j2 jn；4、 j j1 j2 jn中最大者為中最大者為最右方向，其鏈為下一條最右方向，其鏈為下一條發(fā)展鏈。發(fā)展鏈。概念概念3 3

10、 用多邊形面積判斷方向用多邊形面積判斷方向用面積值判斷方向（需將絕對號去除）用面積值判斷方向（需將絕對號去除）niiiiixxyy111A)()(21S建立多邊形的基本過程建立多邊形的基本過程1、順序取一個結(jié)點為起始、順序取一個結(jié)點為起始結(jié)點，至該點上所有鏈均用結(jié)點，至該點上所有鏈均用2次止；取過該結(jié)點的任一次止；取過該結(jié)點的任一條鏈作為起始鏈。條鏈作為起始鏈。2、取這條鏈的另一結(jié)點，、取這條鏈的另一結(jié)點，找這個結(jié)點上，靠這條鏈最找這個結(jié)點上，靠這條鏈最右邊的鏈，作為下一條鏈。右邊的鏈，作為下一條鏈。3、是否回到起點：是，已、是否回到起點：是，已形成一多邊形，記錄之，并形成一多邊形，記錄之，并

11、轉(zhuǎn)轉(zhuǎn)4；否，轉(zhuǎn)；否，轉(zhuǎn)2。4、取起始點上開始的，剛、取起始點上開始的，剛才所形成多邊形的最后一條才所形成多邊形的最后一條邊反向作為新的起始鏈，轉(zhuǎn)邊反向作為新的起始鏈，轉(zhuǎn)2；若這條鏈已用過兩次，；若這條鏈已用過兩次，即已成為兩個多邊形的邊，即已成為兩個多邊形的邊，則轉(zhuǎn)則轉(zhuǎn)1。島的判斷島的判斷島的判斷即指找出多邊形互相包含的情況，即島的判斷即指找出多邊形互相包含的情況，即尋找多邊形的連通邊界。尋找多邊形的連通邊界。 找出所有比該正面積多邊形面積小的負面積多邊形；找出所有比該正面積多邊形面積小的負面積多邊形； 用外接矩形法去掉不可能包含的多邊形；用外接矩形法去掉不可能包含的多邊形； 取負面積多邊形上

12、的一點，看是否在正面積多邊形內(nèi)。取負面積多邊形上的一點，看是否在正面積多邊形內(nèi)。 單多邊形被追蹤兩次單多邊形被追蹤兩次 p1p1p2p2p3p3記錄多邊形記錄多邊形多邊形的記錄格式可由節(jié)點或鏈構(gòu)成多邊形的記錄格式可由節(jié)點或鏈構(gòu)成 ID ，n ， P ，A ID ，n ， L ，A確定多邊形的屬性確定多邊形的屬性在追蹤出每個多邊形的坐標后，經(jīng)常需確在追蹤出每個多邊形的坐標后，經(jīng)常需確定該多邊形的屬性。定該多邊形的屬性。如果多邊形有內(nèi)點，則可以把內(nèi)點與多邊如果多邊形有內(nèi)點，則可以把內(nèi)點與多邊形匹配后，把內(nèi)點的屬性賦于多邊形。形匹配后，把內(nèi)點的屬性賦于多邊形。思考思考：若無內(nèi)點，能否記錄多邊形的屬性

13、？若無內(nèi)點，能否記錄多邊形的屬性？如果沒有內(nèi)點，則必須通過人機交互，對每個多邊形賦屬性。拓撲處理注意事項拓撲處理注意事項1）可以根據(jù)實際數(shù)據(jù)的情況和使用目的，選擇不同的拓）可以根據(jù)實際數(shù)據(jù)的情況和使用目的，選擇不同的拓撲處理選項組合；撲處理選項組合；2）如果需要進行拓撲錯誤檢查，必須選擇弧段求交，?。┤绻枰M行拓撲錯誤檢查，必須選擇弧段求交，弧段求交是進行后續(xù)拓撲處理的基礎(chǔ)。段求交是進行后續(xù)拓撲處理的基礎(chǔ)。3）線數(shù)據(jù)集經(jīng)過拓撲處理后，原來數(shù)據(jù)集的線對象將會）線數(shù)據(jù)集經(jīng)過拓撲處理后，原來數(shù)據(jù)集的線對象將會在各線對象交點處被打斷，而生成新的線對象，如用戶還在各線對象交點處被打斷，而生成新的線對象

14、，如用戶還需繼續(xù)使用原來的線數(shù)據(jù)集，可以在拓撲處理前對線數(shù)據(jù)需繼續(xù)使用原來的線數(shù)據(jù)集，可以在拓撲處理前對線數(shù)據(jù)集先進行備份，以保護原數(shù)據(jù)集；集先進行備份，以保護原數(shù)據(jù)集；4）弧段求交操作得到的是一個真正的節(jié)點，而合并臨近）弧段求交操作得到的是一個真正的節(jié)點，而合并臨近點操作有時卻得到一個假節(jié)點，因此合并臨近點操作后可點操作有時卻得到一個假節(jié)點，因此合并臨近點操作后可能還要繼續(xù)做合并假節(jié)點操作；能還要繼續(xù)做合并假節(jié)點操作；5）線數(shù)據(jù)集必須關(guān)閉才能進行拓撲處理；）線數(shù)據(jù)集必須關(guān)閉才能進行拓撲處理；6）拓撲處理的結(jié)果與拓撲容限大小的設(shè)置有關(guān)。）拓撲處理的結(jié)果與拓撲容限大小的設(shè)置有關(guān)。中間數(shù)據(jù)集重名延

15、伸長懸線延伸長懸線1 1延伸長懸線延伸長懸線2 26.3 6.3 空間數(shù)據(jù)的壓縮編碼方法空間數(shù)據(jù)的壓縮編碼方法矢量數(shù)據(jù)的壓縮矢量數(shù)據(jù)的壓縮 矢量數(shù)據(jù)壓縮的目的是刪除冗余數(shù)據(jù)，減少數(shù)據(jù)的存貯量，節(jié)省存貯空間，加快后繼處理的速度。柵格數(shù)據(jù)的壓縮柵格數(shù)據(jù)的壓縮 柵格數(shù)據(jù)壓縮的目的是刪除冗余數(shù)據(jù)，減少數(shù)據(jù)的存貯量，節(jié)省存貯空間，但在處理時會增大運算量。是用時間換空間。矢量數(shù)據(jù)的壓縮道格拉斯普克法(DouglasPeucker)道格拉斯道格拉斯普克法普克法對每一條曲線的首末點虛連一條直線，對每一條曲線的首末點虛連一條直線，求所有點與直線的距離，并找出最大距求所有點與直線的距離，并找出最大距離值離值dma

16、x。用。用dmax與限差與限差D相比：相比： 若若dmaxD，這條曲線上的中間點全部舍去；，這條曲線上的中間點全部舍去； 若若dmaxD，保留，保留dmax對應的坐標點，并以該對應的坐標點，并以該點為界，把曲線分為兩部分，對這兩部分重點為界，把曲線分為兩部分，對這兩部分重復使用該方法復使用該方法垂距法垂距法每次順序取曲線上的三個點，計算中間點與其每次順序取曲線上的三個點，計算中間點與其它兩點連線的垂線距離它兩點連線的垂線距離d，并與限差，并與限差D比較。若比較。若dD，則中間點去掉；若，則中間點去掉；若dD，則中間點保留。，則中間點保留。然后順序取下三個點繼續(xù)處理，直到這條線結(jié)然后順序取下三個

17、點繼續(xù)處理，直到這條線結(jié)束。束。 光欄法定義一個扇形區(qū)域，通過判斷曲線上的點在扇形外還是在扇形內(nèi)，確定保留還是舍去。設(shè)曲線上的點列為pi，i1，2，n，光欄口經(jīng)d可根據(jù)壓縮量確定幾種方法的比較標準 既能精確地表示圖形，又能最大限度地淘汰不必要的點，那就是一種好的算法?？梢砸罁?jù)簡化后曲線的總長度、總面積、坐標平均值等與原始曲線的相應數(shù)據(jù)的對比來判別。分析 大多數(shù)情況下道格拉斯普克法的壓縮算法較好，但必須在對整條曲線數(shù)字化完成后才能進行，且計算量較大；光欄法的壓縮算法也很好，并且可在數(shù)字化時實時處理，每次判斷下一個數(shù)字化的點，且計算量較??；垂距法算法簡單，速度快，但有時會將曲線的彎曲極值點p值去掉

18、而失真。柵格數(shù)據(jù)的壓縮柵格數(shù)據(jù)的壓縮JPG 27K BMP 529K 柵格的壓縮和編碼柵格的壓縮和編碼直接柵格編碼直接柵格編碼鏈碼鏈碼(chain Encoding)游程長編碼游程長編碼(Run_length Encoding)塊碼塊碼四叉樹編碼四叉樹編碼(quarter_tree Encoding)直接柵格編碼將柵格數(shù)據(jù)當成數(shù)據(jù)矩陣，逐行(或逐列)記錄代碼，每行都從左到右記錄，也可奇數(shù)行從左到右，偶數(shù)行從右到左。為了為了特定的目的還可采用其他特殊特定的目的還可采用其他特殊的順序。的順序。圖右：AAAAABBBAABBAABB同時記錄行、列數(shù)特點是處理方便，但沒有壓縮。A A A AA B B

19、 BA A B BA A B B直接柵格編碼直接柵格編碼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。柵格數(shù)據(jù)的組織方法柵格數(shù)據(jù)的組織方法無論如何取值，在計算機中，如果矩陣的每個元素用一個雙字節(jié)表示，則一個圖層的全柵格數(shù)據(jù)所需要的存儲空間為m（行） n（列） 2（字節(jié)）。如：一個面積為100km2的區(qū)域，如果網(wǎng)格邊長取為1m，每個網(wǎng)格用一個雙字節(jié)表示，則一個圖層的要素就占用 兆字節(jié)的存儲

20、空間。200是將原始柵格陣列中屬性值相同的連續(xù)若干個柵格單元映射為一個游程，每個游程的數(shù)據(jù)結(jié)構(gòu)為（A，P）整數(shù)對。其中，A代表屬性值，P代表該游程最右端柵格的列號。游程長度(行程)編碼 按行掃描，將相鄰等值的象元合并記錄。 右圖編碼為 A4 A1 B3 A2 B2 A2 B2。若在行與行之間不間斷地連續(xù)編碼，則為 A5 B3 A2 B2 A2 B2。 對于游程長度編碼，區(qū)域越大，數(shù)據(jù)的相關(guān)性越強，則壓縮越大。其特點是，壓縮效率較高，疊加、合并等運算簡單，編碼和解碼運算快A A A AA B B BA A B BA A B B游程長度編碼游程長度編碼只在各行（或列）數(shù)據(jù)的代碼發(fā)生變化時依次記錄只

21、在各行（或列）數(shù)據(jù)的代碼發(fā)生變化時依次記錄該代碼以及相同代碼重復的個數(shù)；該代碼以及相同代碼重復的個數(shù)；沿行方向進行編碼：沿行方向進行編碼：( 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）。）。游程長度編碼游程長度編碼逐個記錄各行（或列）代碼發(fā)生變化的位置和逐

22、個記錄各行（或列）代碼發(fā)生變化的位置和相應代碼相應代碼（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）四叉樹編碼 四叉樹編碼是最有效的柵格數(shù)據(jù)壓縮編碼方法之一，在GIS中有廣泛的應用。其基本思路為：將2n2n象元組成的圖像(不足的用背景補上)所構(gòu)成的二維平面按四個象限進行遞歸分割，直到子象限的數(shù)值單

23、調(diào)為止，最后得到一顆四分叉的倒向樹，該樹最高為n級。用一倒立樹表示這種分割和分用一倒立樹表示這種分割和分割結(jié)果。割結(jié)果。根：根：整個區(qū)域整個區(qū)域高：高：深度、分幾級，幾次分割深度、分幾級，幾次分割葉：葉：不能再分割的塊不能再分割的塊樹叉：樹叉：還需分割的塊還需分割的塊 每個樹叉均有每個樹叉均有4個分叉，叫四個分叉，叫四叉樹。叉樹。四叉樹編碼四叉樹編碼 四叉樹分解，各子象限大小不完全一樣，四叉樹分解，各子象限大小不完全一樣，但都是同代碼柵格單元組成的子塊，其中最上但都是同代碼柵格單元組成的子塊，其中最上面的一個結(jié)點叫做根結(jié)點，它對應于整個圖形。面的一個結(jié)點叫做根結(jié)點，它對應于整個圖形。 不能再分

24、的結(jié)點稱為葉子結(jié)點，可能落在不不能再分的結(jié)點稱為葉子結(jié)點，可能落在不同的層上，該結(jié)點代表子象限單一的代碼，所同的層上，該結(jié)點代表子象限單一的代碼，所有葉子結(jié)點所代表的方形區(qū)域覆蓋了整個圖形。有葉子結(jié)點所代表的方形區(qū)域覆蓋了整個圖形。 從上到下，從左到右為葉子結(jié)點編號，最下從上到下，從左到右為葉子結(jié)點編號，最下面的一排數(shù)字表示各子區(qū)的代碼。面的一排數(shù)字表示各子區(qū)的代碼。 為了保證四叉樹分解能不斷的進行下去，要為了保證四叉樹分解能不斷的進行下去，要求圖形必須為求圖形必須為2 2n n2 2 n n的柵格陣列。的柵格陣列。n n 為極限分為極限分割次數(shù)，割次數(shù)，n n1 1是四叉樹最大層數(shù)或最大高度

25、是四叉樹最大層數(shù)或最大高度8 8* *8 8四叉樹編碼四叉樹編碼 1112131415161718192021222324252627282930313233363738393435400 0 00 3 3 3 0 3 3 33 3 5 3 0 0 2 2 2 3 2 2 2 2 0 22 2 2 5 2 5 5 53 33 5 5西南東南西北東北 四叉樹編碼法的優(yōu)點：1）容易而有效地計算多邊形的數(shù)量特征；2）陣列各部分的分辯率是可變的，邊界復雜部分四叉樹較高即分級多，分辯率也高，而不需表示許多細節(jié)的部分則分級少，分辯率低，因而既可精確表示圖形結(jié)構(gòu)又可減少存貯量；3）柵格到四叉樹及四叉樹到簡單

26、柵格結(jié)構(gòu)的轉(zhuǎn)換比其它壓縮方法容易；4）多邊形中嵌套異類小多邊形的表示較方便。0231由直接柵格編碼轉(zhuǎn)換成四叉樹編碼的樹狀表示3333311111113333311111113331111444413331114444443322211144413222211114112222211111112222211111112222221111112222221111113331111031331111411311441332221444103211141122211122221110210000000000用用MortonMorton碼表示四叉樹地址碼表示四叉樹地址Morton碼表示的葉結(jié)點碼表示的葉

27、結(jié)點Morton碼的轉(zhuǎn)換碼的轉(zhuǎn)換 Morton碼碼葉節(jié)點碼葉節(jié)點碼 葉節(jié)點碼葉節(jié)點碼Morton碼碼 Morton碼碼行列值行列值 行列值行列值Morton碼碼0123四叉樹地址和四叉樹地址和MortonMorton碼碼01230123MortonMorton碼碼葉節(jié)點碼葉節(jié)點碼將十進制將十進制Morton碼轉(zhuǎn)為二進制碼碼轉(zhuǎn)為二進制碼 39 100111將二進制將二進制Morton碼每二位轉(zhuǎn)為十進制數(shù)碼每二位轉(zhuǎn)為十進制數(shù) 10 01 11 2 1 3葉節(jié)點碼葉節(jié)點碼MortonMorton碼碼將葉節(jié)點碼逐位轉(zhuǎn)為二進制將葉節(jié)點碼逐位轉(zhuǎn)為二進制 2 1 3 10 01 11將二進制葉節(jié)點碼轉(zhuǎn)為將二

28、進制葉節(jié)點碼轉(zhuǎn)為Morton碼碼 100111 39 1*25+0*24+0*23+1*22+1*21+1*20 32+0+0+4+2+1=39MortonMorton碼碼行列值行列值將將Morton碼碼39轉(zhuǎn)為二進制轉(zhuǎn)為二進制100111將二進制的將二進制的Morton碼奇偶分開碼奇偶分開 10 01 11 101 011將奇偶分別變成十進制的行列將奇偶分別變成十進制的行列 101 011 5 3行列值行列值MortonMorton碼碼將十進制的行列分別變成二進制將十進制的行列分別變成二進制 5 3 101 011將二進制的行列值奇偶合并得將二進制的行列值奇偶合并得Morton碼碼 101

29、011 10 01 11將二進制將二進制Morton碼變?yōu)槭M制碼變?yōu)槭M制 1*25+0*24+0*23+1*22+1*21+1*20 32+0+0+4+2+1=39十進制地址碼Morton碼例如，對于第5行、第7列的Moton碼為：行數(shù) = 5 ( 0 1 0 1 ) ；列數(shù) = 7 ( 0 1 1 1 ) Morton = 0 0 1 1 0 1 1 1 = 55 這樣，在一個2 n2 n 的圖像中，每個像元點都給出一個Morton碼。十進制和二進制的轉(zhuǎn)換十進制和二進制的轉(zhuǎn)換十進制轉(zhuǎn)二進制：十進制轉(zhuǎn)二進制： 用用2輾轉(zhuǎn)相除至結(jié)果為輾轉(zhuǎn)相除至結(jié)果為0， 將余數(shù)從下向上倒序?qū)憣⒂鄶?shù)從下向上倒

30、序?qū)?就就是二進制值是二進制值例如例如302轉(zhuǎn)二進制轉(zhuǎn)二進制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 余余0 1/2 = 0 余余1 故十進制故十進制302 =二進制二進制100101110 二進制轉(zhuǎn)十進制二進制轉(zhuǎn)十進制 從最后一位開始算，依次列為第從最后一位開始算，依次列為第0、1、2.位位 、第第n位的數(shù)（位的數(shù)（0或或1）乘以）乘以2的的n次方，得到的結(jié)次方，得到的結(jié)果相加就是十進制值。果相加就是十進制值。例如例如:0110

31、1011.轉(zhuǎn)十進制轉(zhuǎn)十進制: 第第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 然后：然后：120 8032640107 二進制二進制01101011十進制十進制107十進制和二進制的轉(zhuǎn)換十進制和二進制的轉(zhuǎn)換6.4 6.4 空間數(shù)據(jù)的格式轉(zhuǎn)換空間數(shù)據(jù)的格式轉(zhuǎn)換數(shù)據(jù)格式轉(zhuǎn)換的內(nèi)容數(shù)據(jù)格式轉(zhuǎn)換的內(nèi)容 空間定位、空間關(guān)系、屬性信息空間定位、空間關(guān)系、屬性信息轉(zhuǎn)換的方式轉(zhuǎn)換的方式 通過外部數(shù)據(jù)交換文件轉(zhuǎn)換通過外部數(shù)據(jù)交換文件轉(zhuǎn)

32、換 通過標準空間數(shù)據(jù)文件轉(zhuǎn)換通過標準空間數(shù)據(jù)文件轉(zhuǎn)換 通過標準通過標準API函數(shù)轉(zhuǎn)換函數(shù)轉(zhuǎn)換6.5 6.5 矢量和柵格數(shù)據(jù)的轉(zhuǎn)換矢量和柵格數(shù)據(jù)的轉(zhuǎn)換矢量矢量柵格轉(zhuǎn)換柵格轉(zhuǎn)換 由于矢量數(shù)據(jù)的點到柵格數(shù)據(jù)的點只是簡單由于矢量數(shù)據(jù)的點到柵格數(shù)據(jù)的點只是簡單的坐標變換，線和面的坐標變換，線和面(多邊形多邊形)的矢量數(shù)據(jù)向柵的矢量數(shù)據(jù)向柵格數(shù)據(jù)的轉(zhuǎn)換是主要內(nèi)容。格數(shù)據(jù)的轉(zhuǎn)換是主要內(nèi)容。柵格柵格矢量轉(zhuǎn)換矢量轉(zhuǎn)換 柵格數(shù)據(jù)到矢量數(shù)據(jù)轉(zhuǎn)換的一般過程為：二柵格數(shù)據(jù)到矢量數(shù)據(jù)轉(zhuǎn)換的一般過程為：二值化、二值圖像的預處理、細化、追蹤、拓撲值化、二值圖像的預處理、細化、追蹤、拓撲化化矢量矢量柵格轉(zhuǎn)換柵格轉(zhuǎn)換點的柵格化點

33、的柵格化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線的柵格化方法線的柵格化方法 線是由多個直線段組成的，因此，線的柵線是由多個直線段組成的，因此，線的柵格化的核心就是直線段如何由矢量數(shù)據(jù)轉(zhuǎn)格化的核心就是直線段如何由矢量數(shù)據(jù)轉(zhuǎn)換為柵格數(shù)據(jù)。換為柵格數(shù)據(jù)。DDADDA法法( (數(shù)字微分分析法數(shù)字微分分析法) )直線段的兩端點坐標轉(zhuǎn)換到柵格數(shù)據(jù)的坐標系直線段的兩端點坐標轉(zhuǎn)換到柵格數(shù)據(jù)的坐標系后為后為(xA,yA),

34、(xB,yB)。設(shè)。設(shè)(xA,yA),(xB,yB)與柵格網(wǎng)與柵格網(wǎng)的交點為的交點為(xi,yi)，則，則:直線生成算法直線生成算法直線生成直線生成: 求與直線段充分接近的像素集求與直線段充分接近的像素集當直線作為一系列像素位置生成時產(chǎn)生的階梯效果當直線作為一系列像素位置生成時產(chǎn)生的階梯效果天津大學計算機科學與技術(shù)學院直線方程直線方程直線的斜率截矩方程直線的斜率截矩方程:給定線段的兩個端點給定線段的兩個端點 , 可可以計算斜率以計算斜率m和和y軸截矩軸截矩b:ym xB00(,) (,)endendxyxy00endendyymxx00 xmyb生成直線的常用算法均假定所畫直線的斜率k0，1。

35、DDA畫線算法DDA（Digital Differential Analyzer）畫線算法也稱數(shù)值微分法，是一種增量算法。它的算法實質(zhì)是用數(shù)值方法解微分方程，通過同時對x和y各增加一個小增量，計算下一步的x、y值。DDA算法算法 數(shù)值微分算法數(shù)值微分算法(Digital Differential Analyzer) 條件：條件： 待掃描轉(zhuǎn)換的直線段：待掃描轉(zhuǎn)換的直線段： 斜率：斜率： 直線方程：直線方程： , 算法步驟：算法步驟： 劃分區(qū)間劃分區(qū)間x0,x1: 計算縱坐標：計算縱坐標：01( 0, 0)( 1, 1)P xyP xy10,10 xxxyyy /myx ym xB011,1nii

36、x xxxx其中11(1)iiiiiym xBmxBm xBmym01mDDA算法算法 取整：取整： 算法復雜度算法復雜度: 加法加法+取整取整11()(int)(0.5)iiiyround yymDDA算法算法其他斜率情況其他斜率情況:1m 交換交換x和和y的位置的位置0m 步長步長dx或或dy取取-1不足之處：取整操作和浮點運算仍十分耗時不足之處：取整操作和浮點運算仍十分耗時已知一條直線段L（P0, P1）,其端點坐標為：P0 (x0, y0), P1(x1, y1)?？捎嬎愠鲋本€的斜率k為： 假定端點坐標均為整數(shù)，取直線起點P0 (x0, y0)作為初始坐標。畫線過程從x的左端點x0開始

37、，向x右端點步進，每步x遞增1，y遞增k（即直線斜率）；取像素點（x，round（y）作為當前點的坐標。0101xxyyk數(shù)值微分(DDA)法 假定直線的起點、終點分別為：（x0,y0), (x1,y1)，且都為整數(shù)。(X i+1 ,Yi + k)(X i , Int(Yi +0.5)(X i , Yi)柵格交點表示象素點位置。數(shù)值微分(DDA)法基本思想已知過端點P0 (x0, y0), P1(x1, y1)的直線段Ly=kx+b直線斜率為這種方法直觀，但效率太低，因為每一步需要一次浮點乘法和一次舍入運算。 0101xxyyk)(,;10yroundxbkxystepxxxxxx令數(shù)值微分(

38、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地位互換數(shù)值微分(DDA)法增量算法：在一個迭代算法中，如果每一步的x、y值是用前一步的值加上一個增量來獲得，則稱為增量算法。DDA算法就是一個增量算法。BresenhamBresenham算法算法該算法原來是為繪圖機設(shè)該算法原來是為繪圖機設(shè)計的，同樣適合于柵格化。計的，同樣適合于柵格化。該算法的基本思路為：若該算法的基本思路為：若

39、直線的斜率為直線的斜率為12yx1，則下一點取，則下一點取(1，1)點，點，若若0yx12，則下一點，則下一點取取(1，0)點。點。n根據(jù)直線的斜率，把直線分為根據(jù)直線的斜率，把直線分為8個卦限。以斜率在第個卦限。以斜率在第一卦限為例，其余卦限的情況類似。一卦限為例，其余卦限的情況類似。BreseBresenhamnham算例算例斜率為斜率為13， 起始點：起始點：e12， 即即e3，取點，取點第第2點：點：e12 + 1316，e32y1取點取點第第3點：點：e16 + 13 = 16，即，即e121， 取點取點，且且e5/6,e=3；第第4點：點：e16 + 13 = 12 0，即，即e5

40、23， 取點取點因因e12，所以，所以，e12112。面面( (多邊形多邊形) )的柵格化方法的柵格化方法內(nèi)部點擴散法內(nèi)部點擴散法 由一個內(nèi)部的種子點，向其由一個內(nèi)部的種子點，向其4個方向的鄰點擴散。判個方向的鄰點擴散。判斷新加入的點是否在多邊形邊界上，如果是，不作斷新加入的點是否在多邊形邊界上，如果是，不作為種子點，否則當作新的種子點，直到區(qū)域填滿，為種子點，否則當作新的種子點，直到區(qū)域填滿，無種子點為止。無種子點為止。該算法比較復雜，而且該算法比較復雜，而且可能造成阻塞而造成擴可能造成阻塞而造成擴散不能完成，此外若多散不能完成，此外若多邊形不完全閉合時，會邊形不完全閉合時，會擴散出去。擴散

41、出去。區(qū)域區(qū)域是指已經(jīng)表示成點陣形式的填充圖形，它是像素集合。4-鄰接點鄰接點和8-鄰接點鄰接點表示內(nèi)點表示邊界點 四個方向運動 八個方向運動 四連通區(qū)域 八連通區(qū)域區(qū)域連通方式對填充結(jié)果的影響區(qū)域連通方式對填充結(jié)果的影響4連通區(qū)域邊界填充算法的填充結(jié)果8連通區(qū)域邊界填充算法的填充結(jié)果掃描法掃描法按掃描線的順序，計算多邊形與掃描線的相按掃描線的順序，計算多邊形與掃描線的相交區(qū)間，再用相應的屬性值填充這些區(qū)間，交區(qū)間，再用相應的屬性值填充這些區(qū)間，即完成了多邊形的柵格化。這種算法的缺點即完成了多邊形的柵格化。這種算法的缺點是計算量較大。是計算量較大。邊填充算法邊填充算法邊填充算法2 2上行時，左

42、側(cè)加上行時，左側(cè)加-a；下行時左側(cè)減；下行時左側(cè)減-a。柵格柵格矢量轉(zhuǎn)換矢量轉(zhuǎn)換多邊形邊界提取二值化 細化 二值圖像二值圖像矢量轉(zhuǎn)換矢量轉(zhuǎn)換二值化二值化 對于地圖，通常在灰度級直方圖上出現(xiàn)兩個對于地圖，通常在灰度級直方圖上出現(xiàn)兩個峰值，這時，取波谷處的灰度級為閾值，二峰值，這時，取波谷處的灰度級為閾值，二值化的效果較好值化的效果較好二值圖像的預處理二值圖像的預處理 對于掃描輸入的對于掃描輸入的圖幅，會出現(xiàn)一些圖幅，會出現(xiàn)一些飛白、污點、線劃飛白、污點、線劃邊緣凹凸不平等。邊緣凹凸不平等?？梢酝ㄟ^一些算法可以通過一些算法來進行處理。來進行處理。對飛白、污點給定對飛白、污點給定其最小尺寸，不足其最小尺寸，不足的消除的消除；對于斷對于斷線，采取先加粗后減細的方法進行斷線相連；用低通線，采取先加粗后減細的方法進行斷線相連；用低通型濾波進行破碎地物的合并，用高通濾波提取區(qū)域范型濾波進行破碎地物的合并，用高通濾波提取區(qū)域范圍等等圍等等細化細化所謂細化就是將二值圖像象元陣列逐步剝除輪所謂細化就是將二值圖像象元陣列逐步剝除輪廓邊緣的點，使之成為線劃寬度只有一個象元廓邊緣的點，使之成為線劃寬度只有一個象元的骨架圖形。細化后的圖形便于跟蹤處理。的骨架圖形。細化后的圖形便于跟蹤處理。細化的基本過程是：細化