第五講矢/柵轉(zhuǎn)換金毅河南理工大學(xué)資源環(huán)境學(xué)院454003ＱＱ:65585045電話_mail:jinyi2005@基本內(nèi)容柵格化：矢量數(shù)據(jù)結(jié)構(gòu)向柵格數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換確定柵格矩陣（行列數(shù)/分辨率）點(diǎn)的變換、線的變換以及多邊形的變換（面的變換）矢量化：柵格數(shù)據(jù)結(jié)構(gòu)向矢量數(shù)據(jù)結(jié)構(gòu)的轉(zhuǎn)換拓?fù)滢D(zhuǎn)換—保持柵格表示出的聯(lián)通性和鄰接性轉(zhuǎn)換物體正確的外形一、柵格化①確定柵格矩陣矢量數(shù)據(jù)轉(zhuǎn)換成柵格數(shù)據(jù)后，圖形的幾何精度必然要降低，所以選擇柵格尺寸的大小要盡量滿足精度要求，使之不過多地?fù)p失地理信息。為了提高精度，柵格需要細(xì)化，但柵格細(xì)化，數(shù)據(jù)量將以平方指數(shù)遞增，因此，精度和數(shù)據(jù)量是確定柵格大小的最重要的影響因素。在轉(zhuǎn)換之前需要確定柵格單元的大小，柵格單元的大小又稱為柵格圖像的分辨率，直接決定了柵格數(shù)據(jù)的精度一、柵格化①確定柵格矩陣YXOJIyx(0,0)XmaxYminXminYmaxI=(Ymax-Ymin)/dyJ=(Xmax-Xmin)/dxI，J為整數(shù)，尾數(shù)入上去dx=(Xmax-Xmin)/Jdy=(Ymax-Ymin)/I一、柵格化②點(diǎn)的柵格化一、柵格化③線的柵格化線是由多個直線段組成的，因此線的柵格化的核心就是直線段如何由矢量數(shù)據(jù)轉(zhuǎn)換為柵格數(shù)據(jù)柵格化的兩種常用方法為：DDA法(DigitalDifferentialAnalyzer數(shù)字微分分析法)Bresenham法1.

DDA法(數(shù)字微分分析法)—基本原理設(shè)(xA,yA),(xB,yB)與柵格網(wǎng)的交點(diǎn)為(xi,yi)，則有這樣從i＝0計(jì)算到i＝n－1，即可得直線與格網(wǎng)的n個交點(diǎn)坐標(biāo)，對其取整就是該點(diǎn)的柵格數(shù)據(jù)了一、柵格化③線的柵格化1.

DDA法(數(shù)字微分分析法)—特點(diǎn)該方法的基本依據(jù)是直線的微分方程，即dy/dx＝常數(shù)。其本質(zhì)是用數(shù)值方法解微分方程，通過同時對x和y各增加一個小增量來計(jì)算下一步的x,y值，即這是一種增量算法在該算法中，必須以浮點(diǎn)數(shù)表示坐標(biāo)，且每次都要舍入取整，因此，盡管算法正確，但速度不夠快一、柵格化③線的柵格化2.

Bresenham算法—基本原理算法核心思想是根據(jù)由直線斜率構(gòu)成的誤差項(xiàng)的符號來確定下一列坐標(biāo)的遞增值根據(jù)直線的斜率，把直線分為8個卦限。下面以斜率在第一卦限的情況為例，其余卦限的情況類似一、柵格化③線的柵格化該算法的基本思路可描述為：若直線的斜率為1/2≤△y/△x≤1，則下一點(diǎn)取(1，1)點(diǎn)；若0≤△y/△x＜1/2，則下一點(diǎn)取(1，0)點(diǎn)2.

Bresenham算法—實(shí)現(xiàn)過程在算法實(shí)現(xiàn)時，令起始的誤差項(xiàng)為e＝-1/2，然后在推斷出下一點(diǎn)后，令e＝e＋△y/△x(為直線斜率）,若e≥0，取(1，1)點(diǎn)(45o斜向)若e＜0，取(1，0)點(diǎn)(平行方向）若e≥0時，e＝e-1一、柵格化③線的柵格化直線斜率為1/3，起始點(diǎn)：e0＝-1/2,取點(diǎn)0第1點(diǎn)：e1＝-1/2+1/3＝-1/6取點(diǎn)1第2點(diǎn)：e2＝-1/6+1/3=1/6且e2’=-5/6；取點(diǎn)2第3點(diǎn)：e3＝-5/6+1/3=-1/2取點(diǎn)3；第4點(diǎn)：e4＝-1/2+1/3=-1/6取點(diǎn)4；第5點(diǎn)：e5＝-1/6+1/3=1/6且e2’=-5/6；取點(diǎn)5；第6點(diǎn)：e6＝-5/6+1/3=-1/2取點(diǎn)6；一、柵格化④面的柵格化邊界線的轉(zhuǎn)化與線的柵格化方法相同，接下來就是屬性的填充填充的方法很多，關(guān)鍵問題是正確判斷哪些柵格單元位于多邊形之內(nèi)，哪些位于多邊形之外。為此，多邊形必須嚴(yán)格封閉，沒有縫隙多邊形內(nèi)部屬性填充方法內(nèi)部點(diǎn)擴(kuò)散法射線算法平行線掃描法與鉛垂線跌落法邊界代數(shù)充填算法邊界點(diǎn)跟蹤算法一、柵格化④面的柵格化1、多邊形內(nèi)部屬性填充方法—基本原理由每個多邊形一個內(nèi)部點(diǎn)(種子點(diǎn))開始，向其八個方向的鄰點(diǎn)擴(kuò)散判斷各個新加入點(diǎn)是否在多邊形邊界上法如果是邊界點(diǎn)，則新加入點(diǎn)不作為種子點(diǎn)否則把非邊界點(diǎn)的鄰點(diǎn)作為新的種子點(diǎn)與原有種子點(diǎn)一起進(jìn)行新的擴(kuò)散運(yùn)算將該種子點(diǎn)賦予多邊形的編號重復(fù)上述過程，直到所有種子點(diǎn)填滿該多邊形并遇到邊界為止一、柵格化④面的柵格化1、多邊形內(nèi)部屬性填充方法—缺點(diǎn)程序設(shè)計(jì)復(fù)雜，需要在柵格陣列中搜索，占用內(nèi)存很大，在內(nèi)存受限時很難采用在一定的柵格精度上，如果復(fù)雜圖形的同一多邊形的兩條邊界落在同一個或相鄰的兩個柵格內(nèi)，會造成多邊形不連通，不能完成多邊形的填充(需板書)一、柵格化④面的柵格化2、射線法—基本原理概念：射線算法，又稱為檢驗(yàn)交點(diǎn)數(shù)法，是逐點(diǎn)判別數(shù)據(jù)柵格點(diǎn)在某多邊形之外或在多邊形內(nèi)來決定是否記錄該點(diǎn)基本原理：具體實(shí)現(xiàn)是由待判點(diǎn)向圖外某點(diǎn)引射線，判斷該射線與某多邊形所有邊界相交的總次數(shù)，判斷的基本原理：如相交偶數(shù)次，則待判點(diǎn)在該多邊形的外部如相交奇數(shù)次，則待判點(diǎn)在該多邊形的內(nèi)部一、柵格化④面的柵格化2、射線法—基本原理一、柵格化④面的柵格化N=0N=2N=1N=3N=42、射線法—特殊情況：奇異點(diǎn)一、柵格化④面的柵格化3、平行線掃描法與鉛垂線跌落法—基本原理射線算法的改進(jìn)，將射線改為沿柵格陣列列方向或行方向掃描線，判斷與射線算法相似。省去了計(jì)算射線與多邊形邊界交點(diǎn)的大量運(yùn)算，大大提高了效率。又稱為掃描算法一、柵格化④面的柵格化XYRfebagdcMN4、邊界代數(shù)填充算法（BAF-BoundaryAlgebraFilling）基本思想：基于積分思想的矢量格式向柵格格式轉(zhuǎn)換算法，它適合于記錄拓?fù)潢P(guān)系的多邊形矢量數(shù)據(jù)轉(zhuǎn)換為柵格結(jié)構(gòu)實(shí)現(xiàn)過程：初始化的柵格陣列各柵格值為零以柵格行列為參考坐標(biāo)軸，由多邊形某點(diǎn)開始順時針?biāo)阉鬟吔缇€邊界上行時，邊界左側(cè)行坐標(biāo)相同的柵格被加上0-a，

邊界下行時，邊界右側(cè)行坐標(biāo)相同的柵格被加上a-0一、柵格化④面的柵格化4、邊界代數(shù)填充算法（BAF-BoundaryAlgebraFilling）一、柵格化④面的柵格化4、邊界代數(shù)填充算法（BAF-BoundaryAlgebraFilling）多多邊形處理策略實(shí)現(xiàn)過程：當(dāng)邊界弧段上行時，該弧段與左圖框之間柵格增加一個值（左多邊形編號減去右多邊形編號）；當(dāng)邊界弧段下行時，該弧段與右圖框之間柵格增加一個值（右多邊形編號減去左多邊形編號）一、柵格化④面的柵格化5、邊界點(diǎn)跟蹤算法以多邊形為單位按順時針方向跟蹤單元格：上行L；橫向N；下行R（如果為島嶼，則相反）逐行掃描，充填LR間的