基于柵格的環(huán)形多邊形區(qū)域填充算法

邱國清

(閩南師范大學(xué) 計算機(jī)學(xué)院， 福建 漳州 363000)

環(huán)形多邊形區(qū)域填充是指在一個給定的區(qū)域內(nèi)對所有像素單元賦予指定的像素值，由于環(huán)形多邊形的區(qū)域形狀不同，有些包含非常狹窄區(qū)域，有些相互嵌套。在填充時，采用傳統(tǒng)的算法如遞歸種子算法、種子填充算法或掃描線算法難以實現(xiàn)填滿整個區(qū)域[1-3]。等間距平行線填充算法是通過在指定區(qū)域內(nèi)繪制一組等間距平行線，計算每條平行線與多邊形邊界的交點(diǎn)并配對成組，根據(jù)每組交點(diǎn)坐標(biāo)值來計算該條平行線所穿越的柵格單元個數(shù)及每個柵格單元的坐標(biāo)，計算出整個區(qū)域柵格單元數(shù)，依次對每個單元進(jìn)行填充，從而實現(xiàn)對整個區(qū)域填充。該算法不需要設(shè)置種子點(diǎn)，特別適用于相互嵌套且狹窄區(qū)域的填充。

1 等間距平行線算法

1.1 等間距平行線基本原理

繪制等間距平行線是指在多邊形區(qū)域內(nèi)繪制一組平行線并計算其與邊界的交點(diǎn)，算法步驟[4]如下：

(1)旋轉(zhuǎn)多邊形頂點(diǎn)坐標(biāo)。由于平行線的傾斜為任意角度，為了計算方便，首先旋轉(zhuǎn)頂點(diǎn)坐標(biāo)值，目的是使繪制出的等間距平行線相互平行且呈現(xiàn)水平狀，設(shè)等間距平行線與原坐標(biāo)系的y軸之間夾角為θ(-180°≤θ≤180°)，新坐標(biāo)系下輪廓點(diǎn)的轉(zhuǎn)換計算公式為

(1)

(2)

(2)在新的曲面輪廓點(diǎn)中求橫坐標(biāo)的最小值和最大值。取輪廓點(diǎn)中橫坐標(biāo)最小值，d為等間距平行線的間距，首先選定一條平行線開始推算，該平行線與新坐標(biāo)系Y軸之間的距離稱為a值，也就是第一條平行線的橫坐標(biāo)，計算公式[5]為

(3)

(3)根據(jù)斜率公式計算交點(diǎn)坐標(biāo)值，即

(4)

(4)根據(jù)交點(diǎn)坐標(biāo)計算該條平行線穿過的柵格單元的行列序號，即

(5)

(6)

1.2 算法描述

(1)建立多邊形頂點(diǎn)集合，輸入每個頂點(diǎn)的坐標(biāo)值，判斷橫坐標(biāo)值，找出最大值和最小值。設(shè)置等間距平行線的間距值，根據(jù)公式(3)計算出第一條平行線的橫坐標(biāo)值。

(2)根據(jù)公式(4)判斷當(dāng)前平行線與多邊形輪廓是否相交，如果沒有交點(diǎn)則執(zhí)行第(3)步，否則執(zhí)行第(4)步。

(3)計算下一條平行線的橫坐標(biāo)，返回第(2)步。

(4)根據(jù)公式(4)計算平行線與輪廓邊界的交點(diǎn)并保存。

(5)判斷a的值是否大于多邊形頂點(diǎn)橫坐標(biāo)最大值，如果小于則返回第(3)步，否則退出。

等間距平行算法流程如圖1所示。

圖1 等間距平行線算法流程圖

1.3 區(qū)域柵格化

區(qū)域柵格化是指把整個環(huán)形多邊形所在區(qū)域劃分成大小一致且緊密相連的網(wǎng)格陣列，每個網(wǎng)格相當(dāng)于一個像元，每個像元由行列號確定其位置。網(wǎng)格大小可以根據(jù)精度要求進(jìn)行設(shè)置，所有網(wǎng)格面積等于環(huán)形多邊形區(qū)域的大小，對所有單元賦予指定像素值，實現(xiàn)了多邊形的區(qū)域填充。

1.4 裁剪算法

線段裁剪是計算機(jī)圖形學(xué)研究的一個基本內(nèi)容[6]，在圖形處理系統(tǒng)中，裁剪是指在指定區(qū)域內(nèi)識別圖形內(nèi)、外部分的過程[7]。多邊形裁剪算法是指被裁剪的多邊形與裁剪區(qū)域均為多邊形的情形，該算法的原理是：由入點(diǎn)開始，沿被裁剪多邊形追蹤，當(dāng)遇到出點(diǎn)時跳轉(zhuǎn)到裁剪區(qū)域繼續(xù)追蹤；如果再次遇到入點(diǎn)，則跳轉(zhuǎn)回被裁剪多邊形繼續(xù)追蹤。重復(fù)以上過程，直到回到起始入點(diǎn)，算法步驟如下：

(1)計算多邊形a、c的交點(diǎn)，把交點(diǎn)分別加入到兩個多邊形的頂點(diǎn)數(shù)組中，構(gòu)成新的集合a′、c′；

(2)建立交點(diǎn)I集合，記錄交點(diǎn)類型及其在兩個多邊形頂點(diǎn)集合中的位置；

(3)在交點(diǎn)集合I中取出一個入點(diǎn)，在a′中查找該入點(diǎn)的位置并沿順時針方向追蹤a′的頂點(diǎn)集合，直到遇到下一個交點(diǎn)；

(4)根據(jù)第(3)步搜索到的交點(diǎn)在c′表中的位置，沿順時針追蹤c′的頂點(diǎn)表，直至遇到下一個交點(diǎn)。

(5)跳轉(zhuǎn)到a′，重復(fù)第三、四步，直至回到起始交點(diǎn)。

2 數(shù)據(jù)驗證

2.1 狹窄區(qū)域填充

首先根據(jù)多邊形區(qū)域所有頂點(diǎn)坐標(biāo)值繪制環(huán)形多邊形，如圖2(a)所示，該環(huán)形區(qū)域有多個凹進(jìn)和凸起部分，由于其中一些狹小的區(qū)域間距過小，很難實現(xiàn)填充。為此根據(jù)等間距平行線繪制算法，在多邊形區(qū)域內(nèi)繪制一組平行線，依次循環(huán)判斷每一條平行線與邊界是否相交并計算交點(diǎn)，記錄并保存每個交點(diǎn)的坐標(biāo)值，排序配對輸出。根據(jù)每一對坐標(biāo)值依次判斷該條平行線經(jīng)過的柵格單元個數(shù)，最終的效果如圖2(b)、(c)所示，多邊形區(qū)域內(nèi)有52個坐標(biāo)對，每一個坐標(biāo)對表示一條直線。以圖2(d)為例，計算出22個坐標(biāo)值，如表1所示。

圖2 不規(guī)則多邊形區(qū)域填充

表1 平行線與多邊形輪廓的交點(diǎn)

根據(jù)表1中坐標(biāo)值，可以計算出每條平行線經(jīng)過的柵格單元個數(shù)及行列值，如表2所示。

表2 柵格單元的坐標(biāo)值

2.2 多邊形嵌套區(qū)域填充

環(huán)形多邊形是指在一個多邊形里面除去嵌套一個或多個其他多邊形的剩余部分。此時必須計算每條平行線與有關(guān)多邊形輪廓的所有交點(diǎn)，然后排序，配對輸出，如圖3(a)所示。

在圖3(a)中可以看到，多邊形acdefghija中嵌套了另一個多邊形ACDEFGHA，兩個多邊形各自有若干個狹長的區(qū)域且相互嵌套，彼此之間間距非常小，如夾角efg和DEF、夾角ghi和FGH之間縫隙過于狹窄，填充比較困難。通過計算平行線與兩個多邊形輪廓的交點(diǎn)，可以快速實現(xiàn)填充效果，但此時在交點(diǎn)配對時要注意區(qū)分，因為當(dāng)平行線還未與內(nèi)部多邊形相交時，只需要對平行線與外部多邊形交點(diǎn)配對輸出，當(dāng)平行線同時與兩個多邊形輪廓都有交點(diǎn)時，此時交點(diǎn)配對難度比較大，填充效果如圖圖3(b)所示。

(a) 嵌套多邊形 (b) 內(nèi)部多邊形繪制平行線 (c) 嵌套多邊形繪制平行線 圖3 間距值為9，傾斜角為22.5°

(a) 多邊形相交 (b) 嵌套多邊形繪制平行線圖4 間距值為5，傾斜角為-22.5°

圖3(b)表示的是在內(nèi)部多邊形ACDEFGHA繪制等間距平行線的效果，從圖中可以看到，有12條平行線，包含了24對坐標(biāo)值。在同樣的間距值條件下，外部多邊形acdefghija有30條平行線，包含了60對坐標(biāo)值。與內(nèi)部多邊形相比，外部多邊形多了36對坐標(biāo)值，根據(jù)該數(shù)值繪制出嵌套區(qū)域平行線如圖3(c)所示。

繪制嵌套多邊形平行線時，要考慮到平行線同時經(jīng)過內(nèi)、外多邊形輪廓，在圖3(c)中可以看到，平行線與外部多邊形有60個交點(diǎn)，與內(nèi)部多邊形有24個交點(diǎn)，從第18條平行線開始同時和兩個多邊形都有交點(diǎn)，第27條平行線離開內(nèi)部多邊形只和外部多邊形相交，即第18條到26條平行線在交點(diǎn)配對時，必須是外部多邊形輪廓交點(diǎn)與內(nèi)部多邊形輪廓交點(diǎn)配對，其余都是外部多邊形輪廓交點(diǎn)配對輸出。

2.3 多邊形相交區(qū)域填充

在區(qū)域填充中，當(dāng)兩個任意形狀多邊形相互相交時，一個多邊形為裁剪對象，另一個則是被裁剪對象，此時，被裁剪的多邊形分為內(nèi)側(cè)和外側(cè)兩部分。為了實現(xiàn)內(nèi)側(cè)或外側(cè)區(qū)域填充，需要運(yùn)用1.4節(jié)多邊形裁剪算法來實現(xiàn)，如圖4所示。在圖中可以看出，多邊形acdefghija和ACDEFA相交，交點(diǎn)集合為{a1，a2，a3，a4，a5，a6，a7，a8}，其中多邊形acdefghija是被裁剪對象，根據(jù)1.4節(jié)裁剪算法得出該多邊形被裁剪后得到的內(nèi)側(cè)多邊形為{a1，a2，a3，e，a4，D，a5，a6，a7，a8，A，a1}，利用等間距平行線填充算法對內(nèi)側(cè)多邊形填充，如圖4(b)所示。

3 數(shù)據(jù)分析

3.1 算法復(fù)雜度分析

算法的復(fù)雜度是衡量該算法優(yōu)劣的標(biāo)準(zhǔn)，包括空間復(fù)雜性和時間復(fù)雜性[8]。等間距平行線填充算法的計算量取決于平行線的數(shù)目，間距越小，填充效果越好，但交點(diǎn)越多，包含的柵格單元越多，計算量增大。對于普通的制圖，算法在時間上差別不明顯，以圖3(a)為例，算法的復(fù)雜度見表3。

表3 嵌套多邊形復(fù)雜度分析

3.2 算法通用性分析

等間距平行線區(qū)域填充算法取多邊形頂點(diǎn)中橫坐標(biāo)中的最小值作為平行線的初始值開始循環(huán)繪制，每循環(huán)一次繪制一條平行線，間隔等于設(shè)定的精度值，直到最后一條平行線的橫坐標(biāo)大于多邊形中橫坐標(biāo)最大值時停止循環(huán)，每一次循環(huán)判斷該條平行線與多邊形的所有邊是否存在交點(diǎn)，如果有則計算并保存交點(diǎn)坐標(biāo)，否則接著循環(huán)，直到該條平行線與每條邊都計算過，這就是等間距平行法的兩重循環(huán)原理，算法簡單，有較好的適用性。

3.3 技術(shù)難點(diǎn)分析

(1)裁剪算法中如何把交點(diǎn)分別插入兩個相交多邊形頂點(diǎn)集合。

在裁剪算法中，裁剪對象與被裁剪對象輪廓的交點(diǎn)值，需要分別存入到兩個多邊形頂點(diǎn)集合中，同時要保證插入到準(zhǔn)確的位置，如圖4(a)所示，被裁剪多邊形acdefghija輪廓有9條邊，從第一條邊ac開始判斷，是否與裁剪對象ACDEFGA相交，判斷依據(jù)如下：

max(xa1，xa2)

min(xa1，xa2)>max(xc1，xc2)或

max(ya1，ya2)

min(ya1，ya2)>max(yc1，yc2),

如果上述條件成立，則說明無交點(diǎn)。根據(jù)以上判斷依據(jù)，線段ac兩個端點(diǎn)橫坐標(biāo)最大值小于裁剪對象直線AC兩個端點(diǎn)最小值，說明無交點(diǎn)，線段cd兩個端點(diǎn)橫坐標(biāo)最大值大于線段AC兩個端點(diǎn)的最小值，說明有交點(diǎn)，則計算兩條線段的交點(diǎn)坐標(biāo)，分別插入到線段cd和AC兩個端點(diǎn)所在頂點(diǎn)集合中間的位置。

(2)如何實現(xiàn)平行線與多邊形輪廓配對輸出。

在一些比較復(fù)雜的多邊形區(qū)域中，包含多個凹進(jìn)或凸起部分，當(dāng)平行線同時經(jīng)過多個這些部分時，與之同時都有交點(diǎn)，此時需要對交點(diǎn)配對輸出。以圖3(b)為例，當(dāng)平行線同時與外多邊形acdefghija和內(nèi)多邊形ACDEFGHA輪廓相交時，此時每條平行線會計算出4個交點(diǎn)，此時第1、4交點(diǎn)為外部多邊形輪廓交點(diǎn)，第2、3為內(nèi)部多邊形輪廓交點(diǎn)，所以交點(diǎn)要分別配對。核心代碼如下：

for(int i=0；i

g.drawLine(tx[i]，ty[i]，tx[i+1]，ty[i+1])； //平行線還未與被嵌套的多邊形有交點(diǎn)

}

for(int i=z；i

g.drawLine(tx[i]，ty[i]，kkx[i-z]，kky[i-z])； //平行線與被嵌套的多邊形有交點(diǎn)

i++；

g.drawLine(kkx[i-z]，kky[i-z]，tx[i]，ty[i])； } //取內(nèi)部交點(diǎn)與外部交點(diǎn)配對輸出繪制直線

for(int i=zz+z；i<100；i=i+2){

g.drawLine(tx[i]，ty[i]，tx[i+1]，ty[i+1])；}//平行線離開被嵌套的多邊形沒有交點(diǎn)

(3)裁剪算法中如何創(chuàng)建內(nèi)側(cè)多邊形頂點(diǎn)集合。

在兩個相交多邊形內(nèi)側(cè)或外側(cè)區(qū)域填充，首先需要創(chuàng)建內(nèi)側(cè)或外側(cè)多邊形頂點(diǎn)集合，以圖4(a)為例，交點(diǎn)為a1、a2、a3、a4、a5、a6、a7、a8。按裁剪算法原理，先從被裁剪多邊形頂點(diǎn)集合開始搜索，當(dāng)遇到a1時，跳到裁剪對象頂點(diǎn)集合繼續(xù)搜索，當(dāng)遇到a2時再次跳到被裁剪對象繼續(xù)搜索下一個交點(diǎn)，直到所有8個交點(diǎn)被搜索一遍。關(guān)鍵代碼如下：

t=1； // 計數(shù)器，記錄交點(diǎn)個數(shù)

while (true){

if (t%2==1) // 在被裁剪多邊形中搜索

for(int j=0；j

If (ax[j]!=ex[t]&&ay[j]!=ey[t]){ //被裁剪對象頂點(diǎn)與交點(diǎn)集合頂點(diǎn)不一致

dx[k++]=ax[j]；

dy[k++]=ay[j]；} //把被裁剪對象頂點(diǎn)坐標(biāo)存入dx、dy數(shù)組

else {

dx[k++]=ex[t]；

dy[k++]=ey[t]； } //否則把交點(diǎn)集合頂點(diǎn)存入dx、dy數(shù)組

break；}

if (t%2==1) // 在裁剪多邊形中搜索

for(int jj=0；jj

If (cx[jj]!=ex[t]&&cy[jj]!=ey[t]){ //裁剪對象頂點(diǎn)與交點(diǎn)集合頂點(diǎn)不一致

dx[k++]=cx[jj]；

dy[k++]=cy[jj]；} //把裁剪對象頂點(diǎn)坐標(biāo)存入dx、dy數(shù)組

else {

dx[k++]=ex[t]；

dy[k++]=ey[t]； } //把交點(diǎn)集合頂點(diǎn)坐標(biāo)存入dx、dy數(shù)組

break；}

t++；

if (t>=8) // 交點(diǎn)搜索結(jié)束

break；

} } // dx[]、dy[]是保存內(nèi)側(cè)多邊形坐標(biāo)值

(4)如何實現(xiàn)柵格單元的快速填充。

基于柵格的填充是通過計算每條平行線經(jīng)過柵格單元的行列值，對每個柵格單元填充，此時要準(zhǔn)確計算每個單元的坐標(biāo)值，如圖5所示，表示的是第8條平行線經(jīng)過的柵格單元填充，因為每個單元大小一致，根據(jù)交點(diǎn)坐標(biāo)可以得出該條平行線穿越單元的個數(shù)，同時根據(jù)交點(diǎn)的橫坐標(biāo)或縱坐標(biāo)值，依據(jù)設(shè)定好的像元寬度值，以此推算每個像素單元的中心坐標(biāo)值，最后對所有單元賦予指定像素值。

圖5 柵格填充效果

4 小結(jié)

本文基于等間距平行線原理提出了一種區(qū)域填充算法，計算每條平行線與多邊形輪廓的交點(diǎn)，測算出每條平行線經(jīng)過的柵格單元行列值及坐標(biāo)，通過對所有的柵格單元進(jìn)行填充，從而實現(xiàn)了整個區(qū)域的快速填充。對于狹小區(qū)域或凹進(jìn)與凸出部位以及多個多邊形相互嵌套、裁剪等，都有較好的填充效果，具有良好的通用性。