邱國(guó)清

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

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

1 等間距平行線算法

1.1 等間距平行線基本原理

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

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

(1)

(2)

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

(3)

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

(4)

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

(5)

(6)

1.2 算法描述

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

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

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

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

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

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

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

1.3 區(qū)域柵格化

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

1.4 裁剪算法

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

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

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

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

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

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

2 數(shù)據(jù)驗(yàn)證

2.1 狹窄區(qū)域填充

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 算法通用性分析

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

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

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

在裁剪算法中，裁剪對(duì)象與被裁剪對(duì)象輪廓的交點(diǎn)值，需要分別存入到兩個(gè)多邊形頂點(diǎn)集合中，同時(shí)要保證插入到準(zhǔn)確的位置，如圖4(a)所示，被裁剪多邊形acdefghija輪廓有9條邊，從第一條邊ac開始判斷，是否與裁剪對(duì)象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兩個(gè)端點(diǎn)橫坐標(biāo)最大值小于裁剪對(duì)象直線AC兩個(gè)端點(diǎn)最小值，說明無交點(diǎn)，線段cd兩個(gè)端點(diǎn)橫坐標(biāo)最大值大于線段AC兩個(gè)端點(diǎn)的最小值，說明有交點(diǎn)，則計(jì)算兩條線段的交點(diǎn)坐標(biāo)，分別插入到線段cd和AC兩個(gè)端點(diǎn)所在頂點(diǎn)集合中間的位置。

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

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

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)配對(duì)輸出繪制直線

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)集合。

在兩個(gè)相交多邊形內(nèi)側(cè)或外側(cè)區(qū)域填充，首先需要?jiǎng)?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時(shí)，跳到裁剪對(duì)象頂點(diǎn)集合繼續(xù)搜索，當(dāng)遇到a2時(shí)再次跳到被裁剪對(duì)象繼續(xù)搜索下一個(gè)交點(diǎn)，直到所有8個(gè)交點(diǎn)被搜索一遍。關(guān)鍵代碼如下：

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

while (true){

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

for(int j=0；j

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

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

dy[k++]=ay[j]；} //把被裁剪對(duì)象頂點(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]){ //裁剪對(duì)象頂點(diǎn)與交點(diǎn)集合頂點(diǎn)不一致

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

dy[k++]=cy[jj]；} //把裁剪對(duì)象頂點(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)如何實(shí)現(xiàn)柵格單元的快速填充。

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

圖5 柵格填充效果

4 小結(jié)

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