#include "stdafx.h"
#include "graph.h"
#include "math.h"
CGraph::CGraph(CWnd * cp):CClientDC(cp)
{}
void CGraph::DDALine(int x1,int y1,int x2,int y2,COLORREF color,int width)
{
	int i,j;
	float dx,dy,k,p;
	dy=float(y2-y1);
	dx=float(x2-x1);
	if(dx!=0)
	{
		k=dy/dx;
		if(k<=1&&k>=-1)
		{
			p=float(y1);
			if(dx>0)
			{
				for(i=x1;i<=x2;i++)
				{
				    for(j=-width/2;j<(width+1)/2;j++)
					    SetPixel(i,int(p+0.5)+j,color);
				    p=p+k;
				}
			}
		    else
			{
			    for(i=x1;i>=x2;i--)
				{
				    for(j=-width/2;j<(width+1)/2;j++)
					   SetPixel(i,int(p+0.5)+j,color);
				   p=p-k;
				}
			}
		}
	    else
		{
		   p=float(x1);
		   if(dy>0)
		   {
			   for(i=y1;i<=y2;i++)
			   {
				   for(j=-width/2;j<(width+1)/2;j++)
					SetPixel(int(p+0.5)+j,i,color);
				   p=p+1/k;
			   }
		   }
		   else
		   {
			   for(i=y1;i>=y2;i--)
			   {
				  for(j=-width/2;j<(width+1)/2;j++)
					SetPixel(int(p+0.5)+j,i,color);
				  p=p-1/k;
			   }
		   }
		}
	}
	else
	{
		p=float(x1);
		if(dy>0)
			for(i=y1;i<=y2;i++)
				for(j=-width/2;j<(width+1)/2;j++)
					SetPixel(int(p)+j,i,color);
		else
			for(i=y1;i>=y2;i--)
				for(j=-width/2;j<(width+1)/2;j++)
					SetPixel(int(p)+j,i,color);
	} 
}
void CGraph::MidPointCircle(int xc,int yc,int r,COLORREF color)
{
	int x,y,d;
	x=0;y=r;d=1-r;
	WholeCircle(xc,yc,x,y,color);
	while(x<y)
	{
		x++;
		if(d<0)
		{
			d+=2*x+3;
		}
		else
		{
			d+=2*(x-y)+5;
			y--;
		}
		WholeCircle(xc,yc,x,y,color);
	}//hile
	WholeCircle(xc,yc,x,y,color);
}//MidpointCircle
void CGraph::WholeCircle(int xc,int yc,int x,int y,COLORREF color)
{
	SetPixel(xc+x,yc+y,color);
	SetPixel(xc-x,yc+y,color);
	SetPixel(xc+x,yc-y,color);
	SetPixel(xc-x,yc-y,color);
	SetPixel(xc+y,yc+x,color);
	SetPixel(xc-y,yc+x,color);
	SetPixel(xc+y,yc-x,color);
	SetPixel(xc-y,yc-x,color);
}
void CGraph::InsertEdge(Edge * list,Edge * edge)
{
		Edge * p,*q=list;
		p=q->next;
		while (p!=NULL)
		{if (edge->x<p->x)
		    p=NULL;
		 else
		 {q=p;
		  p=p->next;
		 }
		}
		edge->next=q->next;
		q->next=edge;
}
int CGraph::yNext (int k,int cnt,POINT * pts)     
{
		int j;
		if((k+1)>(cnt-1))
			j=0;
		else
			j=k+1;
		while (pts[k].y==pts[j].y)
			if ((j+1)>(cnt-1))
				j=0;
			else
			    j++;
		return (pts[j].y);
}
void CGraph::MakeEdgeRec(POINT lower,POINT upper,int yComp,Edge * edge,Edge * edges[])
{
		edge->dx=(float)(upper.x-lower.x)/(upper.y-lower.y);
		edge->x=(float)lower.x;
		if (upper.y<yComp)
			edge->ymax=upper.y-1;
		else
			edge->ymax=upper.y;
		InsertEdge(edges[lower.y],edge);
}
void CGraph::BuildEdgeList(int cnt,POINT * pts,Edge * edges[])  
{
		Edge *edge;
		POINT v1,v2;
		int i,yPrev=pts[cnt-2].y;
		v1.x=pts[cnt-1].x;
		v1.y=pts[cnt-1].y;
		for (i=0;i<cnt;i++)
		{
			v2=pts[i];
			if(v1.y!=v2.y)
            {
				edge=(Edge*)malloc(sizeof(Edge));
				if(v1.y<v2.y)
					MakeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);
				else
					MakeEdgeRec(v2,v1,yPrev,edge,edges);
			}
			yPrev=v1.y;
			v1=v2;
		}
}
void CGraph::BuildActiveList(int scan,Edge * active,Edge * edges[])  
{
		Edge *p,*q;
		p=edges[scan]->next;
		while(p)
		{
			q=p->next;
			InsertEdge(active,p);
			p=q;
		}
}
void CGraph::FillScan(int scan,Edge * active,COLORREF color)    
{
		Edge *p1,*p2;
		int i;
		p1=active->next;
		while(p1)
		{
			p2=p1->next;
			for(i=(int)p1->x;i<p2->x;i++)
				SetPixel((int)i,scan,color);
			p1=p2->next;
		}
}
void CGraph::DeleteAfter(Edge *q)    
{
		Edge *p=q->next;
		q->next=p->next;
		free(p);
}

void CGraph::UpdateActiveList(int scan,Edge * active)  
{
		Edge *q=active,*p=active->next;
		while(p)
		if(scan>=p->ymax)
		{
			p=p->next;
			DeleteAfter(q);
		}
		else
		{
			p->x=p->x+p->dx;
			q=p;p=p->next;
		}
}

void CGraph::ResortActiveList(Edge * active)   
{
		Edge *q,*p=active->next;
		active->next=NULL;
		while(p)
		{
			q=p->next;
			InsertEdge(active,p);
			p=q;
		}
}

void CGraph::AreaFill (int cnt,POINT *pts,COLORREF color)
{
		Edge * edges[WINDOW_HEIGHT],*active;
		int i,scan,scanmax=0,scanmin=WINDOW_HEIGHT;
		for(i=0;i<cnt-1;i++)
		{
			if(scanmax<pts[i].y)scanmax=pts[i].y;
			if(scanmin>pts[i].y)scanmin=pts[i].y;
		}
		for(scan=scanmin;scan<=scanmax;scan++)
		{
			edges[scan]=(Edge *)malloc(sizeof(Edge));
			edges[scan]->next=NULL;
		}
		BuildEdgeList(cnt,pts,edges);
		active=(Edge *)malloc(sizeof(Edge));
		active->next=NULL;
		for(scan=scanmin;scan<=scanmax;scan++)
		{
			BuildActiveList(scan,active,edges);
			if(active->next)
			{
				FillScan(scan,active,color);
				UpdateActiveList(scan,active);
				ResortActiveList(active);
			}
		}
}





void CGraph::drawrect(int x0, int y0, int x1, int y1)
{
	DDALine(x0,y0,x1,y0,RGB(255,0,0),1);
	DDALine(x1,y0,x1,y1,RGB(255,0,0),1);
	DDALine(x1,y1,x0,y1,RGB(255,0,0),1);
	DDALine(x0,y1,x0,y0,RGB(255,0,0),1);

}

void CGraph::FillRect(int x0, int y0, int x1, int y1, COLORREF fillcolor)
{
	drawrect(x0,y0,x1,y1);
	for(int i=y0+1;i<y1;i++)
		for(int j=x0+1;j<x1;j++)
			SetPixel(j,i,fillcolor);

}

void CGraph::FillCircle(int x0, int y0, int x1, int y1,COLORREF color, COLORREF fillcolor)
{
	int r,dx,dy;
	dx=x1-x0;
	dy=y1-y0;
	r=(int)(sqrt(dx*dx+dy*dy)+0.5);
	Circle0(x0,y0,r,color,fillcolor);

}

void CGraph::Circle0(int x0, int y0, int r,COLORREF color, COLORREF fillcolor)
{
	int i,x,y,yy,delta,delta1,delta2,dir;
	x=0;
	y=r;
	yy=y;
	delta=2*(1-r);
	while(y>=0)
	{
		SetPixel(x+x0,y+y0,color);
		SetPixel(-x+x0,y+y0,color);
		SetPixel(x+x0,-y+y0,color);
		SetPixel(-x+x0,-y+y0,color);
		if(yy!=y)
		{
			for(i=-x+x0+1;i<x+x0;i++)
				SetPixel(i,y+y0,fillcolor);
			for(i=-x+x0+1;i<x+x0;i++)
				SetPixel(i,-y+y0,fillcolor);
		}
		yy=y;
		if(delta<0)
		{
			delta1=2*(delta+y)-1;
			if(delta1<=0)
				dir=1;
			else
				dir=2;
		}
		else if(delta>0)
		{
			delta2=2*(delta-x)-1;
			if(delta2<=0)
				dir=2;
			else
				dir=3;
		}
		else
			dir=2;
		switch(dir)
		{
		case 1:
			x++;
			delta+=2*x+1;
			break;
		case 2:
			x++;
			y--;
			delta+=2*(x-y+1);
			break;
		case 3:
			y--;
			delta+=-2*y+1;
			break;
		}
	}

}

void CGraph::DrawEllipse(int x1, int y1, int x2, int y2, COLORREF color)
{
	int xx0,yy0,rra,rrb;
	xx0=(x2+x1)/2;
	yy0=(y2+y1)/2;
	rra=abs(x2-x1)/2;
	rrb=abs(y2-y1)/2;
	if(rra==0 && rrb==0) return;
	Ellipse1(xx0,yy0,rra,rrb,color);
}

void CGraph::Ellipse1(int x0, int y0, int a, int b, COLORREF color)
{
	int yy;
	int x,y,deltax,deltay;
	int aa,aa2,aa3,bb,bb2,bb3;
	double d1,d2;
	aa=a*a;
	aa2=aa*2;
	aa3=aa*3;
	bb=b*b;
	bb2=bb*2;
	bb3=bb*3;
		
	x=0;
	y=b;
	d1=bb+aa*(-b+0.25);
	deltax=bb3;
	deltay=-aa2*b+aa2;
	SetPixel(x+x0,y+y0,color);
	SetPixel(x+x0,-y+y0,color);
	while(bb*(x+1)<aa*(y-0.5))
	{
		yy=y;
		if(d1<0)
		{
			d1+=deltax;
			deltax+=bb2;
			x++;
		}
		else
		{
			d1+=deltax+deltay;
			deltax+=bb2;
			deltay+=aa2;
			x++;
			y--;
		}
		SetPixel(x+x0,y+y0,color);
		SetPixel(-x+x0,y+y0,color);
		SetPixel(x+x0,-y+y0,color);
		SetPixel(-x+x0,-y+y0,color);
	}
	d2=bb*(x+0.5)*(x+0.5)+aa*(y-1)*(y-1)-aa*bb;
	deltax-=bb;
	deltay+=aa;
	while(y>0)
	{
		if(d2<0)
		{
			d2+=deltax+deltay;
			deltax+=bb2;
			deltay+=aa2;
			x++;
			y--;
		}
		else
		{
			d2+=deltay;
			deltay+=aa2;
			y--;
		}
		SetPixel(x+x0,y+y0,color);
		SetPixel(-x+x0,y+y0,color);
		SetPixel(x+x0,-y+y0,color);
		SetPixel(-x+x0,-y+y0,color);
	
	}

}




void CGraph::FillEllipse(int x1, int y1, int x2, int y2, COLORREF color, COLORREF fillcolor)
{
	int x0,y0,a,b;
	x0=(x2+x1)/2;
	y0=(y2+y1)/2;
	a=abs(x2-x1)/2;
	b=abs(y2-y1)/2;
	if(a==0 && b==0) return;
	Ellipse0(x0,y0,a,b,color,fillcolor);
}

void CGraph::Ellipse0(int x0, int y0, int a, int b, COLORREF color, COLORREF fillcolor)
{
	int i,yy;
	int x,y,deltax,deltay;
	int aa,aa2,aa3,bb,bb2,bb3;
	double d1,d2;
	aa=a*a;
	aa2=aa*2;
	aa3=aa*3;
	bb=b*b;
	bb2=bb*2;
	bb3=bb*3;
		
	x=0;
	y=b;
	d1=bb+aa*(-b+0.25);
	deltax=bb3;
	deltay=-aa2*b+aa2;
	SetPixel(x+x0,y+y0,color);
	SetPixel(x+x0,-y+y0,color);
	while(bb*(x+1)<aa*(y-0.5))
	{
		yy=y;
		if(d1<0)
		{
			d1+=deltax;
			deltax+=bb2;
			x++;
		}
		else
		{
			d1+=deltax+deltay;
			deltax+=bb2;
			deltay+=aa2;
			x++;
			y--;
		}
		SetPixel(x+x0,y+y0,color);
		SetPixel(-x+x0,y+y0,color);
		SetPixel(x+x0,-y+y0,color);
		SetPixel(-x+x0,-y+y0,color);
		if(yy!=y)
		{
			for(i=-x+x0+1;i<x+x0;i++)
				SetPixel(i,y+y0,fillcolor);
			for(i=-x+x0+1;i<x+x0;i++)
				SetPixel(i,-y+y0,fillcolor);
		}
	}
	d2=bb*(x+0.5)*(x+0.5)+aa*(y-1)*(y-1)-aa*bb;
	deltax-=bb;
	deltay+=aa;
	while(y>0)
	{
		if(d2<0)
		{
			d2+=deltax+deltay;
			deltax+=bb2;
			deltay+=aa2;
			x++;
			y--;
		}
		else
		{
			d2+=deltay;
			deltay+=aa2;
			y--;
		}
		SetPixel(x+x0,y+y0,color);
		SetPixel(-x+x0,y+y0,color);
		SetPixel(x+x0,-y+y0,color);
		SetPixel(-x+x0,-y+y0,color);
	
			for(i=-x+x0+1;i<x+x0;i++)
				SetPixel(i,y+y0,fillcolor);
			for(i=-x+x0+1;i<x+x0;i++)
				SetPixel(i,-y+y0,fillcolor);
	}
}