# Bresenham’s Line Drawing Algorithm in Computer Graphics

This algorithm was introduced by **“Jack Elton Bresenham” **in** 1962. **This algorithm helps us to perform scan conversion of a line. It is a powerful, useful, and accurate method. We use incremental integer calculations to draw a line. The integer calculations include addition, subtraction, and multiplication.

In **Bresenham’s Line Drawing algorithm**, we have to calculate the slope (**m**) between the starting point and the ending point.

As shown in the above figure
let, we have initial coordinates of a line = (**x _{k}, y_{k})**

The next coordinates of a line** = (x _{k+1}, y_{k+1})**

The intersection point between **y**_{k} and **y _{k+1 }**=

**y**

Let we assume that the
distance between **y** and **y _{k }= d_{1}**

The distance between **y** and **y _{k+1 }= d_{2}**

Now, we have to decide which point is nearest to the intersection point.

If **m < 1 **

then **x**
= **x _{k}+1_{ }{** Unit
Interval

**}**

**y **= **y _{k}+1_{ }{** Unit Interval

**}**

As we know the equation of a line-

**y = mx +b**

Now we put the value of x into the line equation, then

**y = m(****x _{k}+1**

**) +b**

**…………. (1)**

The value of **d _{1
}= y - y_{k }**

Now we put the value of **d _{1
}**in equation (1).

**y = m (****x _{k}+1**

**) +b -**

**y**

_{k}Now, we again put the value of **y **in the previous
equation then we got,

**d _{2 }= y_{k+1 }– y **

** = y _{k
}+ 1 – m (**

**x**

_{k}+1**) – b**

Now, we calculate the difference between **d _{1 }– d_{2}**

If **d _{1 }<
d_{2 }**

Then **y _{k+1} =
y_{k}**

**{**we will choose the lower pixel as shown in figure

**}**

If **d _{1 }=>
d_{2}**

Then **y _{k+1} =
y_{k}+1 {**we
will choose the upper pixel as shown in figure

**}**

Now, we calculate the
values of **d _{1 }- d_{2}**

**(d _{1 }- d_{2})=**

**m (**

**x**

_{k}+1**) +b -**

**y**-

_{k}**y**

_{k }- 1 + m (**x**

_{k}+1**) + b**

We simplified the above equation and replaced
the **m **with ?**y/**?**x.**

**(****d _{1 }- d_{2}**

**) = 2 m (x**

_{k+1}) -2y_{k }+ 2b-1We multiplied ?**x **at
both side then we got,

?**x (****d _{1 }- d_{2}**

**) =**?

**x (2m (x**

_{k+1}) -2y_{k }+ 2b-1)We consider ?**x (****d _{1 }- d_{2}**

**)**as a decision parameter

**(P**so

_{k}),**p _{k }= **?

**x (**

**d**

_{1 }- d_{2}**)**

After calculation we got,

**P _{k }= 2**?

**yx**?

_{k }+ 2**y - 2**?

**xy**?

_{k }+**x (2b-1)**

Then, the next coordinate
of** p _{k }**

**p _{k+1 }= 2**?

**yx**?

_{k+1 }+ 2**y - 2**?

**xy**?

_{k+1 }+**x (2b-1)**

Now, the difference between **p _{k+1 }–
p_{k }**then,

**p _{k+1 }– p_{k
}= 2**?

**y (x**?

_{k+1}-x_{k}) – 2**x (y**

_{k+1}-y_{k})**p _{k+1 }= p_{k
}+ 2**?

**y (x**?

_{k+1}-x_{k}) – 2**x (y**

_{k+1}-y_{k}) {Decision parameter coordinate}Now, we put the value of **x _{k+1
}**in above equation then we got,

**p _{k+1 }= p_{k }+ 2**?

**y – 2**?

**x (y**

_{k+1 }- y_{k})**{New decision parameter when m <1}**

Similarly, if **m >1**, the new decision
parameter for next coordinate will be

**p _{k+1 }= p_{k }+ 2**?

**y – 2**?

**x (x**

_{k+1 }- x_{k})**{New decision parameter when m >1}**

If **p _{k }>= 0 {For
coordinate y}**

Then,

**y _{k+1} = y_{k}+1 {We will choose
the nearest y_{k+1} pixel}**

The next coordinate will be **(x _{k}+1,
y_{k}+1)**

If **p _{k }< 0**

Then,

**y _{k+1} = y_{k }{We
will choose the nearest y_{k} pixel}**

The next coordinate will be **(x _{k}+1,
y_{k})**

Similarly,

If **p _{k }>= 0 {For
coordinate x}**

Then,

**x _{k+1} = x_{k}+1 {We will
choose the nearest x_{k+1} pixel}**

The next coordinate will be **(x _{k}+1,
y_{k}+1)**

If **p _{k }< 0**

Then,

**x _{k+1} = x_{k
}{We will choose the nearest x_{k} pixel}**

The next coordinate will be **(x _{k},
y_{k}+1)**

### Algorithm of Bresenham’s Line Drawing Algorithm

**Step 1: **Start.

**Step 2: **Now, we consider Starting point as **(x _{1}, y_{1}) **and endingpoint

**(x**

_{2}, y_{2}).**Step 3: **Now, we have to calculate **?x **and **?y.**

** ?x **= **x _{2}-x_{1}**

_{ }** ?y **= **y _{2}-y_{1}**

**m = ?y/?x **

**Step
4: **Now, we will calculate
the decision parameter **p _{k }**with following formula.

_{ }**p _{k}** =

**2**

**?y-?x**

**Step
5: **Theinitial
coordinates of the line are** (x _{k}, y_{k}), **and the next
coordinatesare

**(x**Now, we are going to calculate two cases for decision parameter

_{k+1}, y_{k+1}).**p**

_{k}_{ }**Case
1: **If

**p _{k
}< 0**

Then

**p _{k+1 }=p_{k }+2**

**?y**

** ****x _{k+1
}= x_{k }+1**

** ****y _{k+1
}= y_{k}**

_{ }**Case
2: **If

**p _{k
}>= 0**

Then

**p _{k+1 }=p_{k }+2**

**?y-2?x**

** ****x _{k+1
}=x_{k }+1**

** ****y _{k+1
}=y_{k}**

**+1**

_{ }**Step 6: **We will repeat step 5 until we found the ending point
of the line and the total number of iterations =**?x-1.**

**Step 7: **Stop.

**Example: **A line has a starting point (9,18) and ending point (14,22).
Apply the Bresenham’s Line Drawing algorithm to plot a line.

**Solution: **We have**
**two coordinates,

Starting Point = **(x _{1},
y_{1})** =

**(9,18)**

Ending Point = **(x _{2},
y_{2})** =

**(14,22)**

**Step 1: **First, we calculate **?x**,** ?y****.**

** ****?x = x _{2 }– x_{1 }= 14-9 = 5 **

** ?y**** = ****y _{2
}– y_{1 }= 22-18 = 4**

**Step 2: **Now, we are going to calculate the decision parameter **(p _{k})**

** p _{k }= **

**2**

**?y-?x**

** = 2 x 4 – 5 = 3**

The value of** p _{k }= 3**

**Step 3: **Now, we will check both the cases.

If

**p _{k
}>= 0**

Then

**Case 2 **is satisfied. Thus

** p _{k+1 }= p_{k }+2**

**?y-2?x**

**=3+**

_{ (}2 x 4)**- (2 x 5) = 1**

** ****x _{k+1
}=x_{k }+1 =**

**9 + 1 = 10**

** ****y _{k+1
}=y_{k}**

**+1**

**= 18 +1 = 19**

**Step 4:**** **Now move to next
step. We will calculate the coordinates until we reach the end point of the
line.

**?x -1 = 5 – 1 = 4**

p
_{k} |
p
_{k+1} |
x
_{k+1} |
y
_{k+1} |

9 | 18 | ||

3 | 1 | 10 | 19 |

1 | -1 | 11 | 20 |

-1 | 7 | 12 | 20 |

7 | 5 | 13 | 21 |

5 | 3 | 14 | 22 |

**Step 5: **Stop.

The Coordinates of drawn lines are-

**P _{1 }= (9,
18)**

**P _{2 }= (10,
19)**

**P _{3 }= (11,
20)**

**P _{4 }= (12,
20)**

**P _{5 }= (13,
21)**

**P _{6 }= (14,
22)**

### Advantages of Bresenham’s Line Drawing Algorithm

- It is simple to implement because it only contains integers.
- It is quick and incremental
- It is fast to apply but not faster than the Digital Differential Analyzer (DDA) algorithm.
- The pointing accuracy is higher than the DDA algorithm.

### Disadvantages of Bresenham’s Line Drawing Algorithm

- The
*Bresenham’s Line drawing algorithm*only helps to draw the basic line. - The resulted draw line is not smooth.

#### Related Posts:

- Bresenham’s Circle Drawing Algorithm in Computer Graphics
- Line Drawing Algorithm in Computer Graphics
- Mid-Point Line Drawing Algorithm in Computer Graphics
- Scan Conversion of a Circle Computer Graphics
- Midpoint Circle Drawing Algorithm in Computer Graphics
- Pointing and Positioning Technique Computer Graphics
- Line Clipping in Computer Graphics
- 3D Rotation in Computer Graphics
- Animation in Computer Graphics
- Image Representation in Computer Graphics