The scanline fill algorithm is an ingenious way of filling in irregular polygons. The algorithm begins with a set of points. Each point is conected to the next, and the line between them is considered to be an edge of the polygon. The points of each edge are adjusted to ensure that the point wih the smaller y value appears first. Next, a data structure is created that contains a list of edges that begin on each scanline of the image. The program progresses from the first scanline upward. For each line, any pixels that contain an intersection between this scanline and an edge of the polygon are filled in. Then, the algorithm progresses along the scanline, turning on when it reaches a polygon pixel and turning off when it reaches another one, all the way across the scanline.

There are two special cases that are solved by this algorithm. First, a problem may arise if the polygon contains edges that are partially or completely out of the image. The algorithm solves this problem by moving pixel values that are outside the image to the boundaries of the image. This method is preferable to eliminating the pixel completely, because its deletion could result in a “backwards” coloring of the scanline i.e. pixels that should be on are off and vice versa.

The second case has to do with the concavity of the polygon. If the polygon has a concave portion, the algorithm will work correctly. The pixel on which the two edges meet will be marked twice, so that it is turned off and then on. If, however, the polygon is convex at the intersection of two edges, the coloring will turn on and then immediately off, resulting in “backwards” coloring for the rest of the scanline. The problem is solved by using the vertical location of the next point in the polygon to determine the concavity of the current portion. Overall, the algorithm is very robust. It turns out that the only difficulty comes with polygons that have large amounts of edges, like circles and ellipses. Filling in such a polygon would be very costly. Luckily, there is a better way to fill circles and ellipses. Below is an image of a polygon filled in with scanfill.

#include <iostream.h>

#include <graphics.h>

#include <conio.h>


const int n=10;
const int ymax=480;
class edge
{
	public:
	float x,y,n;
	edge *link;

	edge()
	{
		link=NULL;
	}

	void update(void)
	{
		x+=n;
	};
};

struct point
{
	float x,y;
};

point pt[n];

void swap(edge **e1, edge **e2)
{
		float temp;
		temp=(*e2)->x;
		(*e2)->x=(*e1)->x;
		(*e1)->x=temp;
		temp=(*e2)->y;
		(*e2)->y=(*e1)->y;
		(*e1)->y=temp;
		temp=(*e2)->n;
		(*e2)->n=(*e1)->n;
		(*e1)->n=temp;
}

edge *del(edge *aet, int i)
{
	edge *p=aet;
	edge *prev=NULL;
	while(p)
	{
		if ((*p).y==i)
		{
			if (p==aet)
			{
				p=aet->link;
				delete aet;
				aet=p;
					 continue;
			}
			else
			{
				prev->link=p->link;
				delete p;
				p=prev;
			}
		}
		prev=p;
		p=p->link;
	}
	return aet;
}

edge *update(edge *aet)
{
	edge *p=aet;
	while (p)
	{
		p->update();
		p=p->link;
	}
	return aet;
};

edge *merge(edge *aet, edge *g[], int i)
{
	edge *p;
	p=g[i];
	while(p->link)
		p=p->link;
	p->link=aet;
	return g[i];
}

edge *sort(edge *aet)
{
	int len=0;
	edge *p=aet;
	while (p)
		p=p->link,len++;
	for (int i=0;i<len-1;i++)
		for (int j=0;j<len-i-1;j++)
		{
			edge *e1, *e2;
			e1=aet;
			for (int k=0;k<j;k++)
				e1=e1->link;
			e2=e1->link;
			if (e1->x>e2->x)
			{
				swap(&e1, &e2);
			}
		}
	return aet;
}

void main()
{
	int gdriver = DETECT, gmode = VGAHI;
	initgraph(&gdriver, &gmode, "");
	edge *get[ymax];
	for (int i=0;i<ymax;i++)
		get[i]=NULL;
	for (i=0;i<n;i++)
	{
		cout<<"Enter x for point "<<i+1<<" : ";
		cin>>pt[i].x;
		pt[i].x*=10;
		cout<<"Enter y for point "<<i+1<<" : ";
		cin>>pt[i].y;
		pt[i].y*=10;
	}
	int ypt[n][2],j,temp,ymin,flag=0;
	for (i=0;i<n;i++)
		ypt[i][0]=i,ypt[i][1]=0;
	for (i=0;i<n-1;i++)
		for (j=0;j<n-i-1;j++)
			if (pt[ypt[j][0]].y>pt[ypt[j+1][0]].y)
			{
				temp=ypt[j][0];
				ypt[j][0]=ypt[j+1][0];
				ypt[j+1][0]=temp;
			}
	ymin=pt[ypt[0][0]].y;
	int	max=pt[ypt[n-1][0]].y;
	for (i=0;i<n;i++)
	{
		if (ypt[i][1]==0)
		{
			if ((pt[ypt[i][0]].y-pt[(ypt[i][0]+1)%n].y)==0)
				continue;
			edge *e;
			e=new edge;
			ymin=pt[ypt[i][0]].y<pt[(ypt[i][0]+1)%n].y?pt[ypt[i][0]].y:pt[(ypt[i][0]+1)%n].y;
			e->y=pt[ypt[i][0]].y>pt[(ypt[i][0]+1)%n].y?pt[ypt[i][0]].y:pt[(ypt[i][0]+1)%n].y;
			e->x=pt[ypt[i][0]].y<pt[(ypt[i][0]+1)%n].y?pt[ypt[i][0]].x:pt[(ypt[i][0]+1)%n].x;
			e->n=(pt[ypt[i][0]].x-pt[(ypt[i][0]+1)%n].x)/(pt[ypt[i][0]].y-pt[(ypt[i][0]+1)%n].y);
			ypt[i][1]=1;
			if (get[ymin]==NULL)
			{
				get[ymin]=e;
			}
			else
			{
				edge *b;
				b=get[ymin];
				while (b->link)
					b=b->link;
				b->link=e;
			}
		}
	}
	line(0,getmaxy()/2,getmaxx(),getmaxy()/2);
	line(getmaxx()/2,0,getmaxx()/2,getmaxy());
	setcolor(BLUE);
	edge *aet=NULL;
	for (i=0;i<=max;i++)
	{
	aet=update(aet);
	if (get[i])
		{
			aet=merge(aet,get,i);
		}
	aet=sort(aet);
	edge *p;
	p=aet;
	while (p&&p->link)
	{
		if (p->y==p->link->y)
		{
			flag=1;
		}
		if (p->y==i)
		{
			line(getmaxx()/2+p->x,getmaxy()/2-i,getmaxx()/2+p->link->x,getmaxy()/2-i);
		}
		p=p->link->link;
	}
	if (flag)
	{
	p=aet;
	while (p&&p->link) //As there can be odd number of nodes in this case

	{
		line(getmaxx()/2+p->x,getmaxy()/2-i,getmaxx()/2+p->link->x,getmaxy()/2-i);
		p=p->link->link;
	}
	aet=del(aet,i);
	}
	else
	{
	aet=del(aet,i);
	p=aet;
	while (p&&p->link)
	{
		line(getmaxx()/2+p->x,getmaxy()/2-i,getmaxx()/2+p->link->x,getmaxy()/2-i);
		p=p->link->link;
	}
	}
	flag=0;
	}
	getch();
}