一種強魯棒性自適應活性邊表算法

師　碩　姚陳堃　于　洋

(河北工業大學計算機科學與軟件學院　天津 300401)

?

一種強魯棒性自適應活性邊表算法

師碩姚陳堃于洋

(河北工業大學計算機科學與軟件學院天津 300401)

摘要為提升多邊形的填充效率，在分析和比較常見填充算法后，以活性邊表算法為基礎，深入挖掘不同掃描方向上的求交次數及多邊形自交特性，提出一種強魯棒性自適應活性邊表算法。新算法引入橫度和縱度的概念表示橫縱掃描方向上的求交次數，并以此為標準自適應選擇掃描方向。此外，通過對活性邊表中相鄰交點的橫坐標進行檢測和糾正，正確而高效地填充了自交多邊形。經實驗驗證，新算法靈活的自適應性和高效的自交糾正方法，大大提高了時間效率和魯棒性。

關鍵詞多邊形填充自適應掃描活性邊表算法自相交魯棒性

0引言

區域填充被廣泛應用于真實感圖形顯示、圖像處理、機械制造和媒體廣告等領域[1,2]，尤其是近年來移動設備上富媒體應用的增多，對圖形填充算法的時空方面提出了更高的要求[3]。

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

但隨著區域面積的增大，掃描線填充算法的出、入棧操作仍很頻繁[4]。活性邊表算法，又稱有效邊表算法或多邊形填充算法，它充分挖掘了邊的連貫性和頂點間的約束關系，從而有效避免了復雜的計算和耗時的堆棧操作[7,8]。目前已有學者對該算法進行了改進，如文獻[9]中楊長強等人提出了一種用水平掃描線與B樣條曲線求交的填充算法，文獻[10]中Al-Rawi I提出了一種鏈表與數組結合并分凸、凹和復合多邊形填充的算法等。

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

1傳統的活性邊表算法

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

(1)

dx=xi+1-xi

(2)

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

(3)

再由li和li+1的步進關系知：

yi+1-yi=1

(4)

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

(5)

填充前，需根據多邊形構造新邊表NET，圖1中多邊形的NET如圖2所示。鄰接表每行的表頭結點代表一條掃描線，其后每個結點代表一條邊，其中關于邊結點的定義如下：

class Edge

{

double xi;

double dx;

intym;

Edge nextEdge;

}

圖1　掃描多邊形的過程

圖2　NET的邏輯結構

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

圖3AET的邏輯結構

傳統的活性邊表算法的基本步驟如下：

Step1構造NET與AET。

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

Step3利用公式xi=xi+dx更新AET中各交點。

Step4對AET中交點兩兩配對，并填充其間的區域。

Step5掃描線步進。若掃描線與多邊形有交點，則轉Step2;若無交點，則結束。

2強魯棒性自適應活性邊表算法

圖4　橫縱鋸齒

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

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

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

針對上述問題，本文提出一種強魯棒性自適應活性邊表算法。該算法在填充前先對多邊形的形狀進行預判斷，自動調整掃描線的方向后再執行傳統的活性邊表算法，且在更新AET時，對相鄰交點的xi進行升序糾正，正確填充了自交多邊形。

2.1自適應性

2.1.1掃描方向的確定

圖6　鋸齒與掃描線求交

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

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

(6)

(7)

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

(8)

(9)

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

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

(10)

(11)

2.1.2決策算法的描述

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

polygon:存儲多邊形頂點坐標的數組

N:多邊形頂點數目

cur:當前頂點下標

rear:當前頂點的后繼頂點下標

abs:取絕對值

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自交糾正算法

傳統算法在填充自交多邊形時之所以產生異常，是因為相交的兩條邊在更新各自的xi到其排列次序變為降序后，并未采取措施以糾正為原來的升序。目前諸多算法采用在更新xi后加入起泡排序來解決，但這種方法孤立地考慮當前AET中所有交點的有序性，而未從自交點產生原因的角度分析，故而產生了許多不必要的比較和判斷。

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

為對比新舊自交糾正算法的效率，不妨假設問題的規模為n，即當前AET中有n個邊結點，其效率對比如表1所示。

表1　新舊自交糾正算法的時間效率對比

從時間復雜度看，交換算法較起泡排序算法降低了一個數量級；從比較次數看，當n=1或n=2時兩種算法的比較次數相等，當n>2時交換算法的比較次數更少。綜合看來，交換算法更具時間優勢。

3實驗分析

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

表2　實驗用多邊形的屬性數據

實驗1選取四個具有典型特征的多邊形，每個多邊形分別用逐點判斷算法、種子填充算法、掃描線填充算法、傳統的活性邊表算法、自適應活性邊表算法填充10 000次，并計算平均耗時，其填充效果如圖7所示，時間效率統計如表3所示。

圖7　實驗1用多邊形及填充效果

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

深入分析表3，并對照表2可以發現：

1) 種子填充算法空間開銷較大，不宜在內存緊缺的移動平臺使用；逐點判斷算法的時間效率較低。

2) 掃描線填充算法的時間效率受區域面積影響較大，而活性邊表算法則相對穩定。

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

實驗2選取偏橫度、偏縱度和橫縱度相當的三個多邊形，每個多邊形分別用縱向、橫向和自適應方向掃描的活性邊表算法填充10 000次，并計算平均耗時。其中縱向和橫向掃描的活性邊表算法采用起泡排序算法進行自交糾正，而自適應活性邊表算法采用交換算法，其填充效果如圖8(a)、(b)、(c)所示，時間效率統計如表4所示，時間效率對比如圖9所示。另為驗證自交糾正與否對填充結果的影響，采用不含自交糾正的活性邊表算法對圖8(c)多邊形填充，效果如圖8(d)所示，可見產生填充異常。

圖8　實驗2用多邊形及填充效果

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

圖9　三種掃描方式的時間效率對比

深入分析圖9，并對照表2可以發現：

1) 自適應活性邊表算法可自適應地找到耗時較少的掃描方向，驗證了新算法自適應結果的正確性。

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

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

圖10　剪紙圖案及填充效果

圖11　空心文字及填充效果

4結語

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

參考文獻

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

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

[3] 張驥先,羅蕾,姜帆.移動設備上富媒體場景渲染優化策略[J].計算機輔助設計與圖形學學報,2010,22(8):1272-1278.

[4] 孫家廣,楊長貴.計算機圖形學[M].3版.北京:清華大學出版社,2002:170-205.

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

[6] 張榮國,劉焜.新區入棧的區域填充掃描線算法[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] 陳萬領,黃培,陳卓寧,等.一種新的任意多邊形的快速填充算法[J].計算機應用與軟件,1999(4):23-26.

[9] 楊長強,彭延軍,鄭永果.一種封閉B樣條曲線的掃描線填充算法[J].系統仿真學報,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].中國農業大學學報,2007,12(2):67-71.

[12] 張志龍,李吉成,沈振康.一種新的快速復雜連通區域掃描線填充算法[J].計算機工程與應用,2004(31):6-8.

收稿日期：2015-02-03。天津市科技計劃項目(14RCGFGX008 46)；河北省教育廳高等學校科學研究計劃項目(Z2013078)。師碩，講師，主研領域：圖像特征提取，圖形圖像處理，網絡編程。姚陳堃，本科生。于洋，講師。

中圖分類號TP301.6

文獻標識碼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