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

邱國清

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

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

1 等間距平行線算法

1.1 等間距平行線基本原理

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

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

(1)

(2)

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

(3)

(3)根據(jù)斜率公式計算交點坐標值，即

(4)

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

(5)

(6)

1.2 算法描述

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

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

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

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

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

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

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

1.3 區(qū)域柵格化

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

1.4 裁剪算法

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

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

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

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

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

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

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

2.1 狹窄區(qū)域填充

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

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

表1 平行線與多邊形輪廓的交點

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

表2 柵格單元的坐標值

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

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

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

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

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

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

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

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

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

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

3.1 算法復雜度分析

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

表3 嵌套多邊形復雜度分析

3.2 算法通用性分析

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

3.3 技術難點分析

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

在裁剪算法中，裁剪對象與被裁剪對象輪廓的交點值，需要分別存入到兩個多邊形頂點集合中，同時要保證插入到準確的位置，如圖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),

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

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

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

for(int i=0；i

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

}

for(int i=z；i

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

i++；

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

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

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

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

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

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

while (true){

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

for(int j=0；j

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

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

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

else {

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

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

break；}

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

for(int jj=0；jj

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

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

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

else {

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

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

break；}

t++；

if (t>=8) // 交點搜索結束

break；

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

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

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

圖5 柵格填充效果

4 小結

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