4.5-4.6.1.c

计算机图形学

/*递归填充算法----扫描线算法扫描多边形*/
#include "Conio.h"
#include "stdio.h"
#include "graphics.h"
#define closegr closegraph
#define LEN sizeof (struct point)

void initgr(void) /* BGI初始化 */
{int gd=DETECT,gm=0; /* 和gd=VGA,gm=VGAHI是同样效果 */
 registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */
 initgraph(&gd,&gm,"");
}
struct Edge                     /*边的结构*/
      {int ymax;
       float x,delatx;
       struct Edge *nextEdge;};
struct point            /*点的结构*/
  {int x,y;
   struct point *next; };
struct point *creat()  /*顺时针输入顶点*/
{ struct point *h,*p,*r=NULL;
  int x,y;
  printf("顺序输入顶点坐标");
  scanf("%d,%d",&x,&y);
  h=NULL;
  while (x!=0)
  { p=(struct point *)malloc(sizeof (struct point));
    p->x=x;
    p->y=y;
    if (h==NULL) h=p;
     else r->next=p;
    r=p;
    scanf("%d,%d",&x,&y);
  }
  r->next=NULL;
  return(h);
}
/*画出多边形边*/
void draw(struct point *h)
{ int sx,sy;
  struct point *q;
  setcolor(14);
  q=h;
  sx=q->x;
  sy=q->y;
  q=q->next;
  while (q!=NULL)
   {line(sx,sy,q->x,q->y);
    sx=q->x;
    sy=q->y;
    q=q->next;
   }
  q=h;
  line(sx,sy,q->x,q->y);
}
int vertymax(int x1,int x2)
/*求边的上端点的y坐标*/
{int x;
if(x1>x2) x=x1;
   else x=x2;
return x;
 }
int vertymin(int x1,int x2)
/*求边的下端点的y坐标*/
{float x;
 if(x1<x2) x=x1;
 else x=x2;
 return x;
}
void FloodFill(int x,int y,int oldColor,int newColor)
{
 if(getpixel(x,y)==oldColor)
   {putpixel(x,y,newColor);
    FloodFill(x,y+1,oldColor,newColor);
    getch();
    FloodFill(x,y-1,oldColor,newColor);
    FloodFill(x-1,y,oldColor,newColor);
    FloodFill(x+1,y,oldColor,newColor);
   }
 }

main()
{
 struct Edge *p,*s,*r,*net[480],*Ael=NULL;
 struct point *q,*t,*head;
 int i,y,m=0;
 int x0,y0;
 initgr();
 head=creat();
 draw(head);
/*转化为边的结构*/
 q=head; t=head;
 for(i=0;i<480;i++)
    net[i]=NULL;
 while(q!=NULL&&q->next!=NULL)
      {p=(struct Edge*)malloc(sizeof(struct Edge));
       p->ymax=vertymax(q->y,q->next->y);
       if(q->y>q->next->y)p->x=q->next->x;
       else  p->x=q->x;
       p->delatx=(float)(q->x-q->next->x)/(float)(q->y-q->next->y);
       p->nextEdge=NULL;      /*定义一个新的节点边结构节点p*/
       i=vertymin(q->y,q->next->y);
       if(net[i]==NULL&&i<=480) net[i]=p;
       else
          {s=net[i];
           while(s->nextEdge!=NULL)s=s->nextEdge;
           s->nextEdge=p;
          } 
       q=q->next;
     }
  q=head;
  while(q->next!=NULL)q=q->next;
  t=q;q=head;
  p=(struct Edge *)malloc(sizeof(struct Edge));
  p->ymax=vertymax(q->y,t->y);
  if(q->y>t->y)  p->x=t->x;
  else  p->x=q->x;
  p->delatx=(float)(q->x-t->x)/(float)(q->y-t->y);
  p->nextEdge=NULL;      /*定义一个新的节点边结构节点p  */
  i=vertymin(q->y,t->y);
  if(net[i]==NULL&&i<=480)
     net[i]=p;
  else{s=net[i];
      while(s->nextEdge!=NULL)s=s->nextEdge;
      s->nextEdge=p;
     }
 printf("\n边的结构:");
 for(i=0;i<480;i++)
    if(net[i]!=NULL)
    {r=net[i];
     while(r!=NULL)
       {m++;
        printf("\nnet[%d]:%d,%f,%f",i,r->ymax,r->x,r->delatx);
        r=r->nextEdge;
       }
      }
 /*m表示边的分类表中边的个数*/
 printf("\n多边形的边数:m=%d",m);
 y=0;
 while(net[y]==NULL)y++;/**/
 do{
    if(net[y]!=NULL)/*排序插入*/
      {/*全部插入*/
       while(net[y]!=NULL)
         { p=net[y];
           if(Ael==NULL)
             { Ael=p;
               net[y]=p->nextEdge;
               Ael->nextEdge=NULL;
             }
           else
             {s=Ael;
              if(net[y]->x>s->x)
                {while(net[y]->x>s->x&&s!=NULL)
                    {r=s;
                     s=s->nextEdge;
                    }
                 r->nextEdge=p;
                 net[y]=p->nextEdge;
                 p->nextEdge=s;
                }
               else
                {
                 Ael=p;
                 net[y]=p->nextEdge;
                 Ael->nextEdge=s;
                 }
              }
         }
      m=0;
      for(i=0;i<480;i++)
      if(net[i]!=NULL)m++;
     s=Ael;
     printf("\n此时边结构:\n");
     while(s!=NULL){
           printf("%d->(%d,%f,%f)-",y,s->ymax,s->x,s->delatx);
           s=s->nextEdge;  }
     getch();
       }
     s=Ael;
     while(s!=NULL)/*配对，获取有效填充区段，并填充*/
          {line((int)(s->x+0.5),y,(int)(s->nextEdge->x+0.5),y);
           s=s->nextEdge->nextEdge;
          }
     y++;
     /*如果满足条件，则从活化边表中删除*/
     for(s=Ael;s!=NULL;p=s,s=s->nextEdge)
        if(Ael->ymax==y)
           Ael=Ael->nextEdge;
        else if(s!=NULL&&s->ymax==y)
          p->nextEdge=s->nextEdge;
     for(s=Ael;s!=NULL;s=s->nextEdge)
        s->x=s->x+s->delatx;
    }while(Ael!=NULL||m!=0);
getch();
printf("Enter x,y:");
scanf("%d,%d",&x0,&y0);
FloodFill(x0,y0,14,9);
closegr();
}