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.

To study the PN junction diode characteristics under Forward bias conditions
To study the input and output characteristics of a BJT in Common Emitter configuration
Tutorial on Study Input Characteristics of Bipolar Transistor in CE mode
The Study of Optical Fibre and Digital Communication Trainer(OFT) and setting up a fibre optic analog link