polyfill.cpp

边界填充算法,将边界填充的递归算法转化成非递归

#include <stdio.h>

#include "gl/glut.h"

struct point /*点*/

{

int x;

int y;

};

struct stack /*栈*/

{

struct point p;

struct stack *next;

};

struct stack *stack_top = NULL; /*栈顶*/


void push(struct point p) /*压栈*/

{

struct stack *new = (struct stack *)malloc(sizeof(struct stack));

new->p.x=p.x;

new->p.y=p.y;

new->next=stack_top;

stack_top=new;

}

struct point pop() /*出栈*/

{

struct point p;

struct stack *stmp;

p.x=stack_top->p.x;

p.y=stack_top->p.y;

stmp=stack_top;

stack_top=stack_top->next;

free(stmp);

return p;

}

void smx(struct point p); /*扫描线算法实现*/

void fill(int y,int l,int r); /*填充下一条扫描线，并找到种子点压栈*/


int main(int argc,char **argv) /*主函数*/

{

int driver=DETECT,mode;

int n,i;

int y_max,y_min; /*多边形各顶点最大Y值,最小Y值*/

struct point p1,p2,ptmp;


initgraph(&driver,&mode,"C:\\turboc2"); /*初始化*/

y_max=0;

y_min=getmaxy();


/*接受多边形顶点个数及顶点坐标*/

printf("Current Mode:(Max X:%d, Max Y:%d)\n",getmaxx(),getmaxy());

printf("Please Input the Number of the points:");

scanf("%d",&n); /*多边形顶点个数*/

for(i=0; i<n; i++)

{

printf("Please Input the Coordinate of the points:x y:");

scanf("%d%d",&(ptmp.x),&(ptmp.y));

y_max=y_max>ptmp.y?y_max:ptmp.y;

y_min=y_min<ptmp.y?y_min:ptmp.y;

push(ptmp); /*栈存储多边形顶点*/

}

cleardevice(); /*清屏,并设置属性*/

setbkcolor(BLACK);

setcolor(4);

/*画多边形*/

p1=pop();

ptmp.x=p1.x;

ptmp.y=p1.y;

while(stack_top!=NULL)

{

p2=pop();

line(p1.x,p1.y,p2.x,p2.y);

p1=p2;

}

line(p1.x,p1.y,ptmp.x,ptmp.y);

getch();

/*扫描线与图形的最左两个交点*/

for(i=0,n=0 ;i<getmaxx()&&n!=2 ;i++)

{

if(getpixel(i,(y_max+y_min)/2)==4)

{

ptmp.x=i;

ptmp.y=(y_max+y_min)/2;

push(ptmp); /*栈存储交点*/

n++;

}

}

/*选取种子点*/

p2=pop();

p1=pop();

ptmp.x=(p2.x+p1.x)/2;

ptmp.y=p1.y;

/*扫描线算法填充*/

smx(ptmp);

getch();

closegraph();

return 0;

}


void smx(struct point p)

{

int i,j;

int x,y,xl,xr,xlold,xrold;

int s1,s2;

struct point ptmp;

push(p); /*栈存储种子点*/

while(stack_top!=NULL)

{

delay(50000);

p=pop();

x=p.x;

y=p.y;

putpixel(x,y,4);

while(getpixel(++x,y)!=4) /*扫描线右填充*/

{

putpixel(x,y,4);

}

xrold=xr=x-1;

x=p.x;

while(getpixel(--x,y)!=4) /*扫描线左填充*/

{

putpixel(x,y,4);

}

xlold=xl=x+1;

fill(p.y+1,xl,xr);/*下一条扫描线填充，找到种子点压栈*/

fill(p.y-1,xl,xr);/*上一条扫描线填充，找到种子点压栈*/

}

}

void fill(int y,int l,int r)

{

int i,s1,s2=s1=0;

struct point ptmp;

while(l<r&&s1==0) /*向左找未填充点*/

{

if(getpixel(r,y)==4)

r--;

else

s1=1;

}

while(l<r&&s2==0) /*向右找未填充点*/

{

if(getpixel(l,y)==4)

l++;

else

s2=1;

}

if(s2==1) /*找到最右值*/

{

ptmp.x=r;

ptmp.y=y;

push(ptmp); /*最右值压栈*/

if(s1==1)

for(i=l; i<r; i++) /*从最左到最右循环，在每个连续区间上找一个种子点入栈*/

{

if(getpixel(i,y)!=4){} /*不是边界点*/

else

{

ptmp.x=i-1;

ptmp.y=y;

push(ptmp);

}

}

}

}