Program to implement Scan line Algorithm

Scan line Algorithm 

• The scan line algorithm is an alternative to the seed fill algorithm. 
• It does not require scan conversion of the edges before filling the polygons 
• It can be applied simultaneously to a set of polygons rather than filling each polygon individually.

We also call it Scan line polygon fill algorithm as it is used to generate polygons.

Algorithm for Scan line C++ code- 

Step1: Start algorithm

Step2: Initialize the desired data structure

1. Create a polygon table having color, edge pointers, coefficients
2. Establish edge table contains information regarding, the endpoint of edges, pointer to polygon, inverse slope.
3. Create Active edge list. This will be sorted in increasing order of x.
4. Create a flag F. It will have two values either on or off.

Step3: Perform the following steps for all scan lines

1. Enter values in Active edge list (AEL) in sorted order using y as value
2. Scan until the flag, i.e. F is on using a background color
3. When one polygon flag is on, and this is for surface S₁enter color intensity as I₁into refresh buffer
4. When two or image surface flag are on, sort the surfaces according to depth and use intensity value S_n for the nth surface. This surface will have least z depth value
5. Use the concept of coherence for remaining planes.

Step4: Stop Algorithm

Scan line algorithm c++ code - 

#include<bits/stdc++.h>

#include<graphics.h>

using namespace std;

int main()

{

int n,x[10],y[10],k=0,ymin=1000000,ymax=0,Y,dx,dy,xi[100],gm,gd,temp;

float slope[100];

printf("Enter the number of vertices:");

scanf("%d",&n);

printf("enter the coordinates of vertices:");

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

{

scanf("%d%d",&x[i],&y[i]);

if(y[i]>ymax)

ymax=y[i];

if(y[i]<ymin)

ymin=y[i];

}

detectgraph(&gd,&gm);

initgraph(&gd,&gm," ");

x[n]=x[0];y[n]=y[0];

//draw polygon using all the edges

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

{

line(x[i],y[i],x[i+1],y[i+1]);

}

//

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

{

dx=x[i+1]-x[i];

dy=y[i+1]-y[i];

if(dy==0)slope[i]=1.0;

if(dx==0)slope[i]=0.0;

if(dx!=0 && dy!=0)

slope[i]=(float)dx/dy;

}

for(int j=0;j<=ymax;j++)

{

int k=0;

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

if(((y[i]<=j) && (y[i+1]>j)) || ((y[i]>j) && (y[i+1]<=j))){

xi[k]=(int)(x[i]+slope[i]*(j-y[i]));

k++;

}

}

for(int m=0;m<k-1;m++){

for(int i=0;i<k-1;i++){

if(xi[i]>xi[i+1]){

temp=xi[i];

xi[i]=xi[i+1];

xi[i+1]=temp;

}

}

setcolor(2);

for(int i=0;i<k;i+=2){

line(xi[i],j,xi[i+1]+1,j);delay(100);

}

}

}

return 0;

}

OUTPUT-
Enter the number of vertices: 5
enter the coordinates of vertices:
30 30
30 150
120 60
120 120
210 30