徐勝攀，劉正軍，左志權(quán)，程耀東

1.蘭州交通大學(xué)測繪與地理信息學(xué)院，蘭州 730071

2.中國測繪科學(xué)研究院，北京 100830

一種改進(jìn)的活性邊表區(qū)域填充算法

徐勝攀1，2，劉正軍2，左志權(quán)2，程耀東1

1.蘭州交通大學(xué)測繪與地理信息學(xué)院，蘭州 730071

2.中國測繪科學(xué)研究院，北京 100830

為提高區(qū)域填充效率，對三種常見的區(qū)域填充算法進(jìn)行了介紹和分析，并對其中優(yōu)勢較為明顯的活性邊表區(qū)域填充算法進(jìn)行了進(jìn)一步改進(jìn)。改進(jìn)算法針對原始算法的不足，充分利用多邊形頂點信息，建立了活性邊動態(tài)發(fā)現(xiàn)機制，使得算法時間效率和空間效率都得到提高；同時，為填充自相交多邊形，又提出一種簡單有效的基于掃描線的多邊形自相交點探測方法，使得算法的適用性得到進(jìn)一步增強。實驗結(jié)果表明，算法的改進(jìn)取得了很好的效果。

區(qū)域填充；活性邊表；動態(tài)發(fā)現(xiàn)機制；自相交

1 引言

區(qū)域填充是指用一種顏色或圖案來填充一個二維區(qū)域[1]，它是計算機圖形學(xué)和數(shù)字圖像處理領(lǐng)域的一個基本操作[2-3]，也是計算機應(yīng)用的一個重要方面，在計算機輔助設(shè)計、真實感圖形顯示、動畫、圖像處理等實際領(lǐng)域中有著廣泛的應(yīng)用[4-5]。填充算法的優(yōu)劣直接影響著圖形顯示的速度和精確性。

常見的區(qū)域填充算法主要有邊標(biāo)識算法、種子填充算法和活性邊表算法[6-7]。邊標(biāo)識算法[1，6]是基于像素的填充算法，填充過程中需要不斷地讀取像素，以確定是否到達(dá)邊界，效率較低，目前應(yīng)用并不多。種子填充是研究較為活躍的算法，分為經(jīng)典的種子填充算法和基于掃描線的種子填充算法[7-8]，目前后者已出現(xiàn)了許多改進(jìn)算法[3，9-10]。但種子填充算法有其固有的缺點：仍然是基于像素的填充算法；存在大量的出、入棧操作，時間效率不高，空間開銷較大；在填充前需要先確定種子點，并賦予填充色，過程較為繁瑣；一般適用于填充連通多邊形，對非連通多邊形則較為麻煩。

活性邊表算法也叫有效邊表算法[1]，它是一種基于掃描線的算法，算法充分利用了掃描線的連貫性和多邊形邊的連貫性?；舅枷胧怯靡粭l水平掃描線自下而上對多邊形進(jìn)行掃描，對每一個Y值處的掃描線求出屬于多邊形內(nèi)部的區(qū)段，對這些內(nèi)部區(qū)段進(jìn)行填充。這種算法基本著眼點是邊，可以對多邊形實現(xiàn)較為快速的全自動填充。

然而，傳統(tǒng)的活性邊表算法也存在顯著的特點：它在進(jìn)行正式填充之前需要先對多邊形進(jìn)行預(yù)處理，建立關(guān)于每一條掃描線的活性邊列表；在正式填充階段，每當(dāng)?shù)竭_(dá)一條新的掃描線時，又要對上一條掃描線對應(yīng)的活性邊列表進(jìn)行判斷和處理；另外原始填充算法并不針對自相交多邊形。目前對該算法已有學(xué)者提出一些改進(jìn)思想，如文獻(xiàn)[11]中馬輝等提出的基于頂點與鄰邊相關(guān)性對多邊形進(jìn)行分割的一種填充算法，文獻(xiàn)[12]中唐永勇等提出的基于“有效頂點”概念對多邊形按頂點序號掃描的一種填充算法。

在深入研究前人成果的基礎(chǔ)上，結(jié)合多邊形自身特性，本文提出一種新的改進(jìn)算法。新算法充分利用多邊形頂點信息，基于多邊形頂點編號的連續(xù)性和多邊形邊的鄰接關(guān)系，建立了活性邊的動態(tài)發(fā)現(xiàn)機制，避免了原始算法中對多邊形的預(yù)處理過程，節(jié)省了大量的時間和空間，同時后續(xù)填充過程也進(jìn)一步得到優(yōu)化。同時，提出一種基于掃描線的多邊形自相交點探測方法，使得算法對各種形式的自相交多邊形都能進(jìn)行正確填充。

下面，先對傳統(tǒng)活性邊表算法基本處理過程做一個簡單的介紹，然后，針對傳統(tǒng)算法的不足，提出改進(jìn)思想和相應(yīng)算法。

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

傳統(tǒng)的活性邊表算法是一種基于掃描線的算法[1]。在填充之前，需要先對多邊形進(jìn)行預(yù)處理，建立初始的、關(guān)于每一條掃描線的活性邊列表。活性邊列表用一個鄰接表存儲，鄰接表的每一行關(guān)聯(lián)一條掃描線，行中的每一個結(jié)點對應(yīng)一條活性邊。每一個活性邊結(jié)點至少存放以下三個數(shù)據(jù)：

x：掃描線與該邊交點的x坐標(biāo)。

?x：該邊從當(dāng)前掃描線到下一條掃描線之間的x增量。

Ymax：邊的最大y值。

如圖1所示，圖1（a）為一個多邊形及其頂點坐標(biāo)，圖1（b）中是與該多邊形對應(yīng)的鄰接表。

填充時，用一根掃描線自下而上掃描多邊形，根據(jù)當(dāng)前掃描線的活性邊列表確定掃描線與多邊形邊的交點，對交點按奇偶性進(jìn)行兩兩配對（掃描線與多邊形相交時，如果按一定的方向追蹤交點，首先遇到的必然是入交點（序號為奇數(shù)），然后是出交點（序號為偶數(shù)），依此類推……入交點和出交點之間的區(qū)段就是多邊形的內(nèi)部區(qū)域），填充配對點之間的區(qū)域；掃描線上移，首先檢查上條掃描線的活性邊列表，如果某活性邊結(jié)點的ymax等于當(dāng)前掃描線的Y值，則將該結(jié)點從活性邊列表刪除，否則，將該結(jié)點加入當(dāng)前活性邊列表，保持各活性邊結(jié)點按X值遞增排列。

掃描線繼續(xù)上移，直到遍歷完整個鄰接表。

圖1 一個多邊形及其對應(yīng)的活性邊表

3 活性邊表算法改進(jìn)算法

3.1 改進(jìn)的活性邊表算法基本思想

傳統(tǒng)的活性邊表算法在掃描之前需要先建立關(guān)于整個多邊形的鄰接表以存儲初始活性邊，在填充階段又要對每一條掃描線的前一條掃描線對應(yīng)的活性邊列表進(jìn)行判斷和處理，過程較為麻煩。當(dāng)多邊形較復(fù)雜時，需要較大的空間開銷和時間開銷。

事實上，傳統(tǒng)算法對多邊形頂點信息利用不夠：根據(jù)頂點編號的連續(xù)性和多邊形邊的鄰接關(guān)系，不需要事先存儲活性邊表，活性邊總能在掃描線移動到新的頂點處時被發(fā)現(xiàn)。

可以對多邊形各頂點按逆時針順序編號，將頂點編號存入一個數(shù)組，并將數(shù)組按頂點的Y坐標(biāo)升序排列。填充時，沿Y軸自下而上掃描多邊形。開始時活性邊表為空，每到一個新的頂點處時，通過多邊形頂點編號及其連續(xù)性即可找到鄰接該頂點的兩條邊，如果邊的Ymax大于當(dāng)前掃描線的Y值，則將該邊加入活性邊表，保持按X升序排列；否則，表明該活性邊已處理完畢，將其從活性邊表刪除。然后求取當(dāng)前掃描線與各活性邊的交點，對交點進(jìn)行兩兩配對，填充配對點之間的區(qū)域。掃描線不斷上移，直到到達(dá)Y最大值處的多邊形頂點。

與原始算法相比，這是一種動態(tài)發(fā)現(xiàn)活性邊的機制。算法經(jīng)過這樣改進(jìn)之后，取得了以下幾點顯著效果：

（1）無需對多邊形進(jìn)行預(yù)處理以建立活性邊鄰近表，從而節(jié)省了計算時間和存儲活性邊的空間。

（2）不必在每一條掃描線處都檢查上一條掃描線的活性邊數(shù)組，省去了大量的判斷和處理過程，整個填充過程變得更加流暢。

（3）經(jīng)過排序后，在上下兩個多邊形頂點之間，由于不存在活性邊結(jié)點，避免了原始算法中多活性邊結(jié)點的冗余判斷，進(jìn)一步提高了算法效率。

3.2 正確填充自相交多邊形

原始算法并不針對自相交多邊形，對這部分內(nèi)容，文獻(xiàn)中也很少有介紹?；诖耍疚奶岢鲆环N簡單有效的多邊形自相交點探測方法，以實現(xiàn)對自相交多邊形的正確填充。

自相交多邊形是指不共端點的邊存在相交情形的多邊形，邊的交點即為多邊形的自相交點。正確填充自相交多邊形，其關(guān)鍵在于能準(zhǔn)確發(fā)現(xiàn)自相交點。一種簡單的方法是對多邊形邊進(jìn)行兩兩求交，其時間復(fù)雜度為O(n2)，涉及到邊的相交檢測和交點計算，過程麻煩。本文提出一種新的方法，如圖2，在自相交處之前，點A在點B的前面，而在自相交之后，點A′在點B′的后面，因此，只需在自相交處交換兩個活性邊結(jié)點的前后順序即可，這樣在掃描線填充時就能正確完成交點配對，實現(xiàn)對自相交多邊形的正確填充。理論上講，在自相交處，兩條多邊形邊的X坐標(biāo)應(yīng)該相等，但由于計算機存儲數(shù)據(jù)時舍入誤差的存在，交點通過X值相等或X值之差的絕對值小于某一誤差限的方法很難以被探測。此時，將方案調(diào)整如下：掃描過程中處理活性邊結(jié)點時，比較當(dāng)前結(jié)點的X坐標(biāo)與前面結(jié)點的X坐標(biāo)，如果小于或等于前面結(jié)點的X坐標(biāo)值，則表明當(dāng)前處在自相交點或剛剛經(jīng)過自相交點，這時交換這兩個結(jié)點的前后位置即可。

圖2 正確填充自相交多邊形

需要說明的是，在面對較為復(fù)雜的多邊形自相交情形時，多邊形的內(nèi)部和外部甚至變得難于確定。本文對自相交多邊形的內(nèi)部和外部并不作特別規(guī)定，仍是基于普通多邊形內(nèi)、外部規(guī)則進(jìn)行處理，處理的根據(jù)仍是基于交點配對原理：如果按一定的方向追蹤交點，首先遇到的必然是入交點，然后是出交點，依此類推……入交點和出交點之間的區(qū)段就是多邊形的內(nèi)部區(qū)域。

這種方法應(yīng)該是有道理的。如果從足夠遠(yuǎn)的區(qū)域靠近多邊形，開始必然位于多邊形外部，然后遇到多邊形的邊界，也就是入交點，然后必然來到多邊形內(nèi)部（因為多邊形邊界將其內(nèi)部和外部分開了）；繼續(xù)移動，同樣首先將遇到邊界，也就是出交點，然后必然來到多邊形外部（同樣是因為多邊形邊界將其內(nèi)部和外部分開）。

3.3 算法的其他關(guān)鍵過程

（1）活性邊的發(fā)現(xiàn)與刪除

原始的活性邊表算法基于預(yù)先建立的鄰接表來發(fā)現(xiàn)活性邊。改進(jìn)算法是先建立一個存放多邊形頂點編號的數(shù)組，依據(jù)頂點編號的連續(xù)性在掃描過程中動態(tài)發(fā)現(xiàn)活性邊。

（2）掃描線與活性邊交點坐標(biāo)的計算

計算活性邊上某Y值處對應(yīng)點的X坐標(biāo)，容易想到的方法是利用直線方程f(x，y)=0，將Y帶入直線方程求解X。但由于Y是按d y=1累加的，因此有更簡單的方法：只需要求出d y=1對應(yīng)的d x即可，則

其中，d x=1/k，k為直線斜率。

在計算過程中，及時保存當(dāng)前x，則下一個x可根據(jù)上述公式直接計算。

3.4 算法描述

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

1.定義數(shù)組ptID[N]，用于存儲多邊形的N個頂點的序號，并將ptID[]內(nèi)的各元素按頂點的Y坐標(biāo)升序排列

2.建立活性邊表，置初始活性邊表為空

3.for：i=0 to N-1

3.1 找到id=ptID[i]的多邊形頂點，將當(dāng)前掃描線的Y坐標(biāo)作為當(dāng)前掃描線的Y值

3.2 找到與當(dāng)前頂點相關(guān)聯(lián)的另外兩條邊，如果邊的Ymax大于掃描線的Y值，則將該邊加入活性邊列表，保持結(jié)點按X大小升序排列；否則，如果該邊在活性邊列表，則將該邊從活性邊表刪除

3.3 while（Y＜point[id+1].y）

3.3.1 計算當(dāng)前掃描線與各活性邊的交點，按交點出現(xiàn)的先后順序依次兩兩配對，填充配對交點之間的多邊形區(qū)域。在此過程中，如果發(fā)現(xiàn)后面一個結(jié)點的X值小于或等于前面一個結(jié)點的X值，說明出現(xiàn)了自相交情形，則交換這兩個結(jié)點的前后位置

3.3.2 Y++

4.算法結(jié)束

4 實驗與分析

為檢驗本文算法，設(shè)計了兩組實驗。

圖3 實驗多邊形及其填充效果圖

第一組實驗用于檢測本文算法的填充正確性。實驗中選取了一個四個多邊形，分別代表了四種不同的情形。如圖3所示，圖（a）為一個基本的簡單多邊形；圖（b）也為簡單多邊形，但有多條水平邊，且各水平邊所在是掃描線上有很多Y值相同的點（圖中B、D、G、H，C、E、F，S、R、O、M、J，O、N、L、K分別處在四條掃描線上）；圖（c）為一個自相交多邊形，其中，BC、DE，JA、HI分別自相交，DE、EF、FG、GH構(gòu)成了多次自相交；圖（d）中，BC、DE、FG三條邊相交于一點。

從填充效果上可以看到，本文算法對上述列舉出的各類多邊形均進(jìn)行了正確填充。

第二組實驗用于測試算法填充效率。為方便填充自相交多邊形，比較與原始算法的運算效率，將本文正確填充自相交多邊形部分的內(nèi)容也加入到了原始算法，然后對兩者進(jìn)行效率對比。實驗中選取了5 000個隨機多邊形，這些多邊形的頂點數(shù)量為10到30，坐標(biāo)變化范圍為x，y∈(100，1 000)。表1是分別調(diào)用兩個算法對實驗多邊形各填充10次的時間統(tǒng)計結(jié)果。本實驗中，硬件環(huán)境為CPU Intel Pentium P6100，主頻2.0 GHz，內(nèi)存為2 GB，編譯環(huán)境為Virtual Studio 2008。

表1 算法時間效率對比ms

表1中的數(shù)據(jù)表明，改進(jìn)算法的平均填充時間、最小填充時間、最大填充時間都要明顯好于原始算法，算法改進(jìn)取得了預(yù)想的效果。

5 總結(jié)與展望

區(qū)域填充是計算機圖形學(xué)和數(shù)字圖像處理領(lǐng)域的一個基本操作，在計算機輔助設(shè)計、真實感圖形顯示、動畫、圖像處理等實際領(lǐng)域中有著廣泛的應(yīng)用。針對傳統(tǒng)活性邊表算法的不足，本文改進(jìn)了原始算法，使得算法時間效率和空間效率都有了較大提高，并且由于增加了自相交多邊形的處理，算法的適用性也得到增強?？梢灶A(yù)見，如果將本算法應(yīng)用于填充操作比較頻繁、圖形更大更為復(fù)雜的圖形處理軟件，則本算法的優(yōu)勢將得到進(jìn)一步體現(xiàn)。需要指出的是，本文算法是一種針對矢量多邊形的填充算法，若要進(jìn)行對柵格多邊形的填充，種子填充算法可能是更好的選擇。

[1]張義寬.計算機圖形學(xué)[M].西安：西安電子科技大學(xué)出版社，2006：58-64.

[2]張燕，曾立波，吳瓊水，等.一種適用于任意形狀區(qū)域的快速孔洞填充算法[J].計算機應(yīng)用研究，2004（12）：155-156.

[3]劉萬春，劉建君，朱玉文，等.一種實時高速的八連通區(qū)域填充算法[J].計算機應(yīng)用研究，2006（6）：177-179.

[4]張正峰，馬少飛，李緯.新的種子點區(qū)域填充算法[J].計算機工程與應(yīng)用，2009，45（6）：201-202.

[5]廖宗斌.區(qū)域填充及實時動畫生成的研究及應(yīng)用[D].遼寧大連：大連理工大學(xué)，2008：5-45.

[6]Pavlidis T.Algorithms for graphics and image processing[M]. Berlin：Computer Science Press，1982：65-73.

[7]張榮國，劉焜.新區(qū)入棧的區(qū)域填充掃描線算法[J].計算機工程，2006，32（5）：63-64.

[8]宋懷波，路長厚，王富春.一種新的復(fù)雜區(qū)域孔洞填充算法[J].桂林科技大學(xué)學(xué)報，2006，26（6）：451-454.

[9]降愛蓮，謝克明.壓入新_舊區(qū)段的區(qū)域填充掃描線算法[J].計算機工程與應(yīng)用，2006，42（17）：43-45.

[10]郭文平，龍幫強.掃描線種子填充算法的改進(jìn)[J].天津工業(yè)大學(xué)學(xué)報，2008，27（2）：48-51.

[11]馬輝，陸國棟，譚建榮，等.基于頂點與鄰邊相關(guān)性的多邊形填充算法[J].中國圖象圖形學(xué)報，2004，11（9）：1337-1341.

[12]唐永勇，馮劍，杜振華，等.基于頂點的多邊形掃描轉(zhuǎn)換[J].計算機與現(xiàn)代化，2011（1）：117-120.

XU Shengpan1，2,LIU Zhengjun2,ZUO Zhiquan2,CHENG Yaodong1

1.Faculty of Geomatics,Lanzhou Jiaotong University,Lanzhou 730071,China
2.Chinese Academy of Surveying&Mapping,Beijing 100830,China

To improve the efficiency of area filling, the paper makes an introduction and analysis for the three common area filling algorithms and further improves the active-edge-table algorithm which has more obvious advantages compared with the others. For the deficiency of traditional algorithm, the improved algorithm makes full use of vertex information and establishes the dynamic discovery mechanism of active edges, making the time efficiency and space efficiency both improved; meanwhile, in order to fill the self-intersected polygons, an easy and effective method to detect self-intersectedvertices based on scan line is proposed, making the adaptability of the algorithm enhanced. Experimental results demonstrate that the improved algorithm achieves very good results.

area-filling;active-edge-table;dynamic discovery mechanism;self-intersection

XU Shengpan,LIU Zhengjun,ZUO Zhiquan,et al.Im p roved active-edge-table area filling algorithm.Computer Engineering and Applications,2014,50（17）：178-181.

A

TP391

10.3778/j.issn.1002-8331.1210-0172

徐勝攀（1987—），男，碩士研究生，主要研究方向為三維可視化、激光雷達(dá)數(shù)據(jù)處理等；劉正軍（1974—），男，博士，教授，研究員，主要研究方向為遙感影像信息提取與生態(tài)環(huán)境監(jiān)測、突發(fā)事件應(yīng)急地理信息技術(shù)等；左志權(quán)（1983—），男，博士，主要研究方向為攝影測量與遙感、模式識別、LiDAR信息提取等；程耀東（1963—），男，教授，主要研究方向為計算機輔助設(shè)計（CAD）、地理信息系統(tǒng)等。E-mail：jack_1227x@163.com

2012-10-18

2013-01-15

1002-8331（2014）17-0178-04

CNKI網(wǎng)絡(luò)優(yōu)先出版：2013-01-22,http://www.cnki.net/kcms/detail/11.2127.TP.20130122.1437.002.htm l