# Bresenham's Line Drawing Algorithm in Computer Graphics

**Computer Graphics | Bresenham's Line Drawing Algorithm**: In this tutorial, we will learn about the Bresenham's line drawing algorithm. Also, we will be learning about how it is implemented in drawing a line by defining its entire algorithm, and also by taking some examples. Finally, we would be discussing the advantages and disadvantages of this algorithm.

Submitted by Monika Sharma, on April 24, 2020

**Bresenham's algorithm** was proposed to overcome the drawbacks of the DDA algorithm. First, let us see what the drawbacks of DDA algorithm were,

**Drawbacks of DDA algorithm:**

The only drawback of the DDA algorithm was that it produces floating-point results which reduces the overall complexity. This problem was solved by Bresenham's line drawing algorithm.

## Introduction to Bresenham's Algorithm

**Bresenham's line drawing algorithm** is a second method of generating a line that was proposed after the DDA algorithm to overcome its limitations and drawbacks. It was developed by J.E. Bresenham in 1962. This algorithm is used for calculating intermediate coordinate points between the given source and ending points by only using integer addition and subtraction.

This algorithm determines the points which should be selected to form a close approximation to a line between two points.

It is also an incremental method for creating a line.

It is faster than the DDA algorithm as it does not involves the use of heavy operations such as multiplication and division.

### Working of the Bresenham's Algorithm

Suppose we have to draw a line **PQ** with coordinates **P (x1, y1)** and **Q (x2, y2)**.

To draw the line using Breshenam's line drawing algorithm, first of all, calculate the slope of the line from the given coordinates by using,

m = dy/dx Where, dy = x2 - x1 dx = y2 - y1

There can be three values of slope (m) i.e.

a. m < 1 b. m > 1 c. m = 1

On the basis of the value of the slope, the decision parameter is calculated which gives the decision about the selection of the next pixel point which has the least distance from the true line.

We'll be deriving the decision parameter **P _{k}** for slope

**(m < 1)**, to make things clear.

### Derivation of the decision parameter P_{k}

Let us consider a straight line passing through a point **A (x _{k}+1, y)**,

Where,

x_{k}+1 = x_{k}+ 1

and **y** satisfies the equation of the line i.e.

y = m (x_{k}+ 1) + c ------(1)

The next pixel to the line will be either to its top or to its bottom.

If we choose the top pixel, the points at **B** will become,

x_{k}+1 = x_{k}+ 1 and y = y_{k}+ 1

If we choose bottom pixel, the points at **C** will become,

x_{k}+1 = x_{k}+ 1 and y = y_{k}

Since **Bresenham's algorithm** depends upon the distance, let's calculate it between **A** and **B**; and **A** and **C**.

For **A** and **B**: let the distance be denoted as **s**.

s = ( y_{k}+ 1 ) - y

For **A** and **C**: let the distance be denoted as **t**.

t = y - y_{k}

Now consider their difference:

(t – s) = y - y_{k}- [ (y_{k}+ 1) - y] = 2y - 2y_{k}- 1 ------(2)

When (t - s) < 0 => t < s, then the closest pixel will be C.

When (t - s) > 0 => s < t, then the closest pixel will be B.

Putting the value of eq.(1) in eq.(2);

t – s = 2m ( x_{k }+ 1 ) + 2c - 2y_{k }- 1

Now, substituting the value of m;

t – s = 2dy ( x_{k }+ 1 ) / dx + 2c - 2y_{k }- 1

To remove dx from denominator, multiply dx on both sides;

dx (t - s) = dx ( 2dy ( x_{k }+ 1 ) / dx + 2c - 2y_{k }– 1 )

let P_{k }= dx (t - s), thus introducing the decision variable

P_{k }= 2dy . x_{k }- 2dx . y_{k }+ b

B = 2dy + dx ( 2c – 1 )

Let us calculate next decision variable:

P_{k+1 }= 2dy . x_{k+1 }- 2dx . y_{k+1 }+ b

Now, solve the difference P_{k+1 }- P_{k}

P_{k+1 }- P_{k }= 2dy . x_{k+1 }- 2dx . y_{k+1 }+ b - ( 2dy . x_{k }- 2dx . y_{k }+ b )

= 2dy . x_{k+1 }- 2dx . y_{k+1 }- 2dy . x_{k }- 2dx . y_{k}

Since x_{k+1 }= x_{k }+ 1

P_{k+1 }- P_{k }= 2dy . (x_{k }+ 1) - 2dx . y_{k+1 }- 2dy . x_{k }- 2dx . y_{k}

_{ }P_{k+1 }= P_{k }+ 2dy - 2dx . y_{k+1 }- 2dx . y_{k}

**Special Cases:**

When P_{k }>= 0 => y_{k+1 }= y_{k }+ 1 i.e. point B is chosen

P_{k+1 }= P_{k }+ 2dy - 2dx

When P_{k }< 0 => y_{k+1 }= y_{k }i.e. point C is chosen

P_{k+1 }= P_{k }+2dy

Now, we will calculate the initial decision variable by using

P_{0 }= dx ( 2dy ( x_{0 }+ 1 ) / dx + 2c - 2y_{0 }– 1 )

Put c = y_{0 }- x_{0. }( dy / dx )

We get

P_{0 }= 2dy – dx

**Algorithm:**

Step1: Start

Step2: Declare x1, y1, x2, y2.

Step3: Calculate dx = x2 - x1

Dy = y2 - y1

Step 4: Calculate slope, m = dy / dx.

Step5: For m < 1: Calculate initial decision variable: P = 2dy - dx.

Step6: while (x1 <= x2)

if(P < 0):

x_{k }= x_{k }+ 1

P = P + 2dy

y_{k }= y_{k}

else :

x_{k }= x_{k }+ 1

P = P + 2dy - 2dx

y_{k }= y_{k }+ 1

Step 7: Plot ( x_{k }, y_{k })

Step 8: End

### Advantages of Bresenham's Algorithm

- It is faster because it does not involve floating-point calculations.
- It involves only integer arithmetic. Hence, it is easier to implement.

### Disadvantages of Bresenham's Algorithm

- It also does not provide smooth lines though accuracy has been improved.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions