填充算法

(2) 栈非空时重复执行如下两步操作： 栈顶象素出栈；并将出栈象素置成填充色。 按左上右下顺序检查与出栈象素相邻的四个象素（4-邻接点），若其中某个象素不在边界且未置成填充色，则把该象素入栈。

区域填充的扫描线算法:

区域填充的递归算法原理和程序都很简单，但由于多次递归，费时、费内存，效率不高。为了减少递归次数，提高效率可以采用扫描线算法。算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。

区域填充的扫描线算法可由下列四个步骤实现：

(1)初始化：堆栈置空。将种子点(x,y)入栈。

(2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。

(3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。

(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。

区域填充的扫描线算法：

typedef struct{ //记录种子点

intx;

int y；

} Seed;

void ScanLineFill4(int x,int y,COLORREF oldcolor,COLORREF newcolor)

{ int xl,xr,i;

bool spanNeedFill;

Seed pt;

setstackempty();

pt.x =x; pt.y=y;

stackpush(pt); //将前面生成的区段压入堆栈

while(!isstackempty())

{ pt = stackpop();

y=pt.y;

x=pt.x;

while(getpixel(x,y)==oldcolor) //向右填充

{ drawpixel(x,y,newcolor);

x++; }

xr = x-1;

x = pt.x-1;

while(getpixel(x,y)==oldcolor) //向左填充

{ drawpixel(x,y,newcolor);

x--; }

xl = x+1;

//处理上面一条扫描线

x = xl;

y = y+1;

while(x{ spanNeedFill=FALSE;

while(getpixel(x,y)==oldcolor)

{ spanNeedFill=TRUE;

x++;

}

if(spanNeedFill)

{ pt.x=x-1;pt.y=y;

stackpush(pt);

spanNeedFill=FALSE;

}

while(getpixel(x,y)!=oldcolor && x}//End of while(i//处理下面一条扫描线，代码与处理上面一条扫描线类似

x = xl;

y = y-2;

while(x{ ....

}//End of while(i}//End of while(!isstackempty()) }