Bresenham's Line Algorithm For Slope > 1

Previously, I discussed the basic idea of Bresenham’s Line Algorithm. As it had been discussed in the previous post that when slope of line > 1, the shadow of line falls more on y-axis and thus y-axis is the axis of maximum movement. So, when the line is plotted between 45° and 90° i.e. when slope > 1, the driving axis is Y-axis and thus we do sampling along it.

Mathematically, if ∆x = x2 − x1 and ∆y = y2 − y1 , we define the driving axis (DA) to be the x-axis if |∆x| ≥ |∆y|, and the y-axis if |∆y| > |∆x|. The DA is used as the “axis of control” for the algorithm and is the axis of maximum movement. Within the main loop of the algorithm, the coordinate corresponding to the DA is incremented by one unit. The coordinate corresponding to the other axis (usually denoted the passive axis or PA) is only incremented as needed.

I have already discussed Line Algorithm for slope < 1. When slope > 1, Y is sampled i.e incremented and X is evaluated.

yi+1= yi + 1 
xi+1 = xi , if d1<d2 

or

xi+1 = xi + 1, if d2 < d1 

where,

d1 = x -xi
d2= xi+1 - x,  as shown in the figure :

20141002_203250_2

Therefore,

d1-d2 = 2x - xi - xi+1 

Since,

xi+1 = xi + 1
∴ d1-d2 = 2x - xi - xi - 1
           = 2x - 2xi - 1

For each x,

yi+1 = mx + c
x = (yi+1-c)/m 
∴ d1-d2 = 2((yi+1-c)/m) - 2xi - 1
             = 2((yi + 1 -c )/m ) - 2xi - 1
             = 2yi/m + 2/m -c/m - 2xi -  1
             = 2yi/m - 2xi + k 
              where k =  2/m - c/m - 1 

Replace m = dy/dx & multiply by dy
We get,

dy(d1-d2) = 2yidx - 2xidy + kdy 

For slope > 1, dy is always positive and hence the sign of dy(d1-d2) is same as d1-d2 which determines the pixel position for i+1th pixel

∴ Decision variable is taken as Pi = dy(d1-d2)

Pi = 2yidx - 2xidy + kdy

Similarly, decision variable for i+1th pixel is :

Pi+1 = 2yi+1dx - 2xi+1dy + kdy

Subtracting Pi+1 and Pi, we get :

Pi+1 - Pi = 2dx(yi+1 - yi) - 2dy(xi+1 -xi )
Pi+1 = Pi + 2dx - 2dy(xi+1 - xi) 

Decision variable for the initial pixel, say (x0, y0)

P = 2y0dx - 2x0dy + kdy
       = 2y0dx - 2dy( y0 - c )/m + (2/m - 2c/m - 1)dy
       = 2dx - dy

Now, if P < 0 ( i.e. d1-d2 < 0 ), then

xi+1 = xi

∴ Pi+1 = Pi + 2dx 

if P > 0 ( i.e. d1-d2 > 0 ), then

Pi+1 = Pi + 2dx - 2dy

Summarizing the steps

  1. Input the 2 line end points and store the left end point as (x0, y0). We assume the left point as starting point because we have assumed positive slope.
  2. Plot the first point (x0, y0).
  3. Calculate constants dx, dy, 2dx, 2dy, 2dx-dy and obtain the starting value for decision variable as P = 2dx-dy.
  4. At each yi along the line starting at i = 0, perform the following test :

    If Pi < 0, the next point to plot is :

          ( xi , yi+1 )  &  Pi+1 = Pi + 2dx

    otherwise, the next point to plot is :

          ( xi+1 , yi+1)  &  Pi+1 = Pi + 2dx – 2dy

  5. Repeat step 4 dy times.

One thought on “Bresenham's Line Algorithm For Slope > 1

Leave a Reply

Your email address will not be published. Required fields are marked *

%d bloggers like this: