Algorithm and Function of Mid Point Circle Algorithm.

Mid Point Circle Algorithm :

Begin:

   Read (Xc,Yc) and r

   P = 1 – r, x  = 0, y = r

   while(X<=Y)

      plot(X,Y)

      X = X+1

          If (p<=0)

         {

          P=P+2X-1

         }

          else

          {

                Y=Y-1

                P=P+2(X-Y)+1

          }

         end if

     end of while

  

End 

  

Function of Mid Point Circle :

 

void circlemidpoint(int xc,int yc,int r)

 {

      int x=0;

      int y=r;

      int p =1-r;

      point( xc, yc,x,y);

      while(x<y)

      {

            x++;

            if(p<0)

            p+=2*x+1;

           else

           {

                y--;

                p+=2*(x-y)+1;

           }

          point(xc,yc,x,y);

       }

}

void point(int xc,int yc,int x,int y)

 {

     putpixel(xc+x,yc+y,58);

     putpixel(xc+y,yc+x,58);

     putpixel(xc-y,yc+x,58);

     putpixel(xc-x,yc+y,58);

     putpixel(xc+x,yc-y,58);

     putpixel(xc-y,yc-x,58);

     putpixel(xc+y,yc-x,58);

     putpixel(xc-x,yc-y,58);

}

 

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.