地理信息系統(tǒng)第六章空間數(shù)據(jù)的處理方法

地理空間數(shù)據(jù)的獲取與處理第三部分

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

12211矢量數(shù)據(jù)拓?fù)潢P(guān)系在空間數(shù)據(jù)的查詢與分析中非常重要，矢量數(shù)據(jù)拓?fù)潢P(guān)系自動(dòng)建立的算法是GIS中的關(guān)鍵算法之一。歐拉定理對(duì)于多邊形圖形，n、a、b分別表示結(jié)點(diǎn)數(shù)、弧段數(shù)、多邊形數(shù)則：c=n-a+b或c+a=n+bc+弧=點(diǎn)+面c為常數(shù)，其取值為：c=2包含外多邊形c=1不包含外多邊形點(diǎn)線拓?fù)潢P(guān)系的建立記錄結(jié)點(diǎn)——弧段表弧段——結(jié)點(diǎn)表弧段入庫時(shí)，檢測(cè)結(jié)點(diǎn)表，若存在記錄點(diǎn)號(hào)；否則產(chǎn)生新的點(diǎn)號(hào)，再記錄多邊形的四種基本圖形

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

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

單多邊形被追蹤兩次

p1p2p3記錄多邊形多邊形的記錄格式可由節(jié)點(diǎn)或鏈構(gòu)成ID，n，[P]，AID，n，[L]，A確定多邊形的屬性在追蹤出每個(gè)多邊形的坐標(biāo)后，經(jīng)常需確定該多邊形的屬性。如果多邊形有內(nèi)點(diǎn)，則可以把內(nèi)點(diǎn)與多邊形匹配后，把內(nèi)點(diǎn)的屬性賦于多邊形。思考：若無內(nèi)點(diǎn)，能否記錄多邊形的屬性？如果沒有內(nèi)點(diǎn)，則必須通過人機(jī)交互，對(duì)每個(gè)多邊形賦屬性。拓?fù)涮幚碜⒁馐马?xiàng)1）可以根據(jù)實(shí)際數(shù)據(jù)的情況和使用目的，選擇不同的拓?fù)涮幚磉x項(xiàng)組合；2）如果需要進(jìn)行拓?fù)溴e(cuò)誤檢查，必須選擇弧段求交，弧段求交是進(jìn)行后續(xù)拓?fù)涮幚淼幕A(chǔ)。3）線數(shù)據(jù)集經(jīng)過拓?fù)涮幚砗?，原來?shù)據(jù)集的線對(duì)象將會(huì)在各線對(duì)象交點(diǎn)處被打斷，而生成新的線對(duì)象，如用戶還需繼續(xù)使用原來的線數(shù)據(jù)集，可以在拓?fù)涮幚砬皩?duì)線數(shù)據(jù)集先進(jìn)行備份，以保護(hù)原數(shù)據(jù)集；4）弧段求交操作得到的是一個(gè)真正的節(jié)點(diǎn)，而合并臨近點(diǎn)操作有時(shí)卻得到一個(gè)假節(jié)點(diǎn)，因此合并臨近點(diǎn)操作后可能還要繼續(xù)做合并假節(jié)點(diǎn)操作；5）線數(shù)據(jù)集必須關(guān)閉才能進(jìn)行拓?fù)涮幚恚?）拓?fù)涮幚淼慕Y(jié)果與拓?fù)淙菹薮笮〉脑O(shè)置有關(guān)。中間數(shù)據(jù)集重名延伸長懸線1延伸長懸線26.3空間數(shù)據(jù)的壓縮編碼方法矢量數(shù)據(jù)的壓縮矢量數(shù)據(jù)壓縮的目的是刪除冗余數(shù)據(jù)，減少數(shù)據(jù)的存貯量，節(jié)省存貯空間，加快后繼處理的速度。柵格數(shù)據(jù)的壓縮柵格數(shù)據(jù)壓縮的目的是刪除冗余數(shù)據(jù)，減少數(shù)據(jù)的存貯量，節(jié)省存貯空間，但在處理時(shí)會(huì)增大運(yùn)算量。是用時(shí)間換空間。矢量數(shù)據(jù)的壓縮道格拉斯——普克法(Douglas—Peucker)道格拉斯——普克法對(duì)每一條曲線的首末點(diǎn)虛連一條直線，求所有點(diǎn)與直線的距離，并找出最大距離值dmax。用dmax與限差D相比：若dmax＜D，這條曲線上的中間點(diǎn)全部舍去；若dmax≥D，保留dmax對(duì)應(yīng)的坐標(biāo)點(diǎn)，并以該點(diǎn)為界，把曲線分為兩部分，對(duì)這兩部分重復(fù)使用該方法垂距法每次順序取曲線上的三個(gè)點(diǎn)，計(jì)算中間點(diǎn)與其它兩點(diǎn)連線的垂線距離d，并與限差D比較。若d＜D，則中間點(diǎn)去掉；若d≥D，則中間點(diǎn)保留。然后順序取下三個(gè)點(diǎn)繼續(xù)處理，直到這條線結(jié)束。光欄法定義一個(gè)扇形區(qū)域，通過判斷曲線上的點(diǎn)在扇形外還是在扇形內(nèi)，確定保留還是舍去。設(shè)曲線上的點(diǎn)列為｛pi｝，i＝1，2，…，n，光欄口經(jīng)d可根據(jù)壓縮量確定幾種方法的比較標(biāo)準(zhǔn)既能精確地表示圖形，又能最大限度地淘汰不必要的點(diǎn)，那就是一種好的算法?？梢砸罁?jù)簡化后曲線的總長度、總面積、坐標(biāo)平均值等與原始曲線的相應(yīng)數(shù)據(jù)的對(duì)比來判別。分析大多數(shù)情況下道格拉斯——普克法的壓縮算法較好，但必須在對(duì)整條曲線數(shù)字化完成后才能進(jìn)行，且計(jì)算量較大；光欄法的壓縮算法也很好，并且可在數(shù)字化時(shí)實(shí)時(shí)處理，每次判斷下一個(gè)數(shù)字化的點(diǎn)，且計(jì)算量較??；垂距法算法簡單，速度快，但有時(shí)會(huì)將曲線的彎曲極值點(diǎn)p值去掉而失真。柵格數(shù)據(jù)的壓縮JPG27KBMP529K柵格的壓縮和編碼直接?xùn)鸥窬幋a鏈碼(chainEncoding)游程長編碼(Run_lengthEncoding)塊碼四叉樹編碼(quarter_treeEncoding)直接?xùn)鸥窬幋a將柵格數(shù)據(jù)當(dāng)成數(shù)據(jù)矩陣，逐行(或逐列)記錄代碼，每行都從左到右記錄，也可奇數(shù)行從左到右，偶數(shù)行從右到左。為了特定的目的還可采用其他特殊的順序。圖右：AAAAABBBAABBAABB同時(shí)記錄行、列數(shù)特點(diǎn)是處理方便，但沒有壓縮。AAAAABBBAABBAABB直接?xùn)鸥窬幋a0，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ù)的組織方法無論如何取值，在計(jì)算機(jī)中，如果矩陣的每個(gè)元素用一個(gè)雙字節(jié)表示，則一個(gè)圖層的全柵格數(shù)據(jù)所需要的存儲(chǔ)空間為m（行）×n（列）×2（字節(jié)）。如：一個(gè)面積為100km2的區(qū)域，如果網(wǎng)格邊長取為1m，每個(gè)網(wǎng)格用一個(gè)雙字節(jié)表示，則一個(gè)圖層的要素就占用？兆字節(jié)的存儲(chǔ)空間。200因此，柵格數(shù)據(jù)的壓縮是柵格數(shù)據(jù)結(jié)構(gòu)要解決的重要任務(wù)。是將原始柵格陣列中屬性值相同的連續(xù)若干個(gè)柵格單元映射為一個(gè)游程，每個(gè)游程的數(shù)據(jù)結(jié)構(gòu)為（A，P）整數(shù)對(duì)。其中，A代表屬性值，P代表該游程最右端柵格的列號(hào)。游程長度(行程)編碼按行掃描，將相鄰等值的象元合并記錄。右圖編碼為A4A1B3A2B2A2B2。若在行與行之間不間斷地連續(xù)編碼，則為A5B3A2B2A2B2。對(duì)于游程長度編碼，區(qū)域越大，數(shù)據(jù)的相關(guān)性越強(qiáng)，則壓縮越大。其特點(diǎn)是，壓縮效率較高，疊加、合并等運(yùn)算簡單，編碼和解碼運(yùn)算快AAAAABBBAABBAABB游程長度編碼只在各行（或列）數(shù)據(jù)的代碼發(fā)生變化時(shí)依次記錄該代碼以及相同代碼重復(fù)的個(gè)數(shù)；沿行方向進(jìn)行編碼：(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）。游程長度編碼逐個(gè)記錄各行（或列）代碼發(fā)生變化的位置和相應(yīng)代碼（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中有廣泛的應(yīng)用。其基本思路為：將2n×2n象元組成的圖像(不足的用背景補(bǔ)上)所構(gòu)成的二維平面按四個(gè)象限進(jìn)行遞歸分割，直到子象限的數(shù)值單調(diào)為止，最后得到一顆四分叉的倒向樹，該樹最高為n級(jí)。用一倒立樹表示這種分割和分割結(jié)果。根：整個(gè)區(qū)域高：深度、分幾級(jí)，幾次分割葉：不能再分割的塊樹叉：還需分割的塊每個(gè)樹叉均有4個(gè)分叉，叫四叉樹。四叉樹編碼四叉樹分解，各子象限大小不完全一樣，但都是同代碼柵格單元組成的子塊，其中最上面的一個(gè)結(jié)點(diǎn)叫做根結(jié)點(diǎn)，它對(duì)應(yīng)于整個(gè)圖形。不能再分的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)，可能落在不同的層上，該結(jié)點(diǎn)代表子象限單一的代碼，所有葉子結(jié)點(diǎn)所代表的方形區(qū)域覆蓋了整個(gè)圖形。從上到下，從左到右為葉子結(jié)點(diǎn)編號(hào)，最下面的一排數(shù)字表示各子區(qū)的代碼。為了保證四叉樹分解能不斷的進(jìn)行下去，要求圖形必須為2n×2n的柵格陣列。n為極限分割次數(shù)，n＋1是四叉樹最大層數(shù)或最大高度8*8四叉樹編碼①②③④⑤⑥⑦⑧⑨⑩1112131415161718192021222324252627282930313233363738393435400000333033333530022232222022225255533355西南東南西北東北四叉樹編碼法的優(yōu)點(diǎn)：1）容易而有效地計(jì)算多邊形的數(shù)量特征；2）陣列各部分的分辯率是可變的，邊界復(fù)雜部分四叉樹較高即分級(jí)多，分辯率也高，而不需表示許多細(xì)節(jié)的部分則分級(jí)少，分辯率低，因而既可精確表示圖形結(jié)構(gòu)又可減少存貯量；3）柵格到四叉樹及四叉樹到簡單柵格結(jié)構(gòu)的轉(zhuǎn)換比其它壓縮方法容易；4）多邊形中嵌套異類小多邊形的表示較方便。練習(xí)0231練習(xí)由直接?xùn)鸥窬幋a轉(zhuǎn)換成四叉樹編碼的樹狀表示333331111111333331111111333111144441333111444444332221114441322221111411222221111111222221111111222222111111222222111111答案3331111031331111411311441332221444103211141122211122221110210000000000用Morton碼表示四叉樹地址Morton碼表示的葉結(jié)點(diǎn)Morton碼的轉(zhuǎn)換Morton碼—葉節(jié)點(diǎn)碼葉節(jié)點(diǎn)碼—Morton碼Morton碼—行列值行列值—Morton碼四叉樹地址和Morton碼Morton碼—葉節(jié)點(diǎn)碼將十進(jìn)制Morton碼轉(zhuǎn)為二進(jìn)制碼39——100111將二進(jìn)制Morton碼每二位轉(zhuǎn)為十進(jìn)制數(shù)100111213葉節(jié)點(diǎn)碼—Morton碼將葉節(jié)點(diǎn)碼逐位轉(zhuǎn)為二進(jìn)制213100111將二進(jìn)制葉節(jié)點(diǎn)碼轉(zhuǎn)為Morton碼100111——391*25+0*24+0*23+1*22+1*21+1*2032+0+0+4+2+1=39Morton碼—行列值將Morton碼39轉(zhuǎn)為二進(jìn)制100111將二進(jìn)制的Morton碼奇偶分開100111101011將奇偶分別變成十進(jìn)制的行列10101153行列值—Morton碼將十進(jìn)制的行列分別變成二進(jìn)制53101011將二進(jìn)制的行列值奇偶合并得Morton碼101011100111將二進(jìn)制Morton碼變?yōu)槭M(jìn)制1*25+0*24+0*23+1*22+1*21+1*2032+0+0+4+2+1=39十進(jìn)制地址碼——Morton碼例如，對(duì)于第5行、第7列的Moton碼為：行數(shù)=5(0101)；列數(shù)=7(0111)

Morton=00110111=55這樣，在一個(gè)2n×2n的圖像中，每個(gè)像元點(diǎn)都給出一個(gè)Morton碼。十進(jìn)制和二進(jìn)制的轉(zhuǎn)換十進(jìn)制轉(zhuǎn)二進(jìn)制：

用2輾轉(zhuǎn)相除至結(jié)果為0，

將余數(shù)從下向上倒序?qū)懢褪嵌M(jìn)制值例如302轉(zhuǎn)二進(jì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余01/2=0余1

故十進(jìn)制302=二進(jìn)制100101110二進(jìn)制轉(zhuǎn)十進(jìn)制

從最后一位開始算，依次列為第0、1、2...位、第n位的數(shù)（0或1）乘以2的n次方，得到的結(jié)果相加就是十進(jìn)制值。例如:01101011.轉(zhuǎn)十進(jì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

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

二進(jìn)制01101011＝十進(jìn)制107十進(jìn)制和二進(jìn)制的轉(zhuǎn)換6.4空間數(shù)據(jù)的格式轉(zhuǎn)換數(shù)據(jù)格式轉(zhuǎn)換的內(nèi)容空間定位、空間關(guān)系、屬性信息轉(zhuǎn)換的方式通過外部數(shù)據(jù)交換文件轉(zhuǎn)換通過標(biāo)準(zhǔn)空間數(shù)據(jù)文件轉(zhuǎn)換通過標(biāo)準(zhǔn)API函數(shù)轉(zhuǎn)換6.5矢量和柵格數(shù)據(jù)的轉(zhuǎn)換矢量─柵格轉(zhuǎn)換由于矢量數(shù)據(jù)的點(diǎn)到柵格數(shù)據(jù)的點(diǎn)只是簡單的坐標(biāo)變換，線和面(多邊形)的矢量數(shù)據(jù)向柵格數(shù)據(jù)的轉(zhuǎn)換是主要內(nèi)容。柵格─矢量轉(zhuǎn)換柵格數(shù)據(jù)到矢量數(shù)據(jù)轉(zhuǎn)換的一般過程為：二值化、二值圖像的預(yù)處理、細(xì)化、追蹤、拓?fù)浠噶咯鸥褶D(zhuǎn)換點(diǎn)的柵格化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線的柵格化方法

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

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

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

(Xi+1,Yi+k)(Xi,Int(Yi+0.5))(Xi,Yi)柵格交點(diǎn)表示象素點(diǎn)位置。。。。數(shù)值微分(DDA)法基本思想已知過端點(diǎn)P0(x0,y0),P1(x1,y1)的直線段Ly=kx+b直線斜率為這種方法直觀，但效率太低，因?yàn)槊恳徊叫枰淮胃↑c(diǎn)乘法和一次舍入運(yùn)算。

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

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

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

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

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

矢量轉(zhuǎn)換多邊形邊界