摘 要：區(qū)域填充算法廣泛應(yīng)用于各個(gè)領(lǐng)域，經(jīng)典的區(qū)域填充算法存在若干問題，在分析了兩種傳統(tǒng)區(qū)域填充算法的原理的基礎(chǔ)上，闡述了兩種改進(jìn)的區(qū)域填充算法。

關(guān)鍵詞：掃描線填充算法；種子填充算法；鏈隊(duì)列

中圖分類號(hào)：TP391.41

1 區(qū)域填充概述

區(qū)域填充指的是在輸出平面的閉合區(qū)域內(nèi)使用某種指定的顏色或圖案完整地進(jìn)行填充，通俗點(diǎn)講就是指定一個(gè)區(qū)域的邊界，用指定的顏色代碼賦予給邊界范圍內(nèi)的所有像素點(diǎn)。它是計(jì)算機(jī)圖形學(xué)的一項(xiàng)重要內(nèi)容，主要廣泛應(yīng)用于真實(shí)感圖形顯示、交互式圖形設(shè)計(jì)、計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域，至今依然是研究的熱點(diǎn)問題。

經(jīng)典的區(qū)域填充算法一般分兩大類，一類是掃描線填充；一類是種子填充。掃描線填充有一定難度，而種子填充在掌握了“?！边@一抽象數(shù)據(jù)類型的實(shí)現(xiàn)方法的前提下，比較容易完成。

2 經(jīng)典區(qū)域填充算法思想

2.1 掃描線填充算法

掃描線填充算法一般是通過(guò)確定橫跨區(qū)域的掃描線的覆蓋間隔來(lái)填充完成的算法。它主要用來(lái)填充比較簡(jiǎn)單的標(biāo)準(zhǔn)多邊形區(qū)域，例如矩形、橢圓及其他一些簡(jiǎn)單的多邊形，但是它對(duì)輪廓線的形狀有一定的要求，往往在處理復(fù)雜區(qū)域時(shí)失效。

掃描線填充算法基本原理是用水平掃描線自上而下對(duì)由點(diǎn)、線段構(gòu)成的多段多邊形進(jìn)行掃描，每根掃描線與多邊形每條邊都產(chǎn)生一系列交點(diǎn)，這些交點(diǎn)依照x坐標(biāo)進(jìn)行分類，然后成對(duì)取出分類后的交點(diǎn)，作為兩個(gè)端點(diǎn)，用所填的顏色畫水平直線，用此方法對(duì)多邊形進(jìn)行掃描，掃描完畢的同時(shí)也完成了填色。如何正確求得掃描線與區(qū)域內(nèi)外輪廓線的交點(diǎn)，將會(huì)成為算法成敗的關(guān)鍵問題，而采用合適的數(shù)據(jù)結(jié)構(gòu)可以簡(jiǎn)化操作、提高算法的效率。

經(jīng)典掃描線算法一般采用鄰接鏈表的數(shù)據(jù)結(jié)構(gòu)，每條掃描線在該表中都對(duì)應(yīng)有一項(xiàng)，利用表OET與表AET記錄掃描線與多邊形相交的情況。本算法效率雖高，但填充結(jié)果的完備性不是很好，在處理復(fù)雜區(qū)域時(shí)，通常不能準(zhǔn)確填充。

2.2 種子填充算法

種子填充算法（又稱邊界填充算法）是從給定的位置開始填充直到指定的邊界為止的填充算法，使用該算法可以解決邊界比較復(fù)雜的多邊形區(qū)域填充問題。使用本算法需要首先確定一個(gè)或多個(gè)區(qū)域內(nèi)部的點(diǎn)作為種子點(diǎn)，并且賦予其填充色，然后以該像素點(diǎn)為起點(diǎn)，用四向連通方法（或八向連通方法）找到區(qū)域內(nèi)的所有像素點(diǎn)并填充。

種子填充算法基本原理是：從多邊形區(qū)域內(nèi)部的一個(gè)點(diǎn)開始，用指定的顏色畫點(diǎn)，由內(nèi)向外達(dá)到圖形邊界為止。

種子填充算法通常用兩種技術(shù)進(jìn)行填充操作：四連通技術(shù)和八連通技術(shù)。四連通算法是從多邊形區(qū)域內(nèi)一個(gè)像素點(diǎn)出發(fā)，分別通過(guò)向上、向下、向左、向右四個(gè)方向到達(dá)區(qū)域內(nèi)的任意像素點(diǎn)，以此達(dá)到填充的效果；八連通算法是從多邊形區(qū)域內(nèi)一個(gè)像素點(diǎn)出發(fā)，分別通過(guò)向上、向下、向左、向右、向左上、向左下、向右上和向右下八個(gè)方向到達(dá)區(qū)域內(nèi)的任意像素點(diǎn)，以此達(dá)到填充的效果。

2.3 經(jīng)典算法弊端

掃描線算法的一個(gè)明顯問題是在處理帶水平邊的凹拐點(diǎn)時(shí)不能準(zhǔn)確填充，然后基于掃描線上像素點(diǎn)之間的連貫性，因此本算法尚具有較高的效率。

而種子填充算法采用遞歸方法，需要進(jìn)行大量的出入棧操作，因此效率較低，在填充較大的區(qū)域時(shí)，要求分配較大的堆?？臻g，這樣不僅浪費(fèi)了內(nèi)存，同時(shí)有可能出現(xiàn)堆棧溢出的現(xiàn)象。衡量區(qū)域填充算法的標(biāo)準(zhǔn)是填充結(jié)果的完備性和填充過(guò)程的高速高效性，針對(duì)以上問題在傳統(tǒng)區(qū)域填充算法的基礎(chǔ)上，很多文獻(xiàn)提出了更加正確高效的算法。

3 種子填充算法的改進(jìn)

3.1 基于掃描線種子填充算法的改進(jìn)

經(jīng)典的掃描線種子填充算法對(duì)搜索新種子點(diǎn)的操作和種子所在掃描線的填充是分別進(jìn)行的，這就需要對(duì)大量的像素點(diǎn)進(jìn)行重復(fù)判斷和讀取。為了搜索新種子像素點(diǎn)和對(duì)當(dāng)前的掃描線填充，因此需要對(duì)當(dāng)前的掃描線和與其相鄰的上、下掃描線進(jìn)行掃描，這就會(huì)造成多數(shù)掃描線被重復(fù)掃描，即便是該掃描線上的像素點(diǎn)已經(jīng)全部被填充也還是要被再次掃描，這樣就可能出現(xiàn)被掃描3次，降低了程序的效率和運(yùn)行速度。

此外，在該算法中堆棧操作頻繁，每搜到一個(gè)新的填充區(qū)間就要入棧，對(duì)每一條掃描線至少有一個(gè)區(qū)間入棧，每次開始另一條掃描線搜索都要先出棧，這不僅占用了大量的儲(chǔ)存空間，還降低了算法的效率。

對(duì)于經(jīng)典區(qū)域填充算法的欠缺，文獻(xiàn)[1]提出了一種新的區(qū)域填充掃描線算法。文獻(xiàn)[1]中所描述的算法在掃描時(shí)采用的是對(duì)于同一條掃描線上出現(xiàn)多個(gè)填充區(qū)域時(shí)，分成向上搜索和向下搜索兩種情況，每種情況又都可能出現(xiàn)多個(gè)搜索新區(qū)；在填充過(guò)程中，考慮到當(dāng)前區(qū)間上下相關(guān)性和左右連續(xù)性，只需將出現(xiàn)的新搜索區(qū)域壓入堆棧，不需要將相鄰的每根掃描線都?jí)喝攵褩＃M(jìn)而減少了像素點(diǎn)的重復(fù)判斷與讀取，同時(shí)也較少了回溯區(qū)的搜索時(shí)間，以此來(lái)避免不必要的進(jìn)出棧處理，提高填充效率。

3.2 基于鏈隊(duì)列的種子填充法

文獻(xiàn)[2]針對(duì)遞歸種子算法的提出了改進(jìn)算法，在該算法中使用鏈隊(duì)列而不是遞歸，而且采用了先填充后入隊(duì)列，減少了很多不必要的操作，使得改進(jìn)后的算法效率都大大優(yōu)于遞歸種子填充算法，無(wú)論是在時(shí)間上還是空間上，而且也可以填充任意大小、任意復(fù)雜邊界的區(qū)域。

經(jīng)典的遞歸種子填充算法，采用的是先入棧，然后出棧，再填充，也就是可以理解為當(dāng)填充某一個(gè)像素點(diǎn)時(shí)，無(wú)論它的四連通點(diǎn)是否已被填充，都是要進(jìn)入堆棧，因此會(huì)導(dǎo)致很多的冗余像素點(diǎn)進(jìn)入堆棧；改進(jìn)后的種子填充算法使用鏈隊(duì)列種子填充算法，首先進(jìn)行填充，然后再進(jìn)入鏈隊(duì)列，在入隊(duì)列之前需要判斷像素點(diǎn)是否已被填充，如果已經(jīng)被填充，并剛進(jìn)入隊(duì)列，則不予考慮，這樣將會(huì)減少進(jìn)入隊(duì)列的冗余像素點(diǎn)，也就是每一個(gè)像素點(diǎn)只入隊(duì)列一次。

上述改進(jìn)的算法避免了經(jīng)典遞歸種子填充算法因?yàn)橐粋€(gè)像素點(diǎn)重復(fù)進(jìn)入堆棧操作，而導(dǎo)致速度過(guò)慢的問題。但經(jīng)過(guò)研究發(fā)現(xiàn)修改后的算法，仍存在很多冗余的檢測(cè)。繼而提出新的修改思路：分別設(shè)置4個(gè)鏈隊(duì)列用來(lái)記錄上、下、左、右4個(gè)方向的填充新種子像素點(diǎn)，如果此時(shí)正在出隊(duì)的像素點(diǎn)來(lái)自于記錄向上的那個(gè)隊(duì)列，則不要檢測(cè)該像素點(diǎn)的下面那個(gè)像素點(diǎn)，這樣在填充某個(gè)像素點(diǎn)時(shí)只需要檢測(cè)它的上、左、右3個(gè)連通像素點(diǎn)就可以了。

4 結(jié)束語(yǔ)

近年來(lái)計(jì)算機(jī)圖形學(xué)技術(shù)發(fā)展迅速，并在很多行業(yè)得以應(yīng)用，區(qū)域填充算法也因此在很多領(lǐng)域得到了廣泛應(yīng)用，這使得對(duì)填充算法的研究不僅局限于完備性和效率方面，如何實(shí)現(xiàn)填充的完全自動(dòng)化將成為研究熱點(diǎn)。

參考文獻(xiàn)：

[1]張榮國(guó)，劉焜.新區(qū)入棧的區(qū)域填充掃描線算法[J].計(jì)算機(jī)工程，2006（05）：63-65.

[2]陳元琰，陳洪波.一種基于鏈隊(duì)列的種子填充法[J].廣西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2003（03）：31-33.

作者簡(jiǎn)介：石燕（1981.01-），女，河南濟(jì)源人，教師，助教，碩士，研究方向：面向?qū)ο蟆?/p>

作者單位：河南牧業(yè)經(jīng)濟(jì)學(xué)院（英才校區(qū)） 計(jì)算機(jī)系，鄭州 450000