合并填充算法

① 区域填充的主要思想和方法

扫描线种子填充算法思想
首先填充种子所在的尚未填充的一区段,然后确定与这一区段相邻的上下两条扫描线上位于该区段内是否存在需要填充的新区段,如果存在,则依次把每个新区段最右端的象素作为种子放入堆栈。反复这个过程,直到堆栈为空。
扫描线种子填充算法步骤 1、初始化堆栈。 2、种子压入堆栈。 3、While（堆栈非空）从堆栈弹出种子象素。
(1)如果种子象素尚未填充,则： ① 求出种子区段：xleft、xright。
② 填充整个区段。 (2)检查相邻的上扫描线的xleft≤x≤xright区间内,是否存在需要填充的新区段,如果存在,则把每个新区段在xleft≤x≤xright范围内的最右边的象素,作为新的种子象素依次压入堆栈。 (3)检查相邻的下扫描线的xleft≤x≤xright区间内,是否存在需要填充的新区段,如果存在,则把每个新区段在xleft≤x≤xright范围内的最右边的象素,作为新的种子象素依次压入堆栈。 }
有关堆栈操作的辅助代码
1、定义栈结构： # define MAX 100 /*定义最大栈空间*/
struct stack
{
int top; /*指向栈顶的计数器*/
int xy[MAX][2]; /*种子点（二维）*/
}s; 2、初始化堆栈 s.top=－1; 3、进栈操作 pushxy(int x,int y)
{
if(s.top= =MAX－1)
{
printf(“Overflow!”);
exit(1);
}
else
{
s.top=s.top+1;
s.xy[s.top][0]=x;
s.xy[s.top][1]=y;
}
} 4、出栈操作 popxy(int *x,int *y)
{
if(s.top<0)
{
printf(“underflow!”);
exit(1);
}
else
{
*x=s.xy[s.top][0];
*y=s.xy[s.top][1];
s.top=s.top－1;
}
} 5、堆栈非空 s.top!=－1 或者 s.top>=0 扫描线种子填充算法伪代码 scanline_seed_fill(int x,int y,int boundarycolor,int newcolor)
{
int savex,xleft,xright,pflag,xenter;
//初始化堆栈；
pushxy(x,y); /*种子压入堆栈*/
while(堆栈非空)
{
popxy(&x,&y); /*栈顶象素出栈*/
savex=x; /*保存种子坐标x分量的值*/
while(getpixel(x,y)!=boundarycolor) /*获取该点的颜色值*/
{
putpixel(x,y, newcolor ); /*填充种子右侧的象素*/
x++;
}
xright=x－1; /*得到种子区段的右端点*/
x=savex－1; /*准备向种子左侧填充*/
while(getpixel(x,y)!=boundarycolor) /*获取该点的颜色值*/
{
putpixel(x,y, newcolor ); /*填充种子左侧的象素*/
x--;
}
xleft=x+1; /*得到种子区段的左端点*/
x=xleft;
y=y+1; /*考虑种子相邻的上扫描线*/
while(x<=xright)
{
pflag=0; /*找到新种子的标志：0为假；1为真*/
while(getpixel(x,y)!=boundarycolor && getpixel(x,y)!=newcolor&& x<xright)
{
if(pflag= =0)
pflag=1;
x++;
}
if(pflag= =1)
{
if((x= =xright)&&(getpixel(x,y)!=boundarycolor)&&(getpixel(x,y)!=newcolor))
pushxy(x,y); /*新区间超过xright,将代表该区段的象素进栈*/
else
pushxy(x－1,y); /*新区段右端点作为种子进栈*/
pflag=0;
}
xenter=x;
while((getpixel(x,y)==boundarycolor||getpixel(x,y)==newcolor)&&x<xright)
{
x++;/*向右跳过分隔带*/
}
if(xenter==x) x++;/*处理特殊情况,以退出while(x<=xright)循环*/
}
x=xleft; /*为下扫描线的处理作准备*/
y=y－2;
/*检查相邻的下扫描线,找新区段,并将每个新区段右端的象素作为种子
入栈,其方法与上扫描线的处理一样,这里省略。要求同学补充完整。*/
}
} 边相关多边形扫描线填充思想
边相关扫描线填充算法的实现需要建立两个表：边表（ET）和活动边表（AET）。
ET用来对除水平边外的所有边进行登记,即建立边的记录。
AET则是在ET建立的基础上进行扫描转换。对不同的扫描线,与之相交的边线也是不同的,当对某一条扫描线进行扫描转换时,我们只需要考虑与它相交的那些边线,为此AET建立了只与当前扫描线相交的边记录链表,以提供对当前扫描线上的区段进行填充。
边相关多边形扫描线填充算法步骤
1、根据给出的顶点坐标建ET表；并求出顶点坐标中最大y值ymax和最小y值ymin。
2、定义AET指针,并使它为空。
3、使用扫描线的yj值作为循环变量,使其初值为ymin。
4、对于循环变量yj的每一整数值,重复作以下事情,直到yj大于ymax,或ET与AET表都为空为止：
① 如果ET中yj桶非空,则将yj桶中的全部记录合并到AET中。
② 对AET链中的记录按x的大小从小到大排序。
③ 依次取出AET各记录中的xi坐标值,两两配对,对每对xi之间的象素填上所要求的颜色。
④ 如果AET中某记录的ymax=yj,则删除该记录。
⑤ 对于仍留在AET中的每个记录,用xi+1/m代替xi,这就是该记录边线与下一条扫描线yj+1的交点。
⑥ 使yj加1,以便进入下一轮循环。
边相关多边形扫描线填充为伪代码 #include <stdlib.h>
#include <graphics.h>
#include <stdio.h>
#define round(x) ((x>0)?(int)(x+0.5):(int)(x-0.5)) /*求舍入的宏*/
struct edge{ /*边记录结构*/
int ymax;
float xi;
float m;
struct edge *next;
};
void poly_fill(int,int *,int);
void main()
{
int polypoints[]={ /*多边形顶点坐标: x0,y0,x1,y1,... */
100,300, 200,200, 300,200, 300,350,
400,250, 450,300, 300,50, 100,150};
int gdriver=DETECT,gmode;
initgraph(&gdriver,&gmode,);
poly_fill(8,polypoints,4); /*用红色填充*/
getch();
closegraph();
}
/*将一条边记录插入边记录构成的链表的表头*/
void insert_et(struct edge *anedge,struct edge **p_edges)
{
struct edge *p;
p=*p_edges;
*p_edges=anedge;
anedge->next=p;
}
/*复制一条边记录插入有效边表,维持有效边表的有序性*/
short insert_aet(struct edge *p,struct edge **p_aet)
{
struct edge *q,*k,*l;
if(!(q=(struct edge *)malloc(sizeof(struct edge))))
{
printf( OUT MEMORY IN INSERTING EDGE RECORD TO AET );
return(0);
}
q->ymax=p->ymax; q->xi=p->xi;
q->m=p->m; q->next=NULL;
if(!(*p_aet)||((*p_aet)->xi>q->xi)||(((*p_aet)->xi==q->xi)&&((*p_aet)->m>q->m)))
{
l=*p_aet; *p_aet=q; q->next=l;
}
else
{
l=*p_aet;
k=l->next;
while(k&&(k->xi<q->xi))
{
l=k;
k=k->next;
}
if(k&&(k->xi==q->xi)&&(k->m<q->m))
{
l=k;
k=k->next;
}
l->next=q;
q->next=k;
}
return(1);
}
/*从（x1,y）到（x2,y）用color色绘水平直线*/
void draw_line(int x1,int x2,int y,int color)
{
int i;
y=getmaxy()-y; /*进行坐标变换*/
for(i=x1;i<=x2;i++)putpixel(i,y,color);
}
/*多边形扫描线填充:
numpoint是多边形顶点个数；
points存放多边形顶点坐标（x0,y0,x1,y1,...);
color是填充色*/
void poly_fill(int numpoint,int *points,int color)
{
struct edge **et=NULL,*aet,*anedge,*p,*q;
int i,j,maxy,miny,x1,y1,x2,y2,yi,znum;
maxy=miny=points[1];
znum=2*numpoint;
for(i=3;i<znum;i++)
{
if(maxy<points[i]) maxy=points[i];
else if(miny>points[i])miny=points[i];
i++;
}
if(!(et=(struct edge **)malloc((maxy-miny+1)*sizeof(struct edge *))))
{ /*建立边表ET */
printf( OUT MEMORY IN CONSTRUCTING ET );
return;
}
for(i=0;i<maxy-miny+1;i++) et[i]=NULL;
x1=points[znum-2]; y1=points[znum-1];
for(i=0;i<znum;i+=2)
{ /*处理多边形所有边,为每条非水平边建立一个边记录,并将其插到ET表中的合适位置 */
x2=points[i]; y2=points[i+1];
if(y1!=y2) /*只考虑非水平边*/
{
if(!(anedge=(struct edge *)malloc(sizeof(struct edge))))
{
printf( OUT MEMORY IN CONSTRUCTING EDGE RECORD. );
goto quit;
}
anedge->m=(float)(x2-x1)/(y2-y1);
anedge->next=NULL;
if(y2>y1) /*处理奇异点*/
{
j=i+1;
do{ /*向后划过所有水平边*/
if((j+=2)>=znum)j-=znum;
}while(points[j]==y2);
if(points[j]>y2) anedge->ymax=y2-1;
/*若(x2,y2)不是局部极值点,边记录的ymax域为y2-1,这样处理
扫描线y=y2时此边记录将不在AET中,从而不会产生交点 */
else anedge->ymax=y2; /*若(x2,y2)是局部极值点,边记录的ymax域为y2,
这样处理扫描线y=y2时此边记录将在AET中,从而会产生一个交点 */
anedge->xi=x1;
insert_et(anedge,&et[y1-miny]);
}
else
{
j=i+1; /*向前划过所有水平边*/
do{
if((j-=2)<0)j+=znum;
}while(points[j]==y1);
if(points[j]>y1) anedge->ymax=y1-1;
/*若(x1,y1)不是局部极值点,边记录的ymax域为y1-1,这样处理
扫描线y=y1时此边记录将不在AET中,从而不会产生交点 */
else anedge->ymax=y1; /*若(x1,y1)是局部极值点,边记录的ymax
域为y1,这样处理扫描线y=y1时此边记
录将在AET中,从而会产生一个交点 */
anedge->xi=x2;
insert_et(anedge,&et[y2-miny]);
}
}
x1=x2;
y1=y2;
}
aet=NULL; /*初始化有效边表AET*/
for(yi=miny;yi<=maxy;yi++) /*从低到高逐条处理扫描线*/
{ /*将ET表中与yi对应的边记录链表中的全部边记录
p=et[yi-miny]; 都按序并入AET中*/
while(p)
{
if(!insert_aet(p,&aet)) goto quit;
p=p->next;
}
p=aet;
while(p) /*依次取出AET各记录中的xi坐标值,两两配对,*/
{/*对每对xi之间的象素填上所要求的颜色*/
draw_line(round(p->xi),round(p->next->xi),yi,color);
p=p->next->next;
}
p=aet;
while(p&&(p->ymax==yi)) /*对AET中的每个记录,若它的ymax==yi, */
{/*则删除该记录,否则用xi+1/m代替xi,这就是该记录所对应的*/
aet=p->next; /*边线与下一条扫描线y=yi+1的交点 */
free(p);
p=aet;
}
while(p)
{
if(p->ymax==yi)
{
q->next=p->next;
free(p);
p=q->next;
}
else
{
p->xi+=p->m;
q=p;
p=p->next;
}
}
}
quit:
if(et) /*释放动态申请的内存*/
{
for(yi=miny;yi<=maxy;yi++)
{
q=p=et[yi-miny];
while(p)
{
q=p->next;
free(p);
p=q;
}
}
free(et);
}
} 边标志填充算法思想
扫描线具有连贯性,这种连贯性只有在扫描线与多边形相交处才会发生变化,而每次的变化结果：无非是在前景色和背景色之间相互“切换”。
边标志填充算法正是基于这一发现,先在屏幕上生成多边形轮廓线,然后逐条扫描线处理。处理中：逐点读取象素值,若为边界色,则对该象素值进行颜色切换。
边标志填充算法步骤 1、用边界色画出多边形轮廓线,也就是将多边形边界所经过的象素打上边标志。
2、为了缩小范围,加快填充速度,须找出多边形的最小包围盒：xmin、ymin、xmax、ymax。
3、逐条扫描线进行处理,初始时标志为假,对每条扫描线依从左往右的顺序,逐个访问该扫描线上的象素。每遇到边界象素,标志取反。然后,按照标志是否为真决定象素是否为填充色。
边标志填充算法伪代码 EdgeMarkFill(int p[][2],int n,int boundarycolor,int newcolor)
{
int i,x,y,flag,xmin,xmax,ymin,ymax;
setcolor(boundarycolor); /*设置画笔色*/
for(i=0 ;i<n;i++)/*画出多边形的n条边*/
line(p[i][0], p[i][1], p[(i+1)%n][0], p[(i+1)%n][1]);
/*用求极值的算法,从多边形顶点数组p中,求出xmin,xmax,ymin,ymax*/
for(y=ymin;y<=ymax;y++)
{
flag=－1;
for(x=xmin;x<=xmax;x++)
{
if(getpixel(x,y)= = boundarycolor) flag=－flag;
if(flag= =1)putpixel(x,y, newcolor);
}
}
}