Numerical Examples of Bresenham’s Line Algo

Using Bresenham’s algorithm, generate the coordinates of the pixels that lie on a line segment having the endpoints (2, 3) and (5, 8).

Case: When slope (m) > 1

Now let’s solve the same numerical using BLA Algorithm.

S-1:  x1=2; y1=3; x2=5; y2=8.

S-2: dy=y2-y1 8-3= 5 and dx = x2-x1 = 5-2 = 3

 dy-dx = 5-3 = 2; and 2 * dy = 10; m(slope) = dy/dx => 5/3

Slope is more than 1 so we will follow the following method. 

S-3:  Calculate d = 2*dx-dy , so d=2*3 – 5 = 1. 

S-4: Always remember the rule for any line algorithm, If m is less than 1 then always increment x and calculate y. If m is more than 1 then do opposite , which is, always increment y and calculate x.

In this case, we will increase y by 1 every step as m (Slope) is more than 1 and calculate y as follows.

a) If d >=0 then x1 = x1 + 1 and y1 = y1 +1 with  new d = d + 2*(dx-dy)

b) If d<0 then x1 = x1 (remains same) and y1=y1+1  with new d = d + 2*dx

Note: y is always increasing ->Why?, its becasue for m>1, always increase y.

Draw a line from (1,1) to (8,7) using Bresenham’s Line Algorithm.

Case - When Slope (m) <1

Now let’s solve the same numerical using BLA Algorithm.

S-1:  x1=1; y1=1; x2=8; y2=7.

S-2: dy=7-1 = 6 and dx = 8-1 = 7

 dy-dx = 6-7 = -1; and 2 * dy = 12;

S-3: Calculate d = 2*dy-dx , so d=2*6 – 7 = 5 (Note the change here for m<1)

S-4: We will increase x by 1 every step as m is less than 1 and calculate y as follows 

Rule: If slope (m) is less than 1 (m<1) then always increase x and calculate y.

a) If d >=0 then x1 = x1 + 1 and y1 = y1 + 1 with new d = d + 2*(dy-dx)

b) If d<0 then x1 = x1 + 1 and y1 will not change with new d = d + 2*dy