实验四区域填充算法的实现班级信计2班学号 20080502090 姓名张进分数一、实验目的和要求：1、理解区域的表示和类型，能正确区分四连通和八连通的区域2、了解区域填充的实现原理3、利用TurboC实现区域填充的递归算法二、实验内容：当给定种子点(x,y)时，首先填充种子点所在的扫描线上的位于给定区域的一个区段，然后确定与这一区段连通的上下两条扫描线上位于给定区域的区段依次保存下来。
反复这个过程，直到填充结束.三、实验结果分析1、种子填充算法假设在多边内有一像素已知，由此出发利用连通性找到区域内的所有像素2、设(x,y)为内点表示的四连通区域内的一点，oldcolor为区域的原色。
现取(x,y)为种子点，要将整个区域填充为显得颜色newcolor，递归填充过程如下：先判别像素(x,y)的颜色，若它的值不等于oldcolor，说明该像素或者位于区域之外或者已经被置于newcolor，不需要填充，算法结束，否则置该像素的颜色为newcolor，再对与其相邻上、下、左、右四个相邻像素分别作递归填充。
1、程序代码：#include "Conio.h"#include "graphics.h" /*for initgr()*/#include "stdio.h" /*for NULL */#define closegr closegraphvoid 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;elsereturn 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;}1.运行结果：。
