区域填充算法

区域填充算法 #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 < xRight) { 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 < xRight) */ /*处理下面一条扫描线,与处理上面一条扫描线完全类似*/ 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 < xRight) { 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 < xRight) */ 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; }