Home »
Algorithms
Line Drawing Algorithm
In this article, we are going to learn about LineDrawing algorithms by DDA (Digital Differential analyzer) algorithms and Bresenham’s algorithm in computer graphics.
Submitted by Abhishek Kataria, on July 27, 2018
Line drawing algorithms
 The equation for a straight line is y=mx+b
 In this m represent a slope of a line which can be calculated by the m=y2y1/x2x1 where (x1, y1) are the starting position of the points and (x2, y2) are the end positions of the points.

There are generally three cases arises, which are:
 If an angle is greater than 45 degree then it means the slope is greater than 1 which also mean that dy/dx>1.
 If an angle is less than 45 degree then it means the slope is less than 1 which also mean that dy/dx<1.
 If an angle is equal to 45 degrees then it means the slope is 1 which also means that dy/dx=1.
 The increment in x can be calculated by the x2x1 divided by a total number of steps. Similarly increment of y can be calculated by the y2y1 divided by the total number of steps.
DDA Algorithm
This is a line drawing algorithm which is named as Digital Differential Analyzer (DDA). Basically, it uses the floor function which takes the extra time for generating a line. The DDA algorithm is a faster method for calculating a pixel position for a direct use of it. In some cases, the line drawn by the DDA algorithm is not smooth.
Algorithm DDA (x1, y1, x2, y2)
{
dx=x2x1;
dy=y2y1;
if (abs(dx)>abs(dy))
step=abs(dx)
else
step=abs(dy)
x increment= dx/step
y increment= dy/step
for(i=1;i<=step;i++)
{
putpixel (x1,y1);
x1=x1+increment;
y1=y1+increment;
}
}
Conclusion:
In this algorithm for finding a position of a point, there can be an increment in both x coordinate or can be in a y coordinate. On the basis of it, there are three cases generated which are as given below:
 If the value of m is less than 1, then x=x+1 and y=y+m.
 If the value of m is greater than 1, then x=x+m and y=y+1.
 If the value of m is equal to 1, then x=x and y=y.
Bresenham’s Algorithm
This is an algorithm which is used for drawing a line accurately and efficiently which was developed by Bresenham’s. Here generally, decision parameter is used for finding the next value from the initial one. According to this algorithm value of x will always be incremented but the value of y will be incremented or not it depends upon the decision parameter. This is a faster algorithm and less expensive to implement. There are no criteria of a round of the value in this algorithm which makes this algorithm faster and accurate.
Steps for implementing Bresenham’s algorithm:
1. Read the end points (x1, y1) and (x2, y2).
2. dx=x2x1
dy=y2y1
3. x=x1, y=y1
4. e=2dydx where, e is a decision parameter.
5. While(e>=0)
{
y=y+1
e=e2dx
}
X=x+1
e=e+2dy
6. i<=dx , here i is only dependent upon the value of x.
TOP Interview Coding Problems/Challenges