Midpoint Circle Algorithm

The Midpoint Circle Algorithm is a computer graphics algorithm used to draw a circle on a raster display by determining the pixels that best approximate a circle with a given center (h, k) and radius r. It is an efficient algorithm that uses the midpoint between pixels to decide which pixels to illuminate, minimizing computational complexity. The algorithm leverages the symmetry of a circle to reduce calculations, plotting points in one octant and mirroring them to the other seven.

Key Concepts

1. Purpose: To plot pixels forming a circle on a discrete grid, given the center (h, k) and radius r.
2. Basis: Uses the midpoint of two possible pixels to decide which one is closer to the actual circle, based on the circle equation x2 + y2 = r2.
3. Symmetry: A circle has 8-way symmetry, so computing points in one octant (e.g., the second octant, where x increases and y decreases) allows mirroring to the other seven octants.
4. Efficiency: Avoids floating-point calculations and square root operations, using integer arithmetic for faster execution.

Steps of the Midpoint Circle Algorithm

1. Input: Center of the circle (h, k) and radius r.
2. Initialize:
   • Start with the initial point (x, y) = (0, r), relative to the center.
   • Set the initial decision parameter: p = 1 - r (derived from the circle equation).
3. Iterate:
   • For each step in the first octant (while x < y):
   • Plot the pixel at (x + h, y + k) and use 8-way symmetry to plot points in other octants:
     • (x + h, y + k), (-x + h, y + k), (x + h, -y + k), (-x + h, -y + k)
     • (y + h, x + k), (-y + h, x + k), (y + h, -x + k), (-y + h, -x + k)
   • Update the decision parameter p:
     • If p < 0: Choose the east pixel (x + 1, y), update p = p + 2x + 3.
     • If p ≥ 0: Choose the southeast pixel (x + 1, y - 1), update p = p + 2x - 2y + 5.
   • Increment x. If p ≥ 0, decrement y.
4. Termination: Stop when x ≥ y, as the algorithm has covered the first octant.

Example

Draw a circle with center (0, 0) and radius r = 5:

1. Initialize:
   • Start at (x, y) = (0, 5).
   • Initial decision parameter: p = 1 - r = 1 - 5 = -4.
2. Iteration:
   • Step 1: (x, y) = (0, 5), p = -4.
     • p < 0, choose east pixel: (x + 1, y) = (1, 5).
     • Update: p = -4 + 2 ⋅ 0 + 3 = -1.
     • Plot: (1, 5), (-1, 5), (1, -5), (-1, -5), (5, 1), (-5, 1), (5, -1), (-5, -1).
   • Step 2: (x, y) = (1, 5), p = -1.
     • p < 0, choose east pixel: (2, 5).
     • Update: p = -1 + 2 ⋅ 1 + 3 = 4.
     • Plot: (2, 5), (-2, 5), (2, -5), (-2, -5), (5, 2), (-5, 2), (5, -2), (-5, -2).
   • Step 3: (x, y) = (2, 5), p = 4.
     • p ≥ 0, choose southeast pixel: (3, 4).
     • Update: p = 4 + 2 ⋅ 2 - 2 ⋅ 5 + 5 = 4 + 4 - 10 + 5 = 3.
     • Plot: (3, 4), (-3, 4), (3, -4), (-3, -4), (4, 3), (-4, 3), (4, -3), (-4, -3).
   • Step 4: (x, y) = (3, 4), p = 3.
     • p ≥ 0, choose southeast pixel: (4, 3).
     • Update: p = 3 + 2 ⋅ 3 - 2 ⋅ 4 + 5 = 3 + 6 - 8 + 5 = 6.
     • Plot: (4, 3), (-4, 3), (4, -3), (-4, -3), (3, 4), (-3, 4), (3, -4), (-3, -4).
   • Step 5: (x, y) = (4, 3), x ≥ y, stop.
3. Output: Pixels plotted form an approximation of the circle.

Advantages of Midpoint Circle Algorithm

1. Efficiency: Uses integer arithmetic, avoiding costly floating-point operations.
2. Symmetry: Exploits 8-way symmetry to reduce calculations significantly.
3. Accuracy: Selects pixels closest to the true circle, producing a smooth appearance.
4. Simplicity: Easy to implement with minimal computational overhead.

Disadvantages of Midpoint Circle Algorithm

1. Limited to Circles: Only applicable for drawing circles, not other curves like ellipses.
2. Raster Artifacts: On low-resolution displays, the circle may appear jagged due to pixelation.
3. Complexity for Large Radii: Requires more iterations for larger circles, though still efficient.

Applications

• Used in computer graphics for rendering circles in 2D applications (e.g., games, CAD systems).
• Employed in digital plotters and printers for circular shapes.
• Foundational for drawing arcs and circular components in graphical user interfaces.

Comparison with Other Algorithms

• Vs. Bresenham’s Circle Algorithm: The Midpoint Circle Algorithm is essentially an optimized version of Bresenham’s algorithm, using the same principles but formalized with the midpoint approach.
• Vs. Direct Method: The direct method (using x2 + y2 = r2) is computationally expensive due to square root calculations, while the Midpoint algorithm is more efficient.

Pseudo-Code

void MidpointCircle(int h, int k, int r) {
    int x = 0, y = r;
    int p = 1 - r;
    while (x <= y) {
        plot(h + x, k + y); plot(h - x, k + y); plot(h + x, k - y); plot(h - x, k - y);
        plot(h + y, k + x); plot(h - y, k + x); plot(h + y, k - x); plot(h - y, k - x);
        x++;
        if (p < 0) {
            p = p + 2 * x + 3;
        } else {
            y--;
            p = p + 2 * x - 2 * y + 5;
        }
    }
}

Conclusion

The Midpoint Circle Algorithm is an efficient and widely used method for drawing circles on raster displays. Its use of integer arithmetic and symmetry makes it computationally efficient and accurate, making it ideal for computer graphics applications. Despite its limitation to circles, it remains a cornerstone algorithm in raster graphics.