区域填充算法
#include "Conio.h"
#include "graphics.h" /*for initgr()*/
#include "stdio.h" /*for NULL */
#define closegr closegraph
void initgr(void) /* BGI初始化 */
{
int gd = DETECT, gm = 0; /* 和gd = VGA,gm = VGAHI是同样效果 */
registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */
initgraph(&gd, &gm, "");
}
enum BOOL{FALSE = 0, TRUE = 1};
typedef struct{
int y;
int xLeft;
int xRight;
}Span;/*区段*/
typedef struct stacknode
{
Span span;
struct stacknode *next;
}stacknode;
typedef struct
{
stacknode *top;
}linkstack;
/*-----------------进栈操作----------------------------------------*/
void PushStack(linkstack *s, Span *span)
{
stacknode *p=(stacknode*)malloc(sizeof(stacknode));
p->span.y = span->y;
p->span.xLeft = span->xLeft;
p->span.xRight = span->xRight;
p->next=s->top;
s->top=p;
}
/*-----------------出栈操作------------------------------------------*/
void PopStack(linkstack *s,Span *span)
{
int x;
stacknode *p=s->top;
span->y = p->span.y;
span->xLeft = p->span.xLeft;
span->xRight = p->span.xRight;
s->top=p->next;
free(p);
}
/*-----------------将栈清空------------------------------------------*/
void SetStackEmpty(linkstack *s)
{
stacknode *p=s->top;
while( s->top != NULL)
{
free(p);
s->top=p->next;
}
}
/*--------------判断栈是否为空----------------------------------------*/
int IsStackEmpty(linkstack *s)
{
if(s->top == NULL)
return 1;
else
return 0;
}
/*----------------核心程序开始----------------------------------------*/
void ScanLineFill4(int x,int y,int oldColor,int newColor)
{
int xLeft,xRight;
int i;
enum BOOL isLeftEndSet, spanNeedFill;
Span span;
linkstack *s=(linkstack*)malloc(sizeof(linkstack));
s->top = NULL;
/*填充并确定种子点(x,y)所在的区段*/
i = x;
while(getpixel(i,y) == oldColor)/*向右填充*/
{
putpixel(i,y,newColor);
i++;
}
span.xRight = i - 1; /*确定区段右边界*/
i = x - 1;
while(getpixel(i,y) == oldColor)/*向左填充*/
{
putpixel(i,y,newColor);
i--;
}
span.xLeft = i + 1; /*确定区段左边界*/
/*初始化*/
SetStackEmpty(s);
span.y = y;
PushStack(s,&span);/*将前面生成的区段压入堆栈*/
while( ! IsStackEmpty(s) )/*终止判断*/
{
/*出栈*/
PopStack(s, &span);
/*处理上面扫描线*/
y = span.y + 1;
xRight = span.xRight;
i = span.xLeft - 1;
isLeftEndSet = FALSE;
while(getpixel(i,y) == oldColor)/*向左填充*/
{
putpixel(i, y, newColor);
i--;
}
if( i != span.xLeft - 1)/*确定区段左边界*/
{
isLeftEndSet = TRUE;
xLeft = i + 1;
}
i = span.xLeft;
while( i
{
spanNeedFill = FALSE;
while(getpixel(i,y) == oldColor) /*向右填充*/
{
if( ! spanNeedFill)
{
spanNeedFill = TRUE;
if( ! isLeftEndSet)
{
isLeftEndSet = TRUE;
xLeft = i;
}
}
putpixel(i,y,newColor);
i++;
}
if( spanNeedFill )
{
span.y = y;
span.xLeft = xLeft;
span.xRight = i - 1;
PushStack(s, &span); /*将区段压入堆栈*/
isLeftEndSet = FALSE;
spanNeedFill = FALSE;
}
/* while(getpixel(i,y) != oldColor) */
i++;
}/*end of while( i
/*处理下面一条扫描线,与处理上面一条扫描线完全类似*/
y = y - 2;
xRight = span.xRight;
i = span.xLeft - 1;
isLeftEndSet = FALSE;
while(getpixel(i,y) == oldColor)/*向左填充*/
{
putpixel(i, y, newColor);
i--;
}
if( i != span.xLeft - 1)/*确定区段左边界*/
{
isLeftEndSet = TRUE;
xLeft = i + 1;
}
i = span.xLeft;
while( i
{
spanNeedFill = FALSE;
while(getpixel(i,y) == oldColor) /*向右填充*/
{
if( ! spanNeedFill)
{
spanNeedFill = TRUE;
if( ! isLeftEndSet)
{
isLeftEndSet = TRUE;
xLeft = i;
}
}
putpixel(i,y,newColor);
i++;
}
if( spanNeedFill )
{
span.y = y;
span.xLeft = xLeft;
span.xRight = i - 1;
PushStack(s, &span); /*将区段压入堆栈*/
isLeftEndSet = FALSE;
spanNeedFill = FALSE;
}
/* while(getpixel(i,y) != oldColor) */
i++;
}/*end of while( i
delay(2000); /*延时*/
}/*end of while( ! isStackEmpty() ) */
}/*end of ScanLineFill4() */
/*---------------------main()------------------------------------------*/
int main()
{
initgr(); /* BGI初始化 */
setbkcolor(3);
setcolor(5);
moveto(50, 50); /*绘制4连通区域*/
lineto(400, 50);
lineto(400,300);
lineto(150,300);
lineto(150,400);
lineto(50, 400);
lineto(50, 50);
ScanLineFill4(150,150,0,14); /*相与后oldColor == 0*
/
getch(); /* 暂停一下,看看前面绘图代码的运行结果 */
closegr(); /* 恢复TEXT屏幕模式 */
return 0;
}