第三章空間數(shù)據(jù)模型與數(shù)據(jù)庫(kù)13.4矢量結(jié)構(gòu)與柵格結(jié)構(gòu)的相互轉(zhuǎn)換矢量數(shù)據(jù)結(jié)構(gòu)向柵格數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換（柵格化）柵格數(shù)據(jù)結(jié)構(gòu)向矢量數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換（矢量化）23.4.1矢量到柵格柵格化過(guò)程包括以下操作：1）確定柵格矩陣(行列數(shù)\分辨率)；2）點(diǎn)的變換3）線(xiàn)的變換4）多邊形的變換(面的變換)31)確定柵格矩陣矢量數(shù)據(jù)轉(zhuǎn)換成柵格數(shù)據(jù)后，圖形的幾何精度必然要降低，所以選擇柵格尺寸的大小要盡量滿(mǎn)足精度要求，使之不過(guò)多地?fù)p失地理信息。為了提高精度，柵格需要細(xì)化，但柵格細(xì)化，數(shù)據(jù)量將以平方指數(shù)遞增，因此，精度和數(shù)據(jù)量是確定柵格大小的最重要的影響因素。4I=(Ymax-Ymin)/dyJ=(Xmax-Xmin)/dxI，J為整數(shù)，尾數(shù)入上去dx=(Xmax-Xmin)/Jdy=(Ymax-Ymin)/I1)確定柵格矩陣在轉(zhuǎn)換之前需要確定柵格單元的大小，柵格單元的大小又稱(chēng)為柵格圖像的分辨率，直接決定了柵格數(shù)據(jù)的精度。YXOJIyx(0,0)XmaxYminXminYmax53）線(xiàn)的柵格化方法線(xiàn)是由多個(gè)直線(xiàn)段組成的，因此線(xiàn)的柵格化的核心就是直線(xiàn)段如何由矢量數(shù)據(jù)轉(zhuǎn)換為柵格數(shù)據(jù)。柵格化的兩種常用方法為:DDA法(DigitalDifferentialAnalyzer數(shù)字微分分析法)Bresenham法7DDA法(數(shù)字微分分析法)設(shè)(xA,yA),(xB,yB)與柵格網(wǎng)的交點(diǎn)為(xi,yi)，則:

其中：這樣從i＝0計(jì)算到i＝n－1，即可得直線(xiàn)與格網(wǎng)的n個(gè)交點(diǎn)坐標(biāo)，對(duì)其取整就是該點(diǎn)的柵格數(shù)據(jù)了。該方法的基本依據(jù)是直線(xiàn)的微分方程，即dy/dx＝常數(shù)。其本質(zhì)是用數(shù)值方法解微分方程，通過(guò)同時(shí)對(duì)x和y各增加一個(gè)小增量來(lái)計(jì)算下一步的x,y值，即這是一種增量算法。在該算法中，必須以浮點(diǎn)數(shù)表示坐標(biāo)，且每次都要舍入取整，因此，盡管算法正確，但速度不夠快。8在算法實(shí)現(xiàn)時(shí)，令起始的誤差項(xiàng)為e＝-1/2，然后在推斷出下一點(diǎn)后，令e＝e＋△y/△x,若e≥0時(shí)，e＝e-1。這樣只要根據(jù)e的符號(hào)就可確定下一點(diǎn)的增量，即：

若e≥0，取(1，1)點(diǎn)

若e＜0，取(1，0)點(diǎn)例如，一直線(xiàn)的斜率為1/3，起始點(diǎn)：e0＝-1/2,取點(diǎn)0第1點(diǎn)：e1＝-1/2+1/3＝-1/6取點(diǎn)①第2點(diǎn)：e2＝-1/6+1/3=1/6且e2’=-5/6；取點(diǎn)②第3點(diǎn)：e3＝-5/6+1/3=-1/2取點(diǎn)③第4點(diǎn)：e4＝-1/2+1/3=-1/6取點(diǎn)④第5點(diǎn)：e5＝-1/6+1/3=1/6且e2’=-5/6；取點(diǎn)⑤第6點(diǎn)：e6＝-5/6+1/3=-1/2取點(diǎn)⑥依次進(jìn)行，直到到達(dá)直線(xiàn)的另一端點(diǎn)。這種算法不僅速度快、效果好，而且可以理論上證明它是目前同類(lèi)各種算法中最優(yōu)的。為避免浮點(diǎn)運(yùn)算，可令初值e’=e*2*△x當(dāng)△x≥0時(shí)與e同號(hào)

當(dāng)e’>0時(shí)，y方向獲增量1，即令e’＝e’-2*△x；一般情況下e’＝e’+2△y起始點(diǎn)：e＝-1/2，即e’＝-3

第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’=-5；104）面域的柵格化邊界線(xiàn)的轉(zhuǎn)化與線(xiàn)的柵格化方法相同，接下來(lái)就是屬性的填充。填充的方法很多，關(guān)鍵問(wèn)題是正確判斷哪些柵格單元位于多邊形之內(nèi)，哪些位于多邊形之外。為此，多邊性必須嚴(yán)格封閉，沒(méi)有縫隙。方法有：內(nèi)部點(diǎn)擴(kuò)散法射線(xiàn)算法平行線(xiàn)掃描法與鉛垂線(xiàn)跌落法邊界代數(shù)充填算法邊界點(diǎn)跟蹤算法11（1）內(nèi)部點(diǎn)擴(kuò)散算法該算法由每個(gè)多邊形一個(gè)內(nèi)部點(diǎn)（種子點(diǎn)）開(kāi)始，向其八個(gè)方向的鄰點(diǎn)擴(kuò)散，判斷各個(gè)新加入點(diǎn)是否在多邊形邊界上，如果是邊界上，則該新加入點(diǎn)不作為種子點(diǎn)，否則把非邊界點(diǎn)的鄰點(diǎn)作為新的種子點(diǎn)與原有種子點(diǎn)一起進(jìn)行新的擴(kuò)散運(yùn)算，并將該種子點(diǎn)賦以該多邊形的編號(hào)。重復(fù)上述過(guò)程直到所有種子點(diǎn)填滿(mǎn)該多邊形并遇到邊界停止為止。擴(kuò)散算法程序設(shè)計(jì)比較復(fù)雜，并且在一定的柵格精度上，如果復(fù)雜圖形的同一多邊形的兩條邊界落在同一個(gè)或相鄰的兩個(gè)柵格內(nèi)，會(huì)造成多邊形不連通，這樣一個(gè)種子點(diǎn)不能完成整個(gè)多邊形的填充。12（2）射線(xiàn)算法射線(xiàn)算法可逐點(diǎn)判斷數(shù)據(jù)柵格點(diǎn)在某多邊形之外或在多邊形內(nèi)，由待判點(diǎn)向圖外某點(diǎn)引射線(xiàn)，判斷該射線(xiàn)與某多邊形所有邊界相交的總次數(shù)，如相交偶數(shù)次，則待判點(diǎn)在該多邊形外部，如為奇數(shù)次，則待判點(diǎn)在該多邊形內(nèi)部。采用射線(xiàn)算法，要注意的是：射線(xiàn)與多邊形邊界相交時(shí)，有一些特殊情況會(huì)影響交點(diǎn)的個(gè)數(shù)，必須予以排除。射線(xiàn)算法13射線(xiàn)算法的特殊情況14（3）平行線(xiàn)掃描法與鉛垂線(xiàn)跌落法射線(xiàn)算法的改進(jìn)，將射線(xiàn)改為沿柵格陣列列方向或行方向掃描線(xiàn)，判斷與射線(xiàn)算法相似。省去了計(jì)算射線(xiàn)與多邊形邊界交點(diǎn)的大量運(yùn)算，大大提高了效率。XYRfebagdcMN15事實(shí)上，每幅數(shù)字地圖都是由多個(gè)多邊形區(qū)域組成的，如果把不屬于任何多邊形的區(qū)域（包含無(wú)窮遠(yuǎn)點(diǎn)的區(qū)域）看成編號(hào)為零的特殊的多邊形區(qū)域，則圖上每一條邊界弧段都與兩個(gè)不同編號(hào)的多邊形相鄰，按弧段的前進(jìn)方向分別稱(chēng)為左、右多邊形，對(duì)于這種多個(gè)多邊形的矢量向柵格轉(zhuǎn)換問(wèn)題，只需對(duì)所有多邊形邊界弧段作如下運(yùn)算而不考慮排列次序：當(dāng)邊界弧段上行時(shí)，該弧段與左圖框之間柵格增加一個(gè)值（左多邊形編號(hào)減去右多邊形編號(hào)）；當(dāng)邊界弧段下行時(shí)，該弧段與左圖框之間柵格增加一個(gè)值（右多邊形編號(hào)減去左多邊形編號(hào)）。17182021邊界代數(shù)法與前述其他算法的不同之處，在于它不是逐點(diǎn)判斷與邊界的關(guān)系完成轉(zhuǎn)換，而是根據(jù)邊界的拓?fù)湫畔ⅲㄟ^(guò)簡(jiǎn)單的加減代數(shù)運(yùn)算將邊界位置信息動(dòng)態(tài)地賦給各柵格點(diǎn)，實(shí)現(xiàn)了矢量格式到柵格格式的高速轉(zhuǎn)換，而不需要考慮邊界與搜索軌跡之間的關(guān)系，因此算法簡(jiǎn)單、可靠性好，各邊界弧段只被搜索一次，避免了重復(fù)計(jì)算。但是這并不意味著邊界代數(shù)法可以完全替代其它算法，在某些場(chǎng)合下，還是要采用種子填充算法和射線(xiàn)算法，前者應(yīng)用于在柵格圖像上提取特定的區(qū)域；后者則可以進(jìn)行點(diǎn)和多邊形關(guān)系的判斷22（5）邊界點(diǎn)跟蹤算法以多邊形為單位按順時(shí)針?lè)较蚋檰卧裆闲蠰橫向N下行R（島則相反）逐行掃描，充填LR間的單元格233.4.2柵格到矢量從柵格單元轉(zhuǎn)換到幾何圖形的過(guò)程稱(chēng)為矢量化，矢量化過(guò)程要保證以下兩點(diǎn)：1）拓?fù)滢D(zhuǎn)換，即保持柵格表示出的連通性與鄰接性；2）轉(zhuǎn)換物體正確的外形。243.4.2柵格數(shù)據(jù)結(jié)構(gòu)向矢量數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換主要步驟：邊界提取邊緣銳化（遙感影像或分類(lèi)柵格，面狀地物）線(xiàn)的細(xì)化（掃描矢量圖，線(xiàn)狀地物）二值化邊界追蹤拓?fù)潢P(guān)系生成線(xiàn)的簡(jiǎn)化及曲線(xiàn)圓滑25Lenna的Sobel邊界Lenna的Prewitt邊界272)線(xiàn)的細(xì)化:將占有多個(gè)柵格寬的圖形要素縮減為只有1個(gè)像素。剝皮法：每次剝掉等于一個(gè)柵格寬的一層，最后只留下彼此連通的由單個(gè)柵格組成的圖形。28301.邊界提取3)二值化一般情況下，柵格數(shù)據(jù)是按0～255的不同灰度值表達(dá)的。為了簡(jiǎn)化追蹤算法，需把256個(gè)灰階壓縮為2個(gè)灰階，即0和1兩級(jí)。為此，假設(shè)任一格網(wǎng)的灰度值為G(i,j),閥值為T(mén)，那么，根據(jù)下式就可以得到二值圖。G(i,j)=1f(i,j)>=T0f(i,j)<=T312.邊界線(xiàn)追蹤：邊界線(xiàn)跟蹤的目的就是將細(xì)化處理后的柵格數(shù)據(jù)，整理為從結(jié)點(diǎn)出發(fā)的線(xiàn)段或閉合的線(xiàn)條，并以矢量形式存儲(chǔ)（坐標(biāo)）。3.線(xiàn)的簡(jiǎn)化及曲線(xiàn)圓滑：由于搜索是逐個(gè)柵格進(jìn)行的，所以弧段或多邊形的數(shù)據(jù)列十分密集。為了減少存儲(chǔ)量，在保證線(xiàn)段精度的情況下可以刪除部分?jǐn)?shù)據(jù)點(diǎn)。4.拓?fù)潢P(guān)系生成：判