一種改進的活性邊表區域填充算法

徐勝攀，劉正軍，左志權，程耀東

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

2.中國測繪科學研究院，北京 100830

一種改進的活性邊表區域填充算法

徐勝攀1，2，劉正軍2，左志權2，程耀東1

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

2.中國測繪科學研究院，北京 100830

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

區域填充；活性邊表；動態發現機制；自相交

1 引言

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

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

活性邊表算法也叫有效邊表算法[1]，它是一種基于掃描線的算法，算法充分利用了掃描線的連貫性和多邊形邊的連貫性。基本思想是用一條水平掃描線自下而上對多邊形進行掃描，對每一個Y值處的掃描線求出屬于多邊形內部的區段，對這些內部區段進行填充。這種算法基本著眼點是邊，可以對多邊形實現較為快速的全自動填充。

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

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

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

2 傳統的活性邊表算法

傳統的活性邊表算法是一種基于掃描線的算法[1]。在填充之前，需要先對多邊形進行預處理，建立初始的、關于每一條掃描線的活性邊列表。活性邊列表用一個鄰接表存儲，鄰接表的每一行關聯一條掃描線，行中的每一個結點對應一條活性邊。每一個活性邊結點至少存放以下三個數據：

x：掃描線與該邊交點的x坐標。

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

Ymax：邊的最大y值。

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

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

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

圖1 一個多邊形及其對應的活性邊表

3 活性邊表算法改進算法

3.1 改進的活性邊表算法基本思想

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

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

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

與原始算法相比，這是一種動態發現活性邊的機制。算法經過這樣改進之后，取得了以下幾點顯著效果：

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

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

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

3.2 正確填充自相交多邊形

原始算法并不針對自相交多邊形，對這部分內容，文獻中也很少有介紹。基于此，本文提出一種簡單有效的多邊形自相交點探測方法，以實現對自相交多邊形的正確填充。

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

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

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

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

3.3 算法的其他關鍵過程

（1）活性邊的發現與刪除

原始的活性邊表算法基于預先建立的鄰接表來發現活性邊。改進算法是先建立一個存放多邊形頂點編號的數組，依據頂點編號的連續性在掃描過程中動態發現活性邊。

（2）掃描線與活性邊交點坐標的計算

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

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

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

3.4 算法描述

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

1.定義數組ptID[N]，用于存儲多邊形的N個頂點的序號，并將ptID[]內的各元素按頂點的Y坐標升序排列

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

3.for：i=0 to N-1

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

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

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

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

3.3.2 Y++

4.算法結束

4 實驗與分析

為檢驗本文算法，設計了兩組實驗。

圖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構成了多次自相交；圖（d）中，BC、DE、FG三條邊相交于一點。

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

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

表1 算法時間效率對比ms

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

5 總結與展望

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

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

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

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

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

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

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

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

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

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

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

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

[12]唐永勇，馮劍，杜振華，等.基于頂點的多邊形掃描轉換[J].計算機與現代化，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—），男，碩士研究生，主要研究方向為三維可視化、激光雷達數據處理等；劉正軍（1974—），男，博士，教授，研究員，主要研究方向為遙感影像信息提取與生態環境監測、突發事件應急地理信息技術等；左志權（1983—），男，博士，主要研究方向為攝影測量與遙感、模式識別、LiDAR信息提取等；程耀東（1963—），男，教授，主要研究方向為計算機輔助設計（CAD）、地理信息系統等。E-mail：jack_1227x@163.com

2012-10-18

2013-01-15

1002-8331（2014）17-0178-04

CNKI網絡優先出版：2013-01-22,http://www.cnki.net/kcms/detail/11.2127.TP.20130122.1437.002.htm l