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:
Now, consider the coordinates of the point halfway between pixel T and pixel S
This is called midpoint (xi+1,yi-) and we use it to define a decision parameter:
Pi=f (xi+1,yi-) = (xi+1)2+(yi-)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-)2- r2............equation 3
Since xi+1=xi+1, we have
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
We can continue to simplify this in n terms of (xi,yi) and get
Now, initial value of Pi (0,r)from equation 2
We can put ≅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:
0 Comments