Derivation of Mid Point Circle Algorithm.

Derivation:

                           Assume that a circle is passing through origin and it’s  radius is r . Then the equation of circle will be

                                               x2+y2=r2

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

                                       < 0 midpoint is inside.

F(Xmid,Ymid)  =           = 0 midpoint is on the circle.

                                       > 0 midpoint is outside.

F(Xmid,Ymid)  =  (X2k+1) + (Yk-1/2)2 – r2

F(Xmid,Ymid) =  (Xk+1)2 + (Yk-1/2)2 – r2

F(Xmid,Ymid)  =  X2k + 2Xk +1 + Y2k –Yk +1/4 -r2

Decision Parameter(Pk) = X2k +Y2k +2Xk –Yk +5/4 -r2

Initial Parameter(Po) = 02 + r2 + 0 – r + 5/4 - r2

                               Po  =  5/4 – r

Pk+1 = X2k+1 + Y2k+1 + 2Xk+1 – Yk+1 + 5/4 – r2

Pk+1 – Pk = (X2k+1 – X2k) + (Y2k+1 – Y2k) + 2(Xk+1-Xk) – (Yk+1-Yk)

Pk+1 = Pk + (X2k+1 – X2k) + (Y2k+1 – Y2k) + 2(Xk+1-Xk) – (Yk+1-Yk)

Pk+1 = Pk +(Xk+1 – Xk)(Xk+1 + Xk) +(Yk+1 + Yk)(Yk+1 – Yk) + 2(Xk+1-Xk) – (Yk+1-Yk) -------A

If P is negative (P<=0)

Xk+1 – Xk = 1

Yk+1 – Yk = 0

Put  these value in A 

Pk+1=Pk+Xk+1 + Xk +1+1

Pk+1 =  Pk + 2Xk+1 + 1

This is the decision parameter  for less than zero.

If P is positive (P>0)

Xk+1 – Xk = 1

Yk+1 – Yk = 0

Put  these value in A

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

 Pk+1 = Pk + 2Xk+1 – 1 -  (Yk+1 + Yk -1 +1) + 3

 Pk+1 = Pk + 2Xk+1 – 1 -  (2Yk+1 + 1) + 3

  Pk+1 = Pk + 2Xk+1 - 2Yk+1 + 1

This is the decision parameter for greater than zero.