MidPoint Circle Drawing Algorithm
We need to plot the perimeter points of a circle whose center coordinates and radius are given using the MidPoint Circle Drawing Algorithm.
We use the above algorithm to calculate all the perimeter points of the circle in the first octant and then print them along with their mirror points in the other octants. This will work only because a circle is symmetric about it’s centre.
The algorithm is very similar to the MidPoint Line Generation Algorithm. Here, only the boundary condition is different.
For any given pixel (x, y), the next pixel to be plotted is either (x, y+1) or (x1, y+1). This can be decided by following the steps below.
 Find the midpoint p of the two possible pixels i.e (x0.5, y+1)
 If p lies inside or on the circle perimeter, we plot the pixel (x, y+1), otherwise if it’s outside we plot the pixel (x1, y+1)
Boundary Condition : Whether the midpoint lies inside or outside the circle can be decided by using the formula:
In our program we denote F(p) with P. The value of P is calculated at the midpoint of the two contending pixels i.e. (x0.5, y+1). Each pixel is described with a subscript k.
The first point to be plotted is (r, 0) on the xaxis. The initial value of P is calculated as follows:
Examples:
Input : Centre > (0, 0), Radius > 3 Output : (3, 0) (3, 0) (0, 3) (0, 3) (3, 1) (3, 1) (3, 1) (3, 1) (1, 3) (1, 3) (1, 3) (1, 3) (2, 2) (2, 2) (2, 2) (2, 2)
Input : Centre > (4, 4), Radius > 2 Output : (6, 4) (6, 4) (4, 6) (4, 6) (6, 5) (2, 5) (6, 3) (2, 3) (5, 6) (3, 6) (5, 2) (3, 2)
 C

// C program for implementing
// MidPoint Circle Drawing Algorithm
#include<stdio.h>
// Implementing MidPoint Circle Drawing Algorithm
void
midPointCircleDraw(
int
x_centre,
int
y_centre,
int
r)
{
int
x = r, y = 0;
// Printing the initial point on the axes
// after translation
printf
(
"(%d, %d) "
, x + x_centre, y + y_centre);
// When radius is zero only a single
// point will be printed
if
(r > 0)
{
printf
(
"(%d, %d) "
, x + x_centre, y + y_centre);
printf
(
"(%d, %d) "
, y + y_centre, x + x_centre);
printf
(
"(%d, %d)\n"
, y + y_centre, x + x_centre);
}
// Initialising the value of P
int
P = 1  r;
while
(x > y)
{
y++;
// Midpoint is inside or on the perimeter
if
(P <= 0)
P = P + 2*y + 1;
// Midpoint is outside the perimeter
else
{
x;
P = P + 2*y  2*x + 1;
}
// All the perimeter points have already been printed
if
(x < y)
break
;
// Printing the generated point and its reflection
// in the other octants after translation
printf
(
"(%d, %d) "
, x + x_centre, y + y_centre);
printf
(
"(%d, %d) "
, x + x_centre, y + y_centre);
printf
(
"(%d, %d) "
, x + x_centre, y + y_centre);
printf
(
"(%d, %d)\n"
, x + x_centre, y + y_centre);
// If the generated point is on the line x = y then
// the perimeter points have already been printed
if
(x != y)
{
printf
(
"(%d, %d) "
, y + y_centre, x + x_centre);
printf
(
"(%d, %d) "
, y + y_centre, x + x_centre);
printf
(
"(%d, %d) "
, y + y_centre, x + x_centre);
printf
(
"(%d, %d)\n"
, y + y_centre, x + x_centre);
}
}
}
// Driver code
int
main()
{
// To draw a circle of radius 3 centred at (0, 0)
midPointCircleDraw(0, 0, 3);
return
0;
}
Output:
(3, 0) (3, 0) (0, 3) (0, 3) (3, 1) (3, 1) (3, 1) (3, 1) (1, 3) (1, 3) (1, 3) (1, 3) (2, 2) (2, 2) (2, 2) (2, 2) Disclaimer: This content belongs to geeksforgeeks, source: http://geeksforgeeks.org