Header Ads Widget

MidPoint Circle Algorithm

It is based on the following function for testing the spatial relationship between the arbitrary point (x, y) and a circle of radius r centered at the origin:

MidPoint Circle Algorithm
MidPoint Circle Algorithm

Now, consider the coordinates of the point halfway between pixel T and pixel S

This is called midpoint (xi+1,yi-MidPoint Circle Algorithm) and we use it to define a decision parameter:

            Pi=f (xi+1,yi-MidPoint Circle Algorithm) = (xi+1)2+(yi-MidPoint Circle Algorithm)2-r2 ...............equation 2

If Pi is -ve ⟹midpoint is inside the circle and we choose pixel T

If Pi is+ve ⟹midpoint is outside the circle (or on the circle)and we choose pixel S.

The decision parameter for the next step is:

Pi+1=(xi+1+1)2+(yi+1-MidPoint Circle Algorithm)2- r2............equation 3

Since xi+1=xi+1, we have

MidPoint Circle Algorithm

If pixel T is choosen ⟹Pi<0

We have yi+1=yi

If pixel S is choosen ⟹Pi≥0

We have yi+1=yi-1

MidPoint Circle Algorithm

We can continue to simplify this in n terms of (xi,yi) and get

MidPoint Circle Algorithm

Now, initial value of Pi (0,r)from equation 2

MidPoint Circle Algorithm

We can put MidPoint Circle Algorithm≅1
∴r is an integer
So, P1=1-r

Algorithm:

Step1: Put x =0, y =r in equation 2
            We have p=1-r

Step2: Repeat steps while x ≤ y
            Plot (x, y)
            If (p<0)
Then set p = p + 2x + 3
Else
            p = p + 2(x-y)+5
            y =y - 1 (end if)
            x =x+1 (end loop)

Step3: End

Program to draw a circle using Midpoint Algorithm:

#include <graphics.h>  
#include <stdlib.h>  
#include <math.h>  
#include <stdio.h>  
#include <conio.h>  
#include <iostream.h>  
  
class bresen  
{  
    float x, y,a, b, r, p;  
    public:  
    void get ();  
    void cal ();  
};  
    void main ()  
    {  
    bresen b;  
    b.get ();  
    b.cal ();  
    getch ();  
   }  
    Void bresen :: get ()  
   {  
    cout<<"ENTER CENTER AND RADIUS";  
     cout<< "ENTER (a, b)";  
    cin>>a>>b;  
    cout<<"ENTER r";  
    cin>>r;  
}  
void bresen ::cal ()  
{  
    /* request auto detection */  
    int gdriver = DETECT,gmode, errorcode;  
    int midx, midy, i;  
    /* initialize graphics and local variables */  
    initgraph (&gdriver, &gmode, " ");  
    /* read result of initialization */  
    errorcode = graphresult ();  
    if (errorcode ! = grOK)    /*an error occurred */  
    {  
        printf("Graphics error: %s \n", grapherrormsg (errorcode);  
        printf ("Press any key to halt:");  
        getch ();  
        exit (1); /* terminate with an error code */  
    }  
    x=0;  
    y=r;  
    putpixel (a, b+r, RED);  
    putpixel (a, b-r, RED);  
    putpixel (a-r, b, RED);  
    putpixel (a+r, b, RED);  
    p=5/4)-r;  
    while (x<=y)  
    {  
        If (p<0)  
        p+= (4*x)+6;  
        else  
        {  
            p+=(2*(x-y))+5;  
            y--;  
        }  
        x++;  
        putpixel (a+x, b+y, RED);  
        putpixel (a-x, b+y, RED);  
        putpixel (a+x, b-y, RED);  
        putpixel (a+x, b-y, RED);  
        putpixel (a+x, b+y, RED);  
        putpixel (a+x, b-y, RED);  
        putpixel (a-x, b+y, RED);  
        putpixel (a-x, b-y, RED);  
    }  
}

  

Output:

MidPoint Circle Algorithm

Post a Comment

0 Comments