www.knowledgepath.
in
Midpoint Circle Algorithm
A circle is defined as a set of points that are all at a given distance r from a
center positioned at. (xc, yc).
This is represented mathematically by the equation
------------- (1)
Using equation (1) we can calculate the value of y for each given value of x
as
---------------- (2)
Thus one could calculate different pairs by giving step increments to x and
calculating the corresponding value of y. But this approach involves
considerable computation at each step and also the resulting circle has its
pixels sparsely plotted for areas with higher values of the slope of the
curve.
Midpoint Circle Algorithm uses an alternative approach, wherein the pixel
positions along the circle are determined on the basis of incremental
calculations of a decision parameter.
Let
-------------- (3)
Thus f(x, y) = 0 represents the equation of a circle.
Further, we know from coordinate geometry, that for any point, the
following holds:
In Midpoint Circle Algorithm, the decision parameter at the kth step is the
circle function evaluated using the coordinates of the midpoint of the two
pixel centres which are the next possible pixel position to be plotted.
Let us assume that we are giving unit increments to x in the plotting
process and determining the y position using this algorithm. Assuming we
www.knowledgepath.in
have just plotted the kth
pixel at ( Xk, Yk), we next need to determine
whether the pixel at the position ( Xk+1,Yk ) or the one at ( Xk+1 , Yk-1) is
closer to the circle.
Our decision parameter pk at the kth step is the circle function evaluated at
the midpoint of these two pixels.
The coordinates of the midpoint of these two pixels are ( Xk+1, Yk-1/2).
Thus pk
--------------- (4)
Successive decision parameters are obtained using incremental
calculations, thus avoiding a lot of computation at each step. We obtain a
recursive expression for the next decision parameter i.e. at the k+1th step, in
the following manner.
Using eq. (4), at the k+1th step, we have:
Note : In general, it is true that: Xk+1 2 = (XK +1)2
Now if Pk <=0, then the midpoint of the two possible pixels lies within the
circle, thus north pixel is nearer to the theoretical circle. Hence, Yk+1= Yk .
Substituting this value of in Equ. (6), we have
www.knowledgepath.in
If pk > 0 then the midpoint of the two possible pixels lies outside the circle,
thus south pixel is nearer to the theoretical circle. Hence, Yk+1= Yk-1.
Substituting this value of in Equ. (6), we have
For the boundary condition, we have x=0, y=r. Substituting these values in
(4), we have
For integer values of pixel coordinates, we can approximate P0=1-r,
Thus we have:
Drawing the circle:
We can reduce our calculation drastically (8th fraction ) by making use of
the fact that a circle has 8 way symmetry. Thus after calculating a pixel
position (x,y) to be plotted, we get 7 other points on the circle
corresponding to it. These are:
(x,y); (x,-y); (-x,y); (-x,-y); (y,x); (y,-x); (-y,x); (-y,-x)
www.knowledgepath.in
The following code implements Mid Point Circle Algorithm in C++
# include <iostream.h>
# include <conio.h>
# include <graphics.h>
# include <math.h>
void MidPointCircleAlgo(int Radius,int xC,int yC);
void main()
{
int gDriver=DETECT, gMode;
initgraph(&gDriver,&gMode,"c:\\tc\\bgi");
int Radius, xC, yC;
cout<< endl << "Enter Center point coordinates...";
cout<<endl<<" Xc : ";
cin>>xC;
cout<<endl<<" Yc : ";
cin>>yC;
cout<<endl<<"Radius : ";
cin>>Radius;
cleardevice();
MidPointCircleAlgo(Radius,xC,yC);
getch();
}
void MidPointCircleAlgo(int Radius,int xC,int yC)
{
int P;
int x,y;
void Draw(int x,int y,int xC,int yC);
www.knowledgepath.in
P = 3 -2* Radius;
x = 0;
y = Radius;
Draw(x,y,xC,yC);
while (x<=y)
{
x++;
if (P<0)
{
P += 4 * x + 6;
}
else
{
P += 4 * (x - y) + 10;
y--;
}
Draw(x,y,xC,yC);
}
}
void Draw(int x,int y,int xC,int yC)
{
xC=320+xC;
yC=240-yC;
putpixel(xC + x,yC + y,1);
putpixel(xC + x,yC - y,1);
putpixel(xC - x,yC + y,1);
putpixel(xC - x,yC - y,1);
putpixel(xC + y,yC + x,1);
putpixel(xC - y,yC + x,1);
putpixel(xC + y,yC - x,1);
putpixel(xC - y,yC - x,1);
000.}
