計算機圖形學——區域填充算法(基本光柵圖形算法)

一、區域填充概念

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

區域填充:將區域內的一點(常稱【種子點】)賦予給定顏色,然后將這種顏色擴展到整個區域內的過程。

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

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(x<w&&x>0&&y<h&&y>0)
    {
        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的當前掃描線向左右兩個方向逐個像素用新的顏色值進行填充,直到邊界為止即象素顏色等于邊界色。設區間兩邊界的橫坐標分別為xleftxright
步驟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)選擇某種顏色和圖案

這些填充選擇可以應用于多邊形區域或用曲線邊界定義的區域;此外,區域可用多種畫筆、顏色和透明度參數來繪制

 

posted @ 2019-10-05 20:50 王陸 閱讀(...) 評論(...) 編輯 收藏
福彩快三怎么样