Line drawing algorithms

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. Start
2. 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 = 1
8. if i> length then go to step no 14
9. Plot (trun(x), trunk(y))
10. x = x + dx;
11. y = y + dy;
12. Increment i
13. go to step no 8
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()
  	{
     		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. Start
Step 2. dx = |x2-x1| // dx is set to positive x difference
Step 3. dy = |y2-y1| // dyisset to positive y difference
Step 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 9
Step 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