A line connects two points. It is a basic element in graphics. To draw a line, you need two points between which you can draw a line. In the following three algorithms, we refer the one point of line as x1,y1 and the second point of line as x2,y2.

There are two line drawing algorithms:

1.    DDA algorithm

2.   Bresenhams line drawing algorithm

## DDA algorithm:

#### Input to the algorithm:

(x1,y1) and (x2,y2):  the end co-ordinates of a line.

#### Output of the algorithm:

Bring on pixels closest to the line.

#### Data Variables

(x1,y1) & (x2,y2) :  are real numbers representing end co-ordinates of line segment.
length : stores the length of line segment.
dx, dy :stores increment in x and y direction.
Sign : a function returning 1,0, -1 if argument to the function is > 0; = 0; < 0;

#### Algorithm :

`1. Start2. if |x2-x1| >= |y2-y1| then length = |x2-x1|    else length = |y2-y1|3. dx = (x2-x1) / length.4. dy = (y2-y1) / length.5. x = x1 + 0.5 * sign(dx) /*x1 assumed to be at the leftmost*/6. y = y1 + 0.5 * sign(dy).7. Let i = 18. if i> length then go to step no 149. Plot (trun(x), trunk(y))10. x = x + dx;11. y = y + dy;12. Increment i13. go to step no 814. Stop.`

#### Program :

`#include<iostream>#include<graphics.h>using namespace std;class pixel1{  	public:      	void pix1(int x,int y)	{          	putpixel(x,y,WHITE);	}};class lin1:public pixel1{	public:	void linedraw()  	{     		float x,y,dx,dy;    		int x1,y1,x2,y2,i,length;		cout<<"\n Enter Co-ordinates x1,y1 ::  ";     		cin>>x1>>y1;     		cout<<"\n\n Enter Co-ordinates x2,y2  ::  ";     		cin>>x2>>y2;		int gd=DETECT, gm=0;     		initgraph(&gd,&gm,NULL);     		dx = abs(x2-x1);		dy = abs(y2-y1);		if(dx>=dy) 			length = dx;		else 			length = dy;		dx = dx/length;        	dy = dy/length;        	x=x1;        	y=y1;        	i=1;        	while(i<=length)        	{          		pix1(x,y);          		x = x + dx;          		y = y + dy;          		i++;		}       		getch();       		closegraph();  	}  	int main()  	{		lin1 l1;	    	l1.linedraw();	    	return 0;	}};`

## Bresenham's line generation algorithm

#### Input to the algorithm :

(x1,y1)and (x2,y2) : the integer values of end co-ordinates of a line segment.

#### Output of the algorithm:

Turning on the pixels on the line or close to the line.

#### Data variables:

(X1Y1),(X2,y2) : are integer variables representing end co- ordinates.
dx, dy : integers representing difference in x and y values of the co-ordinates
respectively.
c1, c2 : integers used to store value of expression 2* (dy- dx) and 2* dy before the iteration.
x,y : integers used for plotting the pixel
xend : integer set to highest of x value amongst x1 and x2 integer used as a decision variable.

#### Algorithm:

`Step 1. StartStep 2. dx = |x2-x1| // dx is set to positive x differenceStep 3. dy = |y2-y1| // dyisset to positive y differenceStep 4. d = 2* dy- dx; {initialization of decision variable}Step 5. c1 = 2 * (dy- dx); {pre calculating first expression}Step 6. c2 = 2 * dy; { pre calculating second expression}Step 7. if (x1> x2) then        {           x = x2 ; y = y2; xend = x1;        }        else{x = x1; y = y1; xend = x2;}Step 8. plot (x,y)Step 9. if (x>= xend) then go to step no 14.Step 10. x = x + 1; {increment x value by one pixel}Step 11. if (d > = 0) then {check decision variable}{y = y + 1; {increment y value}d = d + c1 ;}else{ d = d + c2 ; }Step 12. plot (x,y);Step 13. go to step no 9Step 14. stop.`

#### Program :

`#include<iostream>#include<graphics.h>using namespace std;class pixel1{     public:   void pix1(int x,int y)   {        putpixel(x,y,WHITE);   }};class lin1:public pixel1{  public:	void linedraw(int x1,int y1,int x2,int y2)	{	      int i,e,x,y,dx,dy,t=2;	      int gd=DETECT, gm=0;	      initgraph(&gd,&gm,NULL);	      dx = abs(x2-x1);	      dy = abs(y2-y1);	      x=x1;	      y=y1;	      e = 2*dy-dx;	      i=1;	      do{			pix1(x,y);			while(e>=0)			{			      y=y+1;			      pix1(x,y);			      e = e - 2*dx;			}			x++;			e = e + 2*dy;			i++;		}while(i<=dx);		getch();		closegraph();	}};int main(){	lin1 l1;	int x1,x2,y1,y2;	cout<<"\n Enter Co-ordinates x1,y1 ::  ";   	cin>>x1>>y1;  	cout<<"\n\n Enter Co-ordinates x2,y2  ::  ";   	cin>>x2>>y2;	l1.linedraw(x1,y1,x2,y2);	return 0;}`

Learn how to run C/C++ graphics programs on Ubuntu here