/***************************************************************
本程序实现区域填充功能，首先输入多边形顶点的个数,回车，
然后依次输入各顶点的坐标格式如下：100,123回车
一定要在中间用逗号隔开噢，输完最后一个点后，屏幕上会依次
画出各条边，最后填充满.
程序还不完善，比如颜色值应该用变量表示以易于修改，画多边形和求种子点
应该做成独立的函数等等，以后再做上吧，这是细节的问题
作者：曹欣
学号：2003378314
班级：计应0301
******************************************************************/
#include <graphics.h>
#include <stdio.h>
#include <alloc.h>
#include <dos.h>
#include <conio.h>
//creat a stack
struct stack_node
{
int x;
int y;
struct stack_node *next;
};
typedef stack_node stack_list;
typedef stack_list *link;
link stack = 0;
//push an element
void push(int xx,int yy)
{
link new_node;
new_node=(stack_list *)malloc(sizeof(stack_list));
new_node->x=xx;
new_node->y=yy;
new_node->next=stack;
stack=new_node;
}
//pop an element
void pop(int &xx,int &yy)
{
link top;
top=stack;
xx=stack->x;
yy=stack->y;
stack=stack->next;
free(top);
}
//fill the plot
void fill(int x,int y)
{
int x0,y0,xl,xr,xlold,xrold;/*x0,y0用来标记x,y的值,xl记录x的最左值,xr记录x的最右值*/
int go=0,go2=0;
int i=0;
push(x,y);//种子像素入栈
while(stack!=0)//如果栈不空则循环，stack==0表示栈空
{
go=0;//go 只是一个标记
pop(x,y);
putpixel(x,y,4);
x0=x+1;
while(getpixel(x0,y)!=4)//fill right 填充右边
{
putpixel(x0,y,4);
x0=x0+1;
}
xr=x0-1;//记录最右值
xrold=xr;//再记录一次最右值，以备后用
x0=x-1;
while(getpixel(x0,y)!=4)//fill right 填充左边
{
putpixel(x0,y,4);
x0=x0-1;
}
xl=x0+1;//记录最左值
xlold=xl;//再记录一次最左值，以备后用
y0=y+1;//go up 向上移一条扫描线
go2=0;//go2 也只是一个用来标记的变量
while(xr>xl&&go==0)//查找上一条线的最右值,并记录为xr
{
if(getpixel(xr,y0)==4)
{
xr=xr-1;
}
else
{
go=1;//若go=1这句执行的话就说明找到了最右值，并在while中的go==0中判断并退出while
}
}
while(xl<xr&&go2==0)//查找上一条线的最左值，并记录为xl
{
if(getpixel(xl,y0)==4)
xl=xl+1;
else
go2=1;//go2=1这句执行就说明找到了最左值，并在此while中的go2==0中退出while
}
if(go==1&&go2==1)//如果找到了最左值各最右值，则执行下面的语句
{
push(xr,y0);//先将上一条线上的最右点作为种子点入栈
for(i=xl;i<xr;i++)//从最左到最右循环，在每个连续区间上找一个种子点入栈
{
if(getpixel(i,y0)!=4)//如果不是边界点，什么也不做
{
}
else if(getpixel(i-1,y0)!=4)//如果是边界点，则看它左边的点是不是边界点，如果不是，则入栈
{
push(i-1,y0);
}
}
}
y0=y-1;//go down;//向下移一条扫描线
go=0;
go2=0;
xl=xlold;//还原最左，最右
xr=xrold;
while(xr>xl&&go==0)//找下一条线的最右
{
if(getpixel(xr,y0)!=4)
{
go=1;
}
else
{
xr--;
}
}
while(xl<xr&&go2==0)//找下一条线的最左
{
if(getpixel(xl,y0)!=4)
go2=1;
else
xl++;
}
if(go==1&&go2==1)//如果找到最左和最右，则执行
{
//push(xl,y0);
push(xr,y0);
for(i=xl;i<=xr;i++)
{
if(getpixel(i,y0)!=4)
{
}
else if(getpixel(i-1,y0)!=4)
{
push(i-1,y0);
}
}
}
}
}
void main()
{
void fill(int x,int y);
int gdriver,gmode;/*显示模式*/
int i,j;
int n,px,py,px0,py0,px1,py1;
int ya=0,yi=getmaxy();
printf("pleas input the number of the top points:");
scanf("%d",&n);
for(i=0;i<n;i++)//从键盘接受各顶点的坐标，依次入栈，并记录最大Y值和最小Y值
{
printf("please input the coordinate of the points--like:100,200 :");
scanf("%d,%d",&px,&py);
if(ya<py)
ya=py;//ya是最大Y值
if(yi>py)
yi=py;//yi是最小Y值
push(px,py);
}
detectgraph(&gdriver,&gmode);
initgraph(&gdriver,&gmode,"c:\\bc31\\bgi");
setbkcolor(0);
cleardevice();
setcolor(4);
pop(px0,py0);//输入的最后一个顶点出栈
px=px0;
py=py0;//记录最后一个顶点
//draw the plot
while(stack != 0)
{
pop(px1,py1);
line(px0,py0,px1,py1);
px0=px1;
py0=py1;
delay(500);
}
line(px0,py0,px,py);//依次画线，画出多边形
//画完多边形后，栈为空
//find the y value
j=(ya+yi)/2;//找Y的中间值,就是第一个种子点的Y值
i=0;
n=0;//记录入栈个数
//find the seed element
while(i<getmaxx()&&n!=2)//按X值从0到X最大值依次查找，并在入栈个数为2的时候退出
{
if(getpixel(i,j)==4)//如果是多边形上的点，则入栈，用n记录入栈的个数
{
push(i,j);
n=n+1;
}
i=i+1;//i是记录当前的X值
}
pop(i,j);//第二个交点出栈
pop(n,j);//第一个交点出栈，虽然覆盖了Y值，但这不重要，我们要的是X值
i=(i+n)/2;//现在i是我们要找的种子点的X值
//fill the plot
fill(i,j);//将种子点作为参数传入fill()方法
delay(1000);
outtextxy(100,410,"the red line was drawing,fill over");
getch();
closegraph();
}
