The motivation of this algorithm is to utilize a parameter P_{K}, the sign of which will decide X or Y value for the next possible point. Consider Line Type IV, the next candidate points are (X_{K}+1, Y_{K}) or (X_{K}+1, Y_{K}+1). Let us assume the line intersect the X_{K}+1 line in Y which is in between of Y_{K }and Y_{K} + 1. So we can say the following:

Y = mX_{K+1} + c = m (X_{K}+1) + c (from the equation y=mx+c)

Consider the following equations

d_{1} = Y - Y_{K }= m (X_{K}+1) + c - Y_{K}

d_{2 }= Y_{K }+ 1 – Y = Y_{K }+ 1 - m (X_{K}+1) – c

So, d_{1 }- d_{2 }= 2m (X_{K}+1) - 2 Y_{K }+ 2c – 1 ... (1)

Now, if we go through the above diagrams, it is clearly shown that it d_{1} > d_{2}, then Y_{K}+1 will be selected, and if d_{2} > d_{1}, then Y_{K} will be selected.

Now let us consider

P_{K }

= d_{x} (d_{1}-d_{2}) // m = dx/dy

= d_{x }(2m (X_{K}+1) - 2 Y_{K }+ 2c – 1)

= 2d_{y}X_{K }– 2d_{x}Y_{K }+ C_{1 }where C_{1} = 2d_{x}c-d_{x}+2d_{y}

P_{K }= 2d_{y}X_{K }– 2d_{x}Y_{K }+ C_{1 }... (2)

Now if d_{x} > 0, then sign of P_{K} is dependent on (d_{1}-d_{2}). So if P_{K }is +ve then Y_{K}+1 will be selected, and if P_{K }is -ve, then Y_{K} will be selected.

P_{K }= 2d_{y}X_{K }– 2d_{x}Y_{K }+ C_{1 }... (2)

P_{K+1 }= 2d_{y}X_{K+1 }– 2d_{x}Y_{K+1 }+ C_{1 }... (3)

Performing, Eq.(3)-Eq.(2)

P_{K+1} - P_{K }= 2d_{y }(X_{K+1 }- X_{K}) – 2d_{x}(Y_{K+1} - Y_{K})

P_{K+1 }= P_{K} + 2d_{y }(X_{K+1 }- X_{K}) – 2d_{x}(Y_{K+1} - Y_{K})

P_{K+1 }= P_{K} + 2d_{y }– 2d_{x}(Y_{K+1} - Y_{K}) as X_{K+1 }= X_{K }+ 1

The value (Y_{K+1} - Y_{K }) may be 0 or may be 1 based on the next selected point.

For the initial point the value of P_{0 }= 2d_{y }- d_{x}

Now the trick is

If P_{K} > 0, next point is (X_{K}+1, Y_{K}+1) and P_{K+1 }= P_{K} + 2d_{y}

If P_{K} < 0, next point is (X_{K}+1, Y_{K}) and P_{K+1 }= P_{K} + 2d_{y }-2d_{x}

**Numeric Example:**

Draw a line with end points (4, 5) and (14, 9) applying Bresenham’s Line Drawing Algorithm.

dx = 14-4 = 10,

dy = 9-5 = 4,

2dy = 8,

2dx = 20

P_{0} = 2dy-dx = 2*4 – 10 = -2 which is negative

Calculation |
P_{k} |
X_{k+1} |
Y_{k+1} |
Comment |

4 | 5 | Initial X and Y | ||

2dy-dx = 8-10 | -2 | 5 | 5 | For -2 Y remain same |

-2+2dy = -2+8 | 6 | 6 | 6 | For 6 Y incremented |

6+2dy-2dx = 6+8-20 | -6 | 7 | 6 | For -6 Y remain same |

-6+2dy = -6+8 | 2 | 8 | 7 | For 2 Y incremented |

2+2dy-2dx = 2+8-20 | -10 | 9 | 7 | For -10 Y remain same |

-10+2dy = -10+8 | -2 | 10 | 7 | For -2 Y remain same |

-2+2dy = -2+8 | 6 | 11 | 8 | For 6 Y incremented |

6+2dy-2dx = 6+8-20 | -6 | 12 | 8 | For -6 Y remain same |

-6+2dy = -6+8 | 2 | 13 | 9 | For 2 Y incremented |

2+2dy-2dx = 2+8-20 | -10 | 14 | 9 | For -10 Y remain same |

**Algo : Bresenham |m|<1**

**Input :** x1, y1, x2, y2

**Variable Used :** dx, dy, P, x, y

**Steps :**-

dx=x2-x1, dy=y2-y1, P=2dy-dx, x=x1, y=y1

plot(x,y)

while(x!=x2 && y!=y2)

if(p<0)

x=x+1;

plot(x,y);

else if (p>0)

x=x+1;

y=y+1;

plot(x,y);

The above algorithm only demonstrates for the Line Type IV. For other line type we can calculate the points applying the same method.

**Follow us on ***Facebook_Page***, ***Youtube_Channel*** and Join us on ***Facebook_Group*

She is a co-founder of "Day On My Plate". Furthermore she is an academician in Dept. of Computer Science & Engineering. She likes to voyage all over the world in search of unrevealed experiences. She is passionate in reading novels and writing articles. Hope you all are enjoying her articles.