Implement the midpoint circle generation algorithm to draw circle in C Language.

 

Midpoint Circle Generation Algorithm (Explanation and Implementation in C)

The Midpoint Circle Generation Algorithm is an efficient algorithm used in computer graphics to draw a circle using only integer arithmetic. This algorithm exploits the symmetry of circles to reduce the number of calculations needed. It calculates points in one octant and then reflects these points to draw the entire circle.

---

Concept and Explanation of Midpoint Circle Algorithm:

Given a center point $(xc,yc)\; and\; a\; radius$$r$, the goal is to draw a circle using pixel-based plotting. Since a circle is symmetric, it is enough to calculate points in one octant (the 45-degree segment of the circle) and then reflect these points to the other seven octants.

The algorithm calculates points along the circumference of the circle using a decision parameter $p$, which is updated incrementally based on whether the next pixel is closer to the ideal circle path.

---

Steps of the Midpoint Circle Algorithm:

1. Initialize the starting point:
   Start at $(x, y) = (0, r)$, where $r$ is the radius.

2. Calculate the initial decision parameter:
   The decision parameter $p$ is calculated as:

   $$p=1-r$$

3. Plot the initial point and reflect it to other octants:
   Plot $(x, y)$ and its reflections to the other seven octants.

4. Iterate while $x < y$:
   As you move from $x = 0$ towards $y$, check the value of $p$:

   • If $p < 0$, choose the next point as $(x+1, y)$ and update $p$ as:

     $$p=p+2x+1$$

   • If $p \geq 0$, choose the next point as $(x+1, y-1)$ and update $p$ as:

     $$p=p+2x-2y+1$$

5. Reflect the calculated points to other octants:
   Due to the symmetry of the circle, the points calculated in one octant are mirrored to the other seven octants.

6. Repeat until $x \geq y$:
   Stop when $x \geq y$, as this covers the full circle.

---

C Implementation of Midpoint Circle Algorithm:

#include <stdio.h>
#include <graphics.h>  // For using graphics functions (may require installation)

void plotCirclePoints(int xc, int yc, int x, int y) {
    // Plot points in all 8 octants
    putpixel(xc + x, yc + y, WHITE);
    putpixel(xc - x, yc + y, WHITE);
    putpixel(xc + x, yc - y, WHITE);
    putpixel(xc - x, yc - y, WHITE);
    putpixel(xc + y, yc + x, WHITE);
    putpixel(xc - y, yc + x, WHITE);
    putpixel(xc + y, yc - x, WHITE);
    putpixel(xc - y, yc - x, WHITE);
}

void midpointCircle(int xc, int yc, int r) {
    int x = 0, y = r;  // Starting point (0, r)
    int p = 1 - r;      // Initial decision parameter

    plotCirclePoints(xc, yc, x, y);  // Plot the initial points

    // Loop until x >= y
    while (x < y) {
        x++;  // Increment x at each step

        if (p < 0) {
            // Midpoint is inside the circle, choose (x+1, y)
            p = p + 2 * x + 1;
        } else {
            // Midpoint is outside or on the perimeter, choose (x+1, y-1)
            y--;
            p = p + 2 * x - 2 * y + 1;
        }

        plotCirclePoints(xc, yc, x, y);  // Plot the calculated points
    }
}

int main() {
    int xc, yc, r;

    printf("Enter the coordinates of the circle's center (xc, yc): ");
    scanf("%d %d", &xc, &yc);
    printf("Enter the radius of the circle: ");
    scanf("%d", &r);

    // Initialize the graphics mode
    int gd = DETECT, gm;
    initgraph(&gd, &gm, NULL);  // Start graphics mode (NULL uses default path)

    // Draw the circle using the Midpoint Circle Algorithm
    midpointCircle(xc, yc, r);

    getch();  // Wait for user input to view the output
    closegraph();  // Close the graphics window

    return 0;
}

---

Explanation of the Code:

1. Function plotCirclePoints:
   This function plots the points in all eight octants using the given center coordinates $(xc, yc)$ and the calculated offsets $(x, y)$.

   • The putpixel() function is used to light up individual pixels at the calculated positions.

2. Function midpointCircle:

   • The function calculates points on the circle using the midpoint circle algorithm.

   • It starts with $(x, y) = (0, r)$ and calculates the decision parameter $p = 1 - r$.

   • Based on the value of $p$, the function increments $x$ and either keeps $y$ the same (if $p < 0$) or decrements $y$ (if $p \geq 0$).

   • Each calculated point $(x, y)$is mirrored to all eight octants.

3. Main Function:

   • The user inputs the center coordinates $(xc, yc)$ and the radius $r$ of the circle.

   • Graphics mode is initialized using initgraph().

   • The midpointCircle() function is called to draw the circle.

   • The program waits for a keypress with getch() and then closes the graphics window with closegraph().

---

Sample Input and Output:

Sample Input:

mathematica
Enter the coordinates of the circle's center (xc, yc): 200 200  
Enter the radius of the circle: 100  

Output:
A circle with radius 100 will be drawn on the screen with center at $(200, 200)$.

---

Advantages of the Midpoint Circle Algorithm:

1. Efficiency:

   • Uses only integer arithmetic (no floating-point calculations), which is faster.

2. Symmetry Exploitation:

   • By calculating points in one octant and reflecting them, the algorithm minimizes the number of calculations.

3. Real-Time Application:

   • Due to its efficiency, the algorithm is well-suited for real-time applications in computer graphics.

---

Disadvantages:

1. Requires Graphics Library:

   • The code depends on a graphics library (e.g., <graphics.h>) for plotting pixels.

2. Limited to Circles:

   • The algorithm is specifically designed for drawing circles and does not generalize easily to other shapes.