Bresenham’s Line Drawing Algorithm

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 = (xk, yk).

The next coordinates of a line = (xk + 1, yk + 1).

The intersection point between yk and yk + 1 = y.

Let we assume that the distance between y and yk = d1.

The distance between y and yk + 1 = d2.

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

If m < 1 then x = xk + 1 { Unit Interval}

y = yk + 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(xk + 1) +b …………. (1)

The value of

d1 = y – yk

Now we put the value of d1 in equation (1).

y = m (xk + 1) + b – yk

Now, we again put the value of y in the previous equation then we got,

d2 = yk + 1 – y

= yk + 1 – m (xk + 1) – b

Now, we calculate the difference between d1 – d2

If d1 < d2 Then yk + 1 = yk {we will choose the lower pixel as shown in figure}

If d1 => d2 Then yk + 1 = yk + 1 {we will choose the upper pixel as shown in figure}

Now, we calculate the values of d1 – d2

(d1 – d2)= m (xk+1) +b – yk – yk – 1 + m (xk+1) + b

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

(d1 – d2) = 2 m (xk+1) -2yk + 2b-1

We multiplied ▲x at both side then we got,

▲x (d1 – d2) = ▲x (2m (xk+1) -2yk + 2b-1)

We consider ▲x (d1 – d2) as a decision parameter (Pk), so

pk = ▲x (d1 – d2)

After calculation we got,

Pk = 2▲yxk + 2▲y – 2▲xyk +▲x (2b-1)

Then, the next coordinate of pk

pk+1 = 2▲yxk+1 + 2▲y – 2▲xyk+1 +▲x (2b-1)

Now, the difference between pk+1 – pk then,

pk+1 – pk = 2▲y (xk+1-xk) – 2▲x (yk+1-yk)

pk+1 = pk + 2▲y (xk+1-xk) – 2▲x (yk+1-yk) { Decision parameter coordinate }

Now, we put the value of xk+1 in above equation then we got,

pk+1 = pk + 2▲y – 2▲x (yk+1 – yk) { New decision parameter when m <1 }

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

pk + 1 = pk + 2▲y – 2▲x (xk + 1 – xk) { New decision parameter when m >1 }

If pk >= 0 { For coordinate y }

Then,

yk + 1 = yk + 1 { We will choose the nearest yk+1 pixel }

The next coordinate will be (xk+1, yk+1)

If pk < 0

Then,

yk+1 = yk { We will choose the nearest yk pixel }

The next coordinate will be (xk + 1, yk)

Similarly,

If pk >= 0 { For coordinate x }

Then,

xk + 1 = xk + 1 { We will choose the nearest xk+1 pixel }

The next coordinate will be (xk + 1, yk + 1)

If pk < 0

Then,

xk + 1 = xk { We will choose the nearest xk pixel }

The next coordinate will be (xk, yk + 1)

Algorithm of Bresenham’s Line Drawing Algorithm

Step 1: Start.
Step 2: Now, we consider Starting point as (x1, y1) and ending point (x2, y2).
Step 3: Now, we have to calculate ▲x and ▲y.
 ▲x = x2-x1
 ▲y = y2-y1
 m = ▲y/▲x 
Step 4: Now, we will calculate the decision parameter pk with following formula.
 pk = 2▲y-▲x
Step 5: The initial coordinates of the line are (xk, yk), and the next coordinates are (xk+1, yk+1). Now, we are going to 
calculate two cases for decision parameter pk
Case 1: If
 pk < 0
 Then
 pk+1 =pk +2▲y
 xk+1 = xk +1
 yk+1 = yk 
Case 2: If
 pk >= 0
 Then
 pk+1 =pk +2▲y-2▲x
 xk+1 =xk +1
 yk+1 =yk +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.