The Midpoint Circle Algorithm

Bresenham's line algorithm draws a straight line on a pixel grid using only integer arithmetic, tracking an error term instead of a real-valued slope. The midpoint circle algorithm applies the same trick to circles: no floating point, no trigonometry, no square roots — just integer additions and a running decision variable.

The idea

A circle has a symmetry a line doesn't: reflecting a point across either axis, or swapping its x and y, gives another point on the same circle. So the algorithm only needs to compute the points for one 45° arc — say, from the top of the circle to the point where the arc crosses the diagonal — and can mirror each one into the other seven positions for free.

Along that one-eighth arc, x increases by exactly one pixel per step, same as the shallow-slope case in Bresenham's line algorithm, while y either stays the same or decreases by one. The question at each step is the same kind of question too: is the true circle closer to the current row or the one below it? The midpoint in the algorithm's name is the point exactly between those two candidate pixels — checking which side of the true circle that midpoint falls on decides which pixel to pick, and that check can be expressed with an integer decision variable d that only ever needs +, -, and comparisons against zero to update.

Implementation

#include "plot.hpp"

void plot_circle_points(int cx, int cy, int x, int y) {
    PlotPixel(cx + x, cy + y);
    PlotPixel(cx - x, cy + y);
    PlotPixel(cx + x, cy - y);
    PlotPixel(cx - x, cy - y);
    PlotPixel(cx + y, cy + x);
    PlotPixel(cx - y, cy + x);
    PlotPixel(cx + y, cy - x);
    PlotPixel(cx - y, cy - x);
}

void midpoint_circle(int cx, int cy, int r) {
    int x = 0;
    int y = r;
    int d = 1 - r;

    while (x <= y) {
        plot_circle_points(cx, cy, x, y);
        x++;
        if (d < 0) {
            d += 2 * x + 1;
        } else {
            y--;
            d += 2 * x - 2 * y + 1;
        }
    }
}

void frame() {
    PlotBackground(250, 250, 250);
    PlotColor(30, 100, 200);
    midpoint_circle(320, 240, 180);
}

plot_circle_points is the eightfold mirroring: given one point (x, y) relative to the center, it plots all eight symmetric positions at once. midpoint_circle is the loop that walks the one-eighth arc — d starts at 1 - r (the midpoint test for the very first step) and gets updated by either 2x + 1 or 2x - 2y + 1 depending on whether the midpoint fell inside or outside the true circle, exactly mirroring how Bresenham's line algorithm updates its error term by 2*dy or 2*dy - 2*dx. Edit the radius or center in the code above and press "Compile & Run" to see a different circle.

Walking through an example

For a circle of radius 5 centered at the origin, the loop starts at x = 0, y = 5, d = 1 - 5 = -4:

The one-eighth arc is (0,5) (1,5) (2,5) (3,4), ending right at the diagonal where x catches up to y. Mirroring those four points into all eight octants — swapping x/y and flipping signs — produces the full circle outline (with a couple of pixels landing on top of each other right at the axis crossings, where a mirrored point coincides with the original), all from four midpoint tests.

Why the same trick works twice

Both Bresenham's line algorithm and the midpoint circle algorithm reduce a real-valued question — "which pixel is the curve actually closest to?" — to the sign of an integer expression that can be updated incrementally instead of recomputed from scratch at every step. The line algorithm gets away with tracking one error term because a line has one slope for its entire length; the circle algorithm needs the eightfold symmetry on top, because a circle's slope keeps changing, but each of the eight mirrored octants shares the same shallow, monotonic shape that makes a single incrementally-updated decision variable enough.

The same midpoint idea extends further still — ellipses need two decision regions instead of one (the slope crosses the shallow/steep boundary at a different point than a circle's), but the underlying technique of comparing a real curve against an integer midpoint carries over directly.

Conclusion

Where Bresenham's algorithm turns "which row is closest" into one running comparison, the midpoint circle algorithm turns "which row is closest, on one-eighth of a circle" into the same kind of comparison, and then lets symmetry do the rest of the work for free. It's a good example of how far a little bit of geometry can stretch a technique originally built for a much simpler shape.