一種改進(jìn)的多邊形區(qū)域填充算法

衛(wèi)洪春

摘要：多邊形區(qū)域填充是圖形學(xué)和數(shù)字圖像處理等領(lǐng)域的基本問題。種子填充算法雖然簡(jiǎn)單，但需要大量?？臻g來存儲(chǔ)相鄰點(diǎn)，容易發(fā)生工作棧溢出的情況，在實(shí)際填充過程中很難真正發(fā)揮作用。該文提出了一種改進(jìn)的種子填充算法，在堆中實(shí)現(xiàn)棧操作，突破了工作棧大小的限制，可處理任意大的填充區(qū)域。實(shí)驗(yàn)表明，該算法具有較高的運(yùn)算效率及實(shí)用價(jià)值，對(duì)實(shí)際應(yīng)用有較好的參考作用。

關(guān)鍵詞：遞歸；多邊形；種子填充；工作棧

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）02-0210-03

1 概述

多邊形區(qū)域填充是圖形學(xué)和數(shù)字圖像處理等領(lǐng)域中計(jì)算機(jī)應(yīng)用的一個(gè)重要方面。填充算法的優(yōu)劣直接影響圖形顯示的速度和精確性。多邊形填充一直是計(jì)算機(jī)圖形學(xué)研究的熱點(diǎn)，常用于CAD/CAM、界面設(shè)計(jì)、地理信息系統(tǒng)、廣告設(shè)計(jì)、機(jī)械制造、陰影、圖像處理等領(lǐng)域。

多邊形填充算法較多，主要有種子填充法和掃描線填充法。種子填充是從多邊形區(qū)域的一個(gè)內(nèi)點(diǎn)開始，由內(nèi)向外用給定顏色畫點(diǎn)直到邊界為止。若邊界指定了某種顏色，則種子填充算法可逐像素處理直到邊界色為止。該算法需給出圖像數(shù)據(jù)的區(qū)域及區(qū)域內(nèi)的一個(gè)點(diǎn)，該算法較適合以人機(jī)交互方式進(jìn)行的圖像填充操作。種子填充算法的優(yōu)點(diǎn)是非常簡(jiǎn)單，缺點(diǎn)是需要大量?？臻g來存儲(chǔ)相鄰點(diǎn)，且當(dāng)待填充區(qū)域較大時(shí)，容易造成棧溢出，從而中止區(qū)域填充。本文提出了一種改進(jìn)的種子填充算法，可以處理任意大的區(qū)域填充。

2 簡(jiǎn)單種子填充算法

簡(jiǎn)單種子填充算法的核心是遞歸算法。該方法理論上非常簡(jiǎn)單、準(zhǔn)確，但重復(fù)計(jì)算較多。種子填充算法有“4連通算法”和“8連通算法”，如圖1所示。

以四連通域的填充為例，四連通域從區(qū)域內(nèi)任意一點(diǎn)出發(fā)，通過上、下、左、右四個(gè)方向到達(dá)區(qū)域內(nèi)的任意像素。四向連通填充算法如下：

a） 種子像素壓入棧；

b） 若棧為空，則轉(zhuǎn)e）；否則轉(zhuǎn)c）；

c） 彈出一個(gè)像素，并將該像素置成填充色；判斷該像素相鄰的四連通像素是否為邊界色或已經(jīng)置成多邊形的填充色，若不是，則將該像素壓入棧；

d） 轉(zhuǎn)b）；

e） 結(jié)束。

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

由于簡(jiǎn)單種子填充算法存在上述缺點(diǎn)，在實(shí)際填充過程中很難真正發(fā)揮作用。因?yàn)樵诤瘮?shù)調(diào)用過程中，調(diào)用函數(shù)和被調(diào)用函數(shù)之間的鏈接和信息交換需要通過工作棧來完成，而棧是一種容納數(shù)據(jù)的容器，數(shù)據(jù)只能從棧的一端存入（壓入棧），同時(shí)只能從棧的同一端取出（彈出棧）。運(yùn)行棧是一段區(qū)域的內(nèi)存空間，運(yùn)行棧由很多棧幀構(gòu)成，每個(gè)棧幀對(duì)應(yīng)一次函數(shù)調(diào)用。棧幀的內(nèi)容包括：本次函數(shù)調(diào)用的形參值、控制信息、局部變量值及臨時(shí)數(shù)據(jù)。函數(shù)調(diào)用時(shí)，將棧幀壓入運(yùn)行棧；返回時(shí)則彈出棧幀。由此可見，當(dāng)函數(shù)進(jìn)行遞歸調(diào)用時(shí)，隨著遞歸深度的增加，被壓入的棧幀將越來越多，工作棧的可用空間越來越少，直至消耗殆盡。如圖3（a）及圖3（b）所示。

雖然開發(fā)平臺(tái)可調(diào)整運(yùn)行工作棧的大小，例如，在VC環(huán)境下，可通過打開工程，依次操作命令Project->Setting->Link，在Link選項(xiàng)卡的Category 項(xiàng)選擇Output，然后在Reserve中設(shè)定棧的值。reserve默認(rèn)值為1MB，最小值為4Byte若將棧空間設(shè)為4MB，則將reserve改為0x400000。通過以上操作即可完成工作棧大小的調(diào)整。但是調(diào)整了工作棧大小后會(huì)引來一些其他的問題，如響應(yīng)時(shí)間等。因此這不能解決根本問題?；谏鲜鲈?，本文提出了一種將簡(jiǎn)單種子填充遞歸算法改進(jìn)為通過堆棧操作的非遞歸算法。通過在堆中動(dòng)態(tài)開辟一段空間作為棧空間，則這樣的?？臻g可以相當(dāng)大，從而突破了運(yùn)行工作棧大小的限制，滿足了種子填充算法正確運(yùn)行的要求。在MFC中的測(cè)試代碼如下：

4 結(jié)語(yǔ)

簡(jiǎn)單種子填充算法需要大量棧空間來存儲(chǔ)相鄰點(diǎn)，容易造成工作棧的溢出，其實(shí)用價(jià)值不高。由于堆是很大的自由空間，從而可在堆中動(dòng)態(tài)分配所需空間來實(shí)現(xiàn)棧的操作，本文提出的改進(jìn)的種子填充算法，突破了工作棧大小的限制，可處理任意大的填充區(qū)域。實(shí)驗(yàn)表明，該算法具有較好的實(shí)用價(jià)值及較高的運(yùn)算效率，對(duì)實(shí)際應(yīng)用有較好的參考作用。

參考文獻(xiàn)：

[1] 王汝傳，黃海平，林巧民.計(jì)算機(jī)圖形學(xué)教程[M]. 2版.北京：人民郵電出版社，2009.

[2] 和青芳. 計(jì)算機(jī)圖形學(xué)原理及算法教程[M].北京：清華大學(xué)出版社，2008.

[3] 孫劍，王玉亭. C++中一種高性能動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)方法[J].現(xiàn)代計(jì)算機(jī)，2007，（4）：102-104，112.

[4] 蘇小紅，李東，唐好選，等.計(jì)算機(jī)圖形學(xué)實(shí)用教程（第3版）[M]. 北京：人民郵電出版社，2014.

[5] 嚴(yán)蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）[M]. 北京：清華大學(xué)出版社，2015.

[6]張雪彬，劉培國(guó)，曹兵.基于C++語(yǔ)言的多維動(dòng)態(tài)數(shù)組的實(shí)現(xiàn)[J]. 現(xiàn)代電子技術(shù)，2006，29（24）：68-69.