Mid-Point Circle Drawing Algorithm

link 0

We need to plot the perimeter points of a circle whose center co-ordinates and radius are given using the Mid-Point 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.

Circle raster points
Circle octants

The algorithm is very similar to the Mid-Point 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 (x-1, y+1). This can be decided by following the steps below.

  1. Find the mid-point p of the two possible pixels i.e (x-0.5, y+1)
  2. 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 (x-1, y+1)

Boundary Condition : Whether the mid-point lies inside or outside the circle can be decided by using the formula:-
Formula for circle boundary condition
example

In our program we denote F(p) with P. The value of P is calculated at the mid-point of the two contending pixels i.e. (x-0.5, y+1). Each pixel is described with a subscript k.
P Calculation2

The first point to be plotted is (r, 0) on the x-axis. The initial value of P is calculated as follows:-
P1 calculation2

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)
Example 1 explained
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 program for implementing
// Mid-Point Circle Drawing Algorithm
#include<stdio.h>
// Implementing Mid-Point 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++;
        
        // Mid-point is inside or on the perimeter
        if (P <= 0)
            P = P + 2*y + 1;
            
        // Mid-point 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

rakesh

Leave a Reply

Your email address will not be published. Required fields are marked *

Skip to toolbar