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

衛(wèi)洪春

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

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

中圖分類號：TP391 文獻標識碼：A 文章編號：1009-3044（2016）02-0210-03

1 概述

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

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

2 簡單種子填充算法

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

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

a） 種子像素壓入棧；

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

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

d） 轉(zhuǎn)b）；

e） 結(jié)束。

3 改進的種子填充算法

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

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

4 結(jié)語

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

參考文獻：

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

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

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

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

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

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