Derivation of BRESENHAM’S Line Drawing Algorithm.

Assumption :

                          Y=mX+b

                          where b is the intercept cut by line at Y axis and m is the slope of line

                            (0 <= m < 1)

Derivation :

                                Initially we have plotted a point (Xk , Yk) and increase  X by 1 we come to Xk+1.

Decision Parameter(Pk)  - (Xk+1 , Yk+1) 

                                             - (Xk+1 , Yk)

D1 = Y – Yk

D1 = m(Xk+1)+b – Yk

D2 = Yk+1 – Y

D2 = Yk+1 – [m(Xk+1)+b]

D1-D2 = m(Xk+1) – Yk -  Yk+1 + m(Xk+1) + 2b

D1-D2 = 2m(Xk+1) + 2b – Yk – Yk+1

D1-D2 = 2mXk + 2m – 2Yk + (2b-1)

Put  m = dY/dX

(D1-D2)dX = 2Xk dY – 2Yk dX + 2dY + (2b-1)dX

 Pk = 2Xk dY – 2Yk dX + C

 Where C = 2dY + (2b-1)dX

 Pk+1 = 2Xk+1 dY – 2Yk+1 dX + C

 Pk+1-Pk = 2(Xk+1 - Xk)dY – 2(Yk+1 - Yk)dX

 Pk+1 = Pk + 2dY – 2(Yk+1 - Yk)dx    --------------------------    (A)

  If Pk is negative (Pk < 0)

  (D1-D2)dX < 0

   Xk+1 – Xk = 1

   Yk+1 – Yk = 0

   Put these value in A

Pk+1 = Pk +2dy

This is the decision parameter for less than zero.

If P is positive (P>=0)

(D1-D2)dx  >= 0

Xk+1 – Xk = 1

Yk+1 – Yk = 1

 put these value in A

 Pk+1 = Pk + 2(dY - dY)

This is the decision parameter  for greater than zero.

Initial value of decision parameter (Xo , Yo)

Po = 2Xo dY – 2Yo dX + 2dY + (2b-1)dX      --------------------------  (B)

Yo = mXo +b

Yo – mXo = b

Yo – dY/dX Xo = b

2Yo – 2Xo dY/dX = 2b

2Yo dx – 2Xo dY - dX = (2b-1)dX

Put the value of (2b-1)dX  in B

Po = 2Xo dY – 2Yo dX + 2dY + 2Yo dx – 2Xo dY – dX

Po = 2dY – dX

This is the initial decision parameter.