#include "math.h"
#include "graphics.h"
#define SIZE 10000
#define N 4
#define PI 3.14159265358979323846
typedef struct{ int x; int y;} point ;
typedef struct{ 
                point *base;
                point *top ;
                int    size;
               } stack ;
void initiate(stack *s);
void push(point seed,stack *s);
void pop(point *seed,stack *s);
void bresenham_line(int x0,int y0,int x1,int y1,int color);
void casteljau_bezier(int x[N],int y[N],int color);
void seed_fill(int boundcolor ,point seed, int color,stack s);
void coordinate_set() ;
void print();
void initgr(void)
{
  int gd = DETECT, gm = 0;
  registerbgidriver(EGAVGA_driver);
  initgraph(&gd, &gm, "");
}

main()
{
  int i,j;
  int x1[]={50,155,200,256},y1[]={52,125,18,54},
      x2[]={25,130,200,256},y2[]={20,110,-50,54} ,
      xx1[N], yy1[N], xx2[N], yy2[N];
  float sn,cs,sx;
  point seed={400,180};
  point a[6]={54,88,68,88,50,52,256,54,25,20,20,20}, aa[6];
  stack s;
  initgr();
  initiate(&s);
  coordinate_set();  /*畫坐標系*/
  for(j=0;j<N;j++)
    {
      xx1[j]=x1[j];yy1[j]=y1[j];
      xx2[j]=x2[j];yy2[j]=y2[j];
    }
  for(j=0;j<6;j++)
    {
      aa[j].x=a[j].x;
      aa[j].y=a[j].y;
    }

  for(i=0;i<60;i++)
    {  
       sn=sin(i*PI/30);    /*旋轉因子*/
       cs=cos(i*PI/30);
       sx=(float)(100-i)/100.0;  /*比例因子*/

       for(j=0;j<4;j++)        /*圖上坐標的比例變換加旋轉變換*/
         {
           x1[j]=(xx1[j]*cs-yy1[j]*sn)*sx;
           y1[j]=(xx1[j]*sn+yy1[j]*cs)*sx;
           x2[j]=(xx2[j]*cs-yy2[j]*sn)*sx;
           y2[j]=(xx2[j]*sn+yy2[j]*cs)*sx;
         }
       for(j=0;j<6;j++)
         {
           a[j].x=(aa[j].x*cs-aa[j].y*sn)*sx;
           a[j].y=(aa[j].x*sn+aa[j].y*cs)*sx;
         }

       for(j=0;j<N;j++)         /*坐標變換……由圖上坐標到屏幕坐標*/
         { 
           x1[j]+=320; y1[j]=240-y1[j];
           x2[j]+=320; y2[j]=240-y2[j];
         }
       for(j=0;j<6;j++)
         { 
           a[j].x+=320; a[j].y=240-a[j].y;
         }

       setcolor(YELLOW);
       bresenham_line(a[0].x,a[0].y,a[1].x,a[1].y,YELLOW);
       bresenham_line(a[1].x,a[1].y,a[2].x,a[2].y,YELLOW);
       bresenham_line(a[4].x,a[4].y,a[5].x,a[5].y,YELLOW);
       bresenham_line(a[0].x,a[0].y,a[5].x,a[5].y,YELLOW);
       casteljau_bezier(x1,y1,YELLOW);
       casteljau_bezier(x2,y2,YELLOW);
       print();

       if(i==0)
       seed_fill(YELLOW,seed,RED,s);

       for(j=0;j<N;j++)         /*坐標還原……由屏幕坐標到圖上坐標*/
         { 
           x1[j]-=320; y1[j]=240-y1[j];
           x2[j]-=320; y2[j]=240-y2[j];
         }
       for(j=0;j<6;j++)
         { 
           a[j].x-=320; a[j].y=240-a[j].y;
         }

    }

  getch();
  closegraph();
}

void initiate(stack *s)

{   
    s->base=(point*)malloc(SIZE*sizeof(point));
    s->top=s->base;
    s->size=SIZE;
}

void push(point seed,stack *s)

{   
  if(s->top-s->base>=s->size)
   {
     s->base=(point*)realloc(s->base,(s->size+100)*sizeof(point));
     s->top=s->base+s->size;
     s->size+=100;
   }
  (s->top)->x=seed.x;
  (s->top)->y=seed.y;
  s->top++;
}

void pop(point *seed,stack *s)

{   
   if(s->top!=s->base)
    {
      s->top--;
      seed->x=(s->top)->x;
      seed->y=(s->top)->y;
    }
}

void bresenham_line(int x0,int y0,int x1,int y1,int color)

{
  int i,x,y,dx,dy,n,flag,e=0;
  dx=x1-x0;  dy=y1-y0;
  flag=(dx*dy>=0)?1:-1;
  dx=abs(dx); dy=abs(dy);
  if(dy<=dx)
  {
     n=dx;
     if(x1>x0) { x=x0; y=y0;}
     else { x=x1; y=y1;}
     e=2*dy-dx;
     for(i=0;i<=n;i++)
       {
         putpixel(x,y,color);
         if(e>=0) {y=y+flag;e+=2*(dy-dx);}
         else e+=2*dy;
         x=x+1;
       }
  }
  else
    {
      n=dy;
      if(y1>y0) { x=x0; y=y0;}
      else { x=x1;y=y1;}
      e=2*dx-dy;
      for(i=0;i<=n;i++)
        {
          putpixel(x,y,color);
          if(e>=0) {x=x+flag; e+=2*(dx-dy);}
          else e+=2*dx;
          y=y+1;
        }
    }
}

void casteljau_bezier(int x[N],int y[N],int color)

{
  int i,j;
  float t,xx[N],yy[N];
  for(t=0;t<=1;t=t+0.0006)
    { 
      for(i=0;i<N;i++)
        {
          xx[i]=(float)x[i]; yy[i]=(float)y[i];
        }  
      for(i=1;i<N;i++)
         for(j=0;j<=N-i;j++)
           {   
             xx[j]=(1-t)*xx[j]+t*xx[j+1];
             yy[j]=(1-t)*yy[j]+t*yy[j+1];
           }
     putpixel(xx[0],yy[0],color);

    }
}


void seed_fill(int boundcolor ,point seed, int color,stack s)

{
  int x,y;
  push(seed,&s);
  while(s.top!=s.base)
     { 
       pop(&seed,&s);
       x=seed.x; y=seed.y;
       putpixel(seed.x,seed.y,color);
       if(getpixel(x-1,y)!=boundcolor&&getpixel(x-1,y)!=color)
         {
           seed.x=x-1; seed.y=y; push(seed,&s);
         }
       if(getpixel(x+1,y)!=boundcolor&&getpixel(x+1,y)!=color)
         {
           seed.x=x+1; seed.y=y; push(seed,&s);
         }
       if(getpixel(x,y-1)!=boundcolor&&getpixel(x,y-1)!=color)
         {
           seed.y=x; seed.y=y-1; push(seed,&s);
         }
       if(getpixel(x,y+1)!=boundcolor&&getpixel(x,y+1)!=color)
         {
           seed.x=x; seed.y=y+1; push(seed,&s);
         }

        if(seed.y>221) break;
    }
}

void coordinate_set()

{   
    setcolor(BLUE);
    line(100,240,540,240);
    line(520,235,540,240);
    line(520,245,540,240);
    line(320,20,320,460);
    line(315,40,320,20);
    line(325,40,320,20);
    outtextxy(530,250,"X");
    outtextxy(330,230,"0");
    outtextxy(340,30,"Y");
}
void print()
{    setcolor(YELLOW);

}