DERIVATION OF BRESENHAM'S CIRCLE DRAWING...

DERIVATION :

                           Let us consider the circle at origin (0,0) i.e. x2 + y2 = r2 and (xk , yk) be  initial points.

F(x,y) = x2 + y2 – r2

F(N) = (xk + 1)2 + y2k – r2

F(S) = (xk + 1)2 + (yk - 1)2 – r2

Decision parameter (Pk) = F(N) + F(S)

Pk = 2( xk + 1 )2 + y2k + (yk - 1)2 – r2

Initial decision parameter (Po) = 2(1+0)2 + r2 + (r-1)2 – 2r2

Po = 3-2r 

Pk+1 = 2(xk + 2)2 + y2k+1 + (yk+1 -1)2 – 2r2

Pk+1 – Pk = 2[(xk+2)2 – (xk+1)2] + (y2k+1 – y2k) + (yk+1 -1)2 – (yk-1)2

Pk+1 = pk + 2(2xk+3) + [(yk+1 + yk)(yk+1 - yk)] + [(yk+1 + yk - 2)(yk +1 - yk)]-----------(A)

Case 1 :

 If P is negative

xk+1 – xk = 1

yk+1 – yk = 0

Put in (A)

Pk+1 = Pk + 2(2xk + 3)

Pk+1 = Pk + 4xk + 6

Case 2 :

If P is positive

xk+1 – xk = 1

yk+1 – yk = -1

Put in (A)

Pk+1 = Pk + 4xk+6 + (yk+1 +yk)(-1) + (yk+1 +yk -2)(-1)

Pk+1 = Pk + 4xk – 4yk + 10