BRESENHAM'S LINE DRAWING ALGORITHM...

Bresenham’s Line Algorithm :

Ø  Read (Xa , Ya) and (Xb , Yb)

      dY = Yb – Ya

      dX = Xb – Xa

      P = 2dY – dX

      X = Xa, Y = Ya

Ø  While(X <= Xb)

      {

              plotpoint(X,Y)

              X++

              if(P<0)

              P=P + 2dY

              else

              {

                      Y++

                      P = P+2(dY - dX)

              }

         }

Ø     End

                  

DERIVATION OF BRESENHAM’S LINE AGORITHM..

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) – Y k -  Yk+1 + m(Xk+1) + 2b

D1-D2 = 2m(Xk+1) + 2b – Y k – 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 (P k < 0)

  (D1-D2)dX < 0

   Xk+1 – X k = 1

   Yk+1 – Y k = 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 – X k = 1

Yk+1 – Y k = 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.