計算機圖形學——區域填充演算法

一、區域填充概念

區域：指已經表示成點陣形式的填充圖形，是象素的集合。

區域填充：將區域內的一點（常稱 【種子點】）賦予給定顏色，然後將這種顏色 擴充套件到整個區域內的過程。

區域填充演算法要求區域是連通的，因為只有在連通區域中，才可能將種子點的顏色擴充套件到區域內的其它點。

1、區域有兩種表示形式

1）內點表示：枚舉出區域內部的所有象素，內部所有象素著同一個顏色，邊界畫素著與內部象素不同的顏色。

2）邊界表示：枚舉出區域外部的所有象素，邊界上的所有象素著同一個顏色，內部畫素著與邊界象素不同的顏色。

2、區域連通

1）四向連通區域：從區域上一點出發可透過【上、下、左、右】四個方向移動的組合，在不越出區域的前提下，到達區域內的任意象素。

2）八向連通區域：從區域上一點出發可透過【上、下、左、右、左上、右上、左下、右下】八個方向移動的組合，在不越出區域的前提下，到達區域內的任意象素。

二、簡單種子填充演算法

基本思想

給定區域G一種子點（x， y），首先判斷該點是否是區域內的一點，如果是，則將該點填充為新的顏色，然後將該點周圍的四個點（四連通）或八個點（八連通）作為新的種子點進行同樣的處理，透過這種擴散完成對整個區域的填充。

這裡給出一個

四連通的種子填充演算法（區域填充遞迴演算法）

，使用

【棧結構】

來實現

原理演算法原理如下：種子畫素入棧，當

【棧非空】

時重複如下三步：

演算法程式碼

這裡給出八

連通的種子填充演算法

的程式碼：

void flood_fill_8（int［］ pixels， int x， int y， int old_color， int new_color）{ if（x0&&y0） { if （pixels［y*w+x］==old_color） { pixels［y*w+x］== new_color）； flood_fill_8（pixels， x，y+1，old_color，new_color）； flood_fill_8（pixels， x，y-1，old_color，new_color）； flood_fill_8（pixels， x-1，y，old_color，new_color）； flood_fill_8（pixels， x+1，y，old_color，new_color）； flood_fill_8（pixels， x+1，y+1，old_color，new_color）； flood_fill_8（pixels， x+1，y-1，old_color，new_color）； flood_fill_8（pixels， x-1，y+1，old_color，new_color）； flood_fill_8（pixels， x-1，y-1，old_color，new_color）； } }}

簡單種子填充演算法的不足

a）有些畫素會多次入棧，降低演算法效率，棧結構佔空間

b）遞迴執行，演算法簡單，但效率不高，區域內每一畫素都要進/出棧，費時費記憶體

c）改進演算法，減少遞迴次數，提高效率

三、掃描線種子填充演算法

基本思想

從

給定的種子點

開始，

填充

當前掃描線上種子點所在的一

區段

，然後確定與這一段相鄰的

上下兩條掃描線

上位於區域內的區段（需要填充的區間），從這些區間上

各取一個種子點

依次把它們存起來，

作為下次填充的種子點

。反覆進行這過程，直到所儲存的各區段都填充完畢。

演算法步驟

步驟 1：（初始化）將演算法設定的堆疊置為空。將給定的種子點（x， y）壓入堆疊

步驟 2：

（出棧）如果堆疊為空，演算法結束；否則取棧頂元素（x， y）作為種子點

步驟 3：

（區段填充）從種子點（x， y）開始，沿縱座標為y的當前掃描線

向左右兩個方向

逐個畫素用新的顏色值進行填充，直到邊界為止即象素顏色等於邊界色。設區間兩邊界的橫座標分別為

xleft

和

xright

。

步驟4：

在與當前掃描線相鄰的上下兩條掃描線上，以區間［xleft， xright］為搜尋範圍，求出需要填充的各小區間，把各小區間中最右邊的點並作為種子點壓入堆疊，轉到步驟2。

演算法的關鍵原則

1）搜尋原則：

從前一個填充的區間（邊界之間的範圍xleft， xright）作為後一條掃描線種子點尋找的範圍。

2）填充原則：

從種子點往左，右填，填到邊界

例項

上述演算法的描述過於抽象，直接看演示

演算法程式碼

Stack stack=new Stack（）；//堆疊 pixel_stack初始化Stack。push （point）； //（x，y）是給定的種子畫素while （！stack。empty（））{ p=（Point）（stack。pop（））；//出棧，從堆疊中取一畫素作種子畫素 x=p。x； y=p。y； savex=x；//儲存種子點的橫座標x的值 while （pixels ［y*w+x］！= boundary_color） { pixels ［y*w+x］= new_color； x++； } //從種子畫素開始向右填充到邊界 xright=x–1； //儲存線段的右端點 x=savex–1； //設定種子點往左填充的起點 while （pixels ［y*w+x］！= boundary_color） { pixels ［y*w+x］ = new_color； x=x–1； } //從種子畫素開始向左填充到邊界，以上兩步完成區間填充。 xleft=x+1； //儲存線段的左端點，加1是因為前面 迴圈時多減一次 x=xleft； //起點是上次的左端點 y=y+1； //開始處理上一條掃描線 while（x<=xright） //在上一條掃描線上檢查是否需要填充 { span_need_fill=false； //先設定為不需要填充 while （pixels ［y*w+x］ ==old_color&&x<=xright ） { //待填充的線段 span_need_fill=true； //發現有舊象素，需要填充 x=x+1； } //待填充的線段處理完，即遇到邊界色，！=old_color跳出 if （span_need_fill） //如果區間需要填充，則將其右端點作為種子點壓進堆疊 { p=new Point（x-1，y）； stack。push （p）； //進棧 span_need_fill=false； } //繼續向右檢查以防有遺漏 while （pixels ［y*w+x］ ！=old_color &&x<=xright ） x=x+1； } //在上一條掃描線上檢查完 x＝xleft； y=y–2； //形成下一條掃描線的y值//在下一條掃描線上從左向右檢查位於區間［xleft，xright］上的畫素，其方法與在上一條掃描線上檢查的情況完全一樣，見書。}//出棧完

四、多邊形的掃描轉換與區域填充演算法小結

上一篇部落格講述了多邊形的掃描轉換，這裡將多邊形掃描轉換和區域填充演算法進行比較總結。

基本思想不同

多邊形掃描轉換是指將多邊形的頂點表示轉化為點陣表示

區域填充只改變填充顏色，不改變區域表示方式

基本條件不同

在區域填充演算法中，要求給定區域內的一點作為種子點，然後從這一點根據連通性將新的顏色擴充套件到整個區域。

掃描轉換多邊形是從多邊形的邊界（頂點）資訊出發，利用多種形式的連貫性進行填充的。

掃描轉換區域填充的核心是知道多邊形的 邊界， 要得到多邊形內部的畫素集，有很多種辦法。其中掃描線演算法是利用一套 特殊的資料結構 ， 避免求交 ，然後一條條掃描線確定。

區域填充條件更強 一些，不但要知道邊界，而且要知道區域內的一點，可以利用四連通或八連通區域不斷向外擴充套件。

填充一個定義的區域的選擇包括：

a）選擇實區域顏色或圖案填充方式

b）選擇某種顏色和圖案

這些填充選擇可以應用於多邊形區域或用曲線邊界定義的區域；此外，區域可用多種畫筆、顏色和透明度引數來繪製