Tutorials

Bresenhamís Line Drawing Algorithm

Papri Ghosh
23 Feb 2017
Read Time : 15 Minutes
Bresenhamís Line Drawing Algorithm

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

Y = mXK+1 + c = m (XK+1) + c (from the equation y=mx+c)

Consider the following equations

d1 = Y - YK = m (XK+1) + c - YK

d2 = YK + 1 – Y = YK + 1 - m (XK+1) – c

So, d1 - d2 = 2m (XK+1) - 2 YK + 2c – 1    ...    (1)

Now, if we go through the above diagrams, it is clearly shown that it d1 > d2, then YK+1 will be selected, and if d2 > d1, then YK will be selected.

Now let us consider 

PK

= dx (d1-d2)

= dx (2m (XK+1) - 2 YK + 2c – 1)

= 2dyXK – 2dxYK + C1 where C1 = 2dxc-dx+2dy

PK = 2dyXK – 2dxYK + C...  (2)

Now if dx > 0, then sign of PK is dependent on (d1-d2). So if PK is +ve then YK+1 will be selected, and if PK is -ve, then YK will be selected.

PK = 2dyXK – 2dxYK + C1   ...  (2)

PK+1 = 2dyXK+1 – 2dxYK+1 + C...  (3)

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

PK+1 - PK = 2dy (XK+1 - XK) – 2dx(YK+1 - YK)

PK+1  = PK + 2dy (XK+1 - XK) – 2dx(YK+1 - YK)

PK+1 = PK + 2dy – 2dx(YK+1 - YK) as XK+1 = XK + 1

The value (YK+1 - YK ) may be 0 or may be 1 based on the next selected point.

For the initial point the value of P0 = 2dy - dx

Now the trick is

If PK > 0, next point is (XK+1, YK+1) and PK+1 = PK + 2dy

If PK < 0, next point is (XK+1, YK) and PK+1 = PK + 2dy -2dx

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

P0 = 2dy-dx = 2*4 – 10 = -2 which is negative

Calculation

Pk

XK+1

YK+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

Authored By Papri Ghosh

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