**Midpoint Circle Algorithm:**

A circle is defined as a set of points that are all at a given distance (x

*r*from a center positioned at._{c},y

_{c).}

This is represented mathematically by the equation

Using equation (1) we can calculate the value of y for each given value of x as

---------------- (2)

---------------- (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.

Thus f(x,y)=0 represents the equation of a circle.

In Midpoint Circle Algorithm, the decision parameter at the

*k*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.^{th}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 have just plotted the X X X

*k*^{th}^{ }pixel at (_{k},Y

_{k}), we next need to determine whether the pixel at the position (

_{k+1},Y

_{k}) or the one at (

_{k+1}, Y

_{k-1}) is closer to the circle.

Our decision parameter

*p*at the_{k}*k*step is the circle function evaluated at the midpoint of these two pixels.^{th}The coordinates of the X

**midpoint**of these two pixels are (_{k}+1, Y

_{k}-1/2).

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+1*step, in the following manner.^{th}Using Equ. (4), at the k

*+1*step, we have:^{th }Now if P Y

_{k }<=0, then the midpoint of the two possible pixels lies within the circle, thus north pixel is nearer to the theoretical circle. Hence,

_{k+1}= Y

_{k }. Substituting this value of in Equ. (6), we have

If p

_{k > }0 then the midpoint of the two possible pixels lies outside the circle, thus south pixel is nearer to the theoretical circle. Hence, Y

_{k+1}= Y

_{k}-1. Substituting this value of in Equ. (6), we have

For integer values of pixel coordinates, we can approximate P

_{0}=1-r,

Thus we have:

**Drawing the circle:**

We can reduce our calculation drastically (8

^{th}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)

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); // Prototype

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); // Function to plots the points

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);

}

Thanks for the explanation.

ReplyDeleteThanks for the appreciation.

ReplyDeleteWell explained, thanks.

ReplyDeleteawesome buddy

ReplyDeleteGreat Job,Perfect Way Of Explaining.......

ReplyDeletethanks a lot - tharindu

ReplyDeletethanks for the explanation n algorithm

ReplyDeletei get an error when i run the algorithm in c++with dos box.the error is....

BGI ERROR:graphics not initialized

(use 'initgraph')

give path of bgi folder as 3rd argument of initgraph function

DeleteThanx buddy

ReplyDeleteCan you give and explain algorithm for anti aliased circle algorithm

ReplyDeleteVery good Explanation

ReplyDeletethanks... its worthfull.

ReplyDeleteVery well explained thanks!

ReplyDeletethan ku

ReplyDeletewhoa, thx dude.

ReplyDeleteWell explained.. Thnkx :)

ReplyDeletetnx a lot

ReplyDeletewhy P0=1-r..??

ReplyDeletep0= 5/4-r ~ 1-r

DeleteIt is very helpful... Thanks :)

ReplyDeletevery helpful

ReplyDeleteCan yu pls tel me what is the use of p(decision parameter in program?why we are calculating it?

ReplyDeletewell explained.....thank you.

ReplyDelete