一種強(qiáng)魯棒性自適應(yīng)活性邊表算法

師　碩　姚陳堃　于　洋

(河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院　天津 300401)

?

一種強(qiáng)魯棒性自適應(yīng)活性邊表算法

師碩姚陳堃于洋

(河北工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與軟件學(xué)院天津 300401)

摘要為提升多邊形的填充效率，在分析和比較常見填充算法后，以活性邊表算法為基礎(chǔ)，深入挖掘不同掃描方向上的求交次數(shù)及多邊形自交特性，提出一種強(qiáng)魯棒性自適應(yīng)活性邊表算法。新算法引入橫度和縱度的概念表示橫縱掃描方向上的求交次數(shù)，并以此為標(biāo)準(zhǔn)自適應(yīng)選擇掃描方向。此外，通過(guò)對(duì)活性邊表中相鄰交點(diǎn)的橫坐標(biāo)進(jìn)行檢測(cè)和糾正，正確而高效地填充了自交多邊形。經(jīng)實(shí)驗(yàn)驗(yàn)證，新算法靈活的自適應(yīng)性和高效的自交糾正方法，大大提高了時(shí)間效率和魯棒性。

關(guān)鍵詞多邊形填充自適應(yīng)掃描活性邊表算法自相交魯棒性

0引言

區(qū)域填充被廣泛應(yīng)用于真實(shí)感圖形顯示、圖像處理、機(jī)械制造和媒體廣告等領(lǐng)域[1,2]，尤其是近年來(lái)移動(dòng)設(shè)備上富媒體應(yīng)用的增多，對(duì)圖形填充算法的時(shí)空方面提出了更高的要求[3]。

常用的區(qū)域填充算法有逐點(diǎn)判斷算法、種子填充算法和掃描線填充算法[4,5]。逐點(diǎn)判斷算法基于像素，對(duì)繪圖窗口內(nèi)每一像素點(diǎn)進(jìn)行射線環(huán)繞探測(cè)來(lái)實(shí)現(xiàn)內(nèi)點(diǎn)判定，孤立地考慮像素點(diǎn)與區(qū)域間的關(guān)系，計(jì)算量較大[5]；種子填充算法需事先給定一像素點(diǎn)作為種子點(diǎn)，再以該種子點(diǎn)為起點(diǎn)朝四連通或八連通方向遞歸填充，但仍基于像素，且區(qū)域內(nèi)每一像素點(diǎn)均需入棧，易堆棧溢出[1,5]；掃描線填充算法也需給定一種子點(diǎn)，分別水平向右和向左地探測(cè)得到圖形邊界點(diǎn)，填充兩端點(diǎn)之間的線段，并讓該線段之上和之下的任意內(nèi)點(diǎn)入棧，繼而棧頂像素點(diǎn)出棧作為新的種子點(diǎn)，重復(fù)上述操作至?？誟6]。不難看出，掃描線填充算法中種子點(diǎn)入棧次數(shù)與掃描線條數(shù)相同，較種子填充算法大大減少了堆棧操作，時(shí)空開銷均有降低。

但隨著區(qū)域面積的增大，掃描線填充算法的出、入棧操作仍很頻繁[4]?；钚赃叡硭惴?，又稱有效邊表算法或多邊形填充算法，它充分挖掘了邊的連貫性和頂點(diǎn)間的約束關(guān)系，從而有效避免了復(fù)雜的計(jì)算和耗時(shí)的堆棧操作[7,8]。目前已有學(xué)者對(duì)該算法進(jìn)行了改進(jìn)，如文獻(xiàn)[9]中楊長(zhǎng)強(qiáng)等人提出了一種用水平掃描線與B樣條曲線求交的填充算法，文獻(xiàn)[10]中Al-Rawi I提出了一種鏈表與數(shù)組結(jié)合并分凸、凹和復(fù)合多邊形填充的算法等。

考慮到目前算法均單一方向地掃描多邊形，并且無(wú)法正確填充自交多邊形，本文提出一種能預(yù)判斷最佳掃描方向并糾正多邊形自交點(diǎn)的活性邊表算法。

1傳統(tǒng)的活性邊表算法

傳統(tǒng)的活性邊表算法讓掃描線以1像素的增量自下而上地掃描多邊形，如圖1所示，其中水平虛線為掃描線，空心圓點(diǎn)為掃描線與多邊形的交點(diǎn)。euv=pupv為多邊形的任一邊，它的上端點(diǎn)縱坐標(biāo)yv=ym，li與li+1(i=1,2,…,9)分別為當(dāng)前掃描線和下一條掃描線，它們與euv的交點(diǎn)分別為(xi,yi)和(xi+1,yi+1)。dx為交點(diǎn)橫坐標(biāo)的增量，為得出dx的計(jì)算公式，不妨假設(shè)euv所在直線方程為ax+by+c=0，斜率為k，易知：

(1)

dx=xi+1-xi

(2)

將式(1)代入式(2)可得：

(3)

再由li和li+1的步進(jìn)關(guān)系知：

yi+1-yi=1

(4)

將式(4)代入式(3)得：

(5)

填充前，需根據(jù)多邊形構(gòu)造新邊表NET，圖1中多邊形的NET如圖2所示。鄰接表每行的表頭結(jié)點(diǎn)代表一條掃描線，其后每個(gè)結(jié)點(diǎn)代表一條邊，其中關(guān)于邊結(jié)點(diǎn)的定義如下：

class Edge

{

double xi;

double dx;

intym;

Edge nextEdge;

}

圖1　掃描多邊形的過(guò)程

圖2　NET的邏輯結(jié)構(gòu)

另還需用活性邊表AET記錄當(dāng)前掃描線與多邊形的所有交點(diǎn)信息，圖2中掃描線l6的AET如圖3所示。

圖3AET的邏輯結(jié)構(gòu)

傳統(tǒng)的活性邊表算法的基本步驟如下：

Step1構(gòu)造NET與AET。

Step2刪除AET中ym和yi相等的所有邊結(jié)點(diǎn)，將NET中掃描線所在行的所有邊結(jié)點(diǎn)按xi升序插入AET。

Step3利用公式xi=xi+dx更新AET中各交點(diǎn)。

Step4對(duì)AET中交點(diǎn)兩兩配對(duì)，并填充其間的區(qū)域。

Step5掃描線步進(jìn)。若掃描線與多邊形有交點(diǎn)，則轉(zhuǎn)Step2;若無(wú)交點(diǎn)，則結(jié)束。

2強(qiáng)魯棒性自適應(yīng)活性邊表算法

圖4　橫縱鋸齒

定義2自下而上地掃描為縱向掃描，自左向右地掃描為橫向掃描，如圖5所示。

圖5　橫向與縱向掃描多邊形的情況對(duì)比

分析發(fā)現(xiàn)，傳統(tǒng)的活性邊表算法存在如下缺陷：1) 掃描方向單一，僅考慮縱向掃描，而事實(shí)上縱向并非總是最佳方向，如圖5所示的多邊形，其內(nèi)部縱鋸齒居多，若選擇縱向掃描，交點(diǎn)較多，計(jì)算量大，生成的配對(duì)區(qū)間也較多而小，直接導(dǎo)致填色次數(shù)與鏈表操作增多，而若選擇橫向掃描，則可一定程度地簡(jiǎn)化上述問(wèn)題；2) 當(dāng)輸入為自交多邊形時(shí)，將產(chǎn)生填充異常，算法的魯棒性不強(qiáng)。

針對(duì)上述問(wèn)題，本文提出一種強(qiáng)魯棒性自適應(yīng)活性邊表算法。該算法在填充前先對(duì)多邊形的形狀進(jìn)行預(yù)判斷，自動(dòng)調(diào)整掃描線的方向后再執(zhí)行傳統(tǒng)的活性邊表算法，且在更新AET時(shí)，對(duì)相鄰交點(diǎn)的xi進(jìn)行升序糾正，正確填充了自交多邊形。

2.1自適應(yīng)性

2.1.1掃描方向的確定

圖6　鋸齒與掃描線求交

掃描方向的確定依賴于快速、準(zhǔn)確且低運(yùn)算量的決策算法，本文通過(guò)分析掃描線與鋸齒的求交過(guò)程，得出了求交次數(shù)的數(shù)學(xué)公式，并給出了決策算法的描述。

現(xiàn)任取一多邊形的第k個(gè)鋸齒，其頂點(diǎn)集為{pk-1,pk,pk+1}，如圖6所示，分別橫向和縱向地掃描該鋸齒，易知線段pk-1pk與pkpk+1在掃描方向上的投影長(zhǎng)度之和即為求交次數(shù)，如式(6)、式(7)所示：

(6)

(7)

將式(6)、式(7)推廣到整個(gè)多邊形后，得式(8)、式(9)：

(8)

(9)

從式(8)、式(9)的求和過(guò)程可知，多邊形每條邊的求交次數(shù)被重復(fù)計(jì)算了一次，而最終只需比較Tx和Ty的大小即可確定掃描方向，故可繼續(xù)通過(guò)定義3化簡(jiǎn)。

定義3Dx和Dy為多邊形的橫度和縱度，它們分別表示橫向和縱向掃描多邊形的求交次數(shù)，也表征多邊形形狀在橫縱方向上的復(fù)雜程度。

(10)

(11)

2.1.2決策算法的描述

下面，采用偽代碼的形式給出決策算法的描述：

polygon:存儲(chǔ)多邊形頂點(diǎn)坐標(biāo)的數(shù)組

N:多邊形頂點(diǎn)數(shù)目

cur:當(dāng)前頂點(diǎn)下標(biāo)

rear:當(dāng)前頂點(diǎn)的后繼頂點(diǎn)下標(biāo)

abs:取絕對(duì)值

for(cur=0; cur< N; cur++)

{

rear = (cur + 1) % N;

Dx+= abs(polygon[rear].x - polygon[cur].x);

Dy+= abs(polygon[rear].y - polygon[cur].y);

}

if(Dx>Dy)

縱向掃描活性邊表算法;

else

橫向掃描活性邊表算法;

2.2自交糾正算法

傳統(tǒng)算法在填充自交多邊形時(shí)之所以產(chǎn)生異常，是因?yàn)橄嘟坏膬蓷l邊在更新各自的xi到其排列次序變?yōu)榻敌蚝?，并未采取措施以糾正為原來(lái)的升序。目前諸多算法采用在更新xi后加入起泡排序來(lái)解決，但這種方法孤立地考慮當(dāng)前AET中所有交點(diǎn)的有序性，而未從自交點(diǎn)產(chǎn)生原因的角度分析，故而產(chǎn)生了許多不必要的比較和判斷。

針對(duì)該問(wèn)題，本文用一種簡(jiǎn)單的交換算法替換起泡排序算法，其基本思想是：遍歷AET，若發(fā)現(xiàn)當(dāng)前邊結(jié)點(diǎn)與其后繼邊結(jié)點(diǎn)的xi成降序，即滿足edge·xi>(edge·next)·xi，則交換它們的位置。

為對(duì)比新舊自交糾正算法的效率，不妨假設(shè)問(wèn)題的規(guī)模為n，即當(dāng)前AET中有n個(gè)邊結(jié)點(diǎn)，其效率對(duì)比如表1所示。

表1　新舊自交糾正算法的時(shí)間效率對(duì)比

從時(shí)間復(fù)雜度看，交換算法較起泡排序算法降低了一個(gè)數(shù)量級(jí)；從比較次數(shù)看，當(dāng)n=1或n=2時(shí)兩種算法的比較次數(shù)相等，當(dāng)n>2時(shí)交換算法的比較次數(shù)更少。綜合看來(lái)，交換算法更具時(shí)間優(yōu)勢(shì)。

3實(shí)驗(yàn)分析

考慮到近年來(lái)移動(dòng)設(shè)備的廣泛普及，以及Android平臺(tái)較高的市場(chǎng)占有率，本文基于Android平臺(tái)，用Java語(yǔ)言編寫了測(cè)試程序，并在4英寸、480×854分辨率、雙核1.5 GHz和1.00 GB內(nèi)存的小米手機(jī)上運(yùn)行和測(cè)試。該部分選取了若干多邊形作為測(cè)試用例，其屬性數(shù)據(jù)如表2所示。共設(shè)計(jì)了三個(gè)實(shí)驗(yàn)，其中實(shí)驗(yàn)1用以比較常用填充算法與本文算法的時(shí)間效率，實(shí)驗(yàn)2用以比較縱向、橫向和自適應(yīng)方向掃描的活性邊表算法的時(shí)間效率，實(shí)驗(yàn)3給出了剪紙圖案和空心文字的實(shí)際填充效果。

表2　實(shí)驗(yàn)用多邊形的屬性數(shù)據(jù)

實(shí)驗(yàn)1選取四個(gè)具有典型特征的多邊形，每個(gè)多邊形分別用逐點(diǎn)判斷算法、種子填充算法、掃描線填充算法、傳統(tǒng)的活性邊表算法、自適應(yīng)活性邊表算法填充10 000次，并計(jì)算平均耗時(shí)，其填充效果如圖7所示，時(shí)間效率統(tǒng)計(jì)如表3所示。

圖7　實(shí)驗(yàn)1用多邊形及填充效果

填充算法圖7(a)圖7(b)圖7(c)圖7(d)種子填充算法溢出溢出溢出溢出逐點(diǎn)判斷算法957.232254.678456.11215626.77掃描線填充算法25.4953.09115.39208.50傳統(tǒng)的活性邊表算法4.7413.5742.9167.84自適應(yīng)活性邊表算法4.7610.2322.6059.89

深入分析表3，并對(duì)照表2可以發(fā)現(xiàn)：

1) 種子填充算法空間開銷較大，不宜在內(nèi)存緊缺的移動(dòng)平臺(tái)使用；逐點(diǎn)判斷算法的時(shí)間效率較低。

2) 掃描線填充算法的時(shí)間效率受區(qū)域面積影響較大，而活性邊表算法則相對(duì)穩(wěn)定。

3) 自適應(yīng)活性邊表算法較傳統(tǒng)的活性邊表算法時(shí)間效率有所提高，且橫縱度差距愈大愈明顯。

實(shí)驗(yàn)2選取偏橫度、偏縱度和橫縱度相當(dāng)?shù)娜齻€(gè)多邊形，每個(gè)多邊形分別用縱向、橫向和自適應(yīng)方向掃描的活性邊表算法填充10 000次，并計(jì)算平均耗時(shí)。其中縱向和橫向掃描的活性邊表算法采用起泡排序算法進(jìn)行自交糾正，而自適應(yīng)活性邊表算法采用交換算法，其填充效果如圖8(a)、(b)、(c)所示，時(shí)間效率統(tǒng)計(jì)如表4所示，時(shí)間效率對(duì)比如圖9所示。另為驗(yàn)證自交糾正與否對(duì)填充結(jié)果的影響，采用不含自交糾正的活性邊表算法對(duì)圖8(c)多邊形填充，效果如圖8(d)所示，可見產(chǎn)生填充異常。

圖8　實(shí)驗(yàn)2用多邊形及填充效果

填充算法圖8(a)圖8(b)圖8(c)縱向掃描的(傳統(tǒng)的)活性邊表算法12.9560.5795.05橫向掃描的活性邊表算法62.5221.37108.71自適應(yīng)活性邊表算法10.7317.9267.59

圖9　三種掃描方式的時(shí)間效率對(duì)比

深入分析圖9，并對(duì)照表2可以發(fā)現(xiàn)：

1) 自適應(yīng)活性邊表算法可自適應(yīng)地找到耗時(shí)較少的掃描方向，驗(yàn)證了新算法自適應(yīng)結(jié)果的正確性。

2) 自適應(yīng)活性邊表算法的耗時(shí)比其余兩種算法中耗時(shí)較少者還少，尤以圖8(c)最明顯，證明交換算法較起泡排序算法更能加快自交多邊形的填充速率，且自交程度愈復(fù)雜愈明顯。

實(shí)驗(yàn)3采用本文的自適應(yīng)活性邊表算法填充剪紙圖案和空心文字，效果如圖10和圖11所示。需要指出的兩點(diǎn)是：1) 任意形狀的輪廓線均可由若干距離較短的線段構(gòu)成，進(jìn)而任意形狀的圖形也可用近似的多邊形代替[11]；2) 活性邊表算法的適用范圍可推廣至含有若干孔洞的連通區(qū)域，此時(shí)只需將區(qū)域分為內(nèi)、外多邊形，并為其分別構(gòu)造NET即可[12]。

圖10　剪紙圖案及填充效果

圖11　空心文字及填充效果

4結(jié)語(yǔ)

區(qū)域填充是計(jì)算機(jī)圖形學(xué)中的重要問(wèn)題，在諸多領(lǐng)域也有著廣泛的應(yīng)用，其中活性邊表算法最常用也最可觀。然而傳統(tǒng)的活性邊表算法固定了掃描方向，未根據(jù)多邊形的形狀對(duì)掃描方向做出自適應(yīng)地調(diào)整，對(duì)于自交多邊形的特殊情況，也未深入挖掘其特性，造成了冗余的操作。本文從掃描線與多邊形的求交次數(shù)進(jìn)行分析，引入橫度和縱度來(lái)分別表征橫向和縱向掃描時(shí)的求交次數(shù)。通過(guò)比較它們的大小選擇最佳的掃描方向，達(dá)到自適應(yīng)的效果。后又采用交換算法糾正自交點(diǎn)，確保了正確而高效的填充。經(jīng)理論和實(shí)驗(yàn)分析可見，本文算法簡(jiǎn)單易行，靈活智能，且填充效率也有較大提升。

參考文獻(xiàn)

[1] 徐勝攀,劉正軍,左志權(quán),等.一種改進(jìn)的活性邊表區(qū)域填充算法[J].計(jì)算機(jī)工程與應(yīng)用,2014,50(17):178-181.

[2] 唐永勇,馮劍,杜振華,等.基于頂點(diǎn)的多邊形掃描轉(zhuǎn)換[J].計(jì)算機(jī)與現(xiàn)代化,2011(1):117-120.

[3] 張?bào)K先,羅蕾,姜帆.移動(dòng)設(shè)備上富媒體場(chǎng)景渲染優(yōu)化策略[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2010,22(8):1272-1278.

[4] 孫家廣,楊長(zhǎng)貴.計(jì)算機(jī)圖形學(xué)[M].3版.北京:清華大學(xué)出版社,2002:170-205.

[5] 吳力心,申閆春.區(qū)域填充算法的研究與應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件,1994(2):31-37.

[6] 張榮國(guó),劉焜.新區(qū)入棧的區(qū)域填充掃描線算法[J].計(jì)算機(jī)工程,2006,32(6):63-64.

[7] Gordon D,Peterson M A,Reynolds R A.Fast polygon scan conversion with medical applications[J].Computer Graphics and Applications,IEEE,1994,14(6):20-27.

[8] 陳萬(wàn)領(lǐng),黃培,陳卓寧,等.一種新的任意多邊形的快速填充算法[J].計(jì)算機(jī)應(yīng)用與軟件,1999(4):23-26.

[9] 楊長(zhǎng)強(qiáng),彭延軍,鄭永果.一種封閉B樣條曲線的掃描線填充算法[J].系統(tǒng)仿真學(xué)報(bào),2006,18(S1):12-13.

[10] AlRawi I.Implementation of an Efficient Scan-Line Polygon Fill Algorithm[J].Computer Engineering and Intelligent Systems,2014,5(4):22-28.

[11] 周天娟,張鐵中,楊麗.草莓采摘機(jī)器人的研究:Ⅲ.掃描線填充算法在草莓圖像孔洞填充中的應(yīng)用[J].中國(guó)農(nóng)業(yè)大學(xué)學(xué)報(bào),2007,12(2):67-71.

[12] 張志龍,李吉成,沈振康.一種新的快速?gòu)?fù)雜連通區(qū)域掃描線填充算法[J].計(jì)算機(jī)工程與應(yīng)用,2004(31):6-8.

收稿日期：2015-02-03。天津市科技計(jì)劃項(xiàng)目(14RCGFGX008 46)；河北省教育廳高等學(xué)?？茖W(xué)研究計(jì)劃項(xiàng)目(Z2013078)。師碩，講師，主研領(lǐng)域：圖像特征提取，圖形圖像處理，網(wǎng)絡(luò)編程。姚陳堃，本科生。于洋，講師。

中圖分類號(hào)TP301.6

文獻(xiàn)標(biāo)識(shí)碼A

DOI:10.3969/j.issn.1000-386x.2016.07.049

AN ACTIVE-EDGE-TABLE FILLING ALGORITHM WITH ADAPTABILITY AND ROBUSTNESS

Shi ShuoYao ChenkunYu Yang

(SchoolofComputerScienceandEngineering,HebeiUniversityofTechnology,Tianjin300401,China)

AbstractTo improve the efficiency of polygon filling, after analysing and comparing several common filling algorithms, the paper puts forward an active-edge-table filling algorithm with adaptability and robustness, which is based on active-edge-table algorithm, by thoroughly mining the number of crossover requests in different scanning directions and the self-intersection character of polygon. The new algorithm introduces the concept of horizontal extent and vertical extent to represent the number of crossover requests in horizontal and vertical directions of scanning, and takes them as the standard to adaptively choose the right scanning direction. In addition, by checking and correcting the coordinates of the adjoining crossover points in active-edge-table, this algorithm fills the self-intersected polygon correctly and efficiently. It is verified by experiment that the new algorithm greatly improves the time efficiency and robustness owing to its flexible adaptability and efficient self-intersection correcting way.

KeywordsPolygon fillingAdaptability scanActive-edge-table algorithmSelf-intersectionRobustness