Goal

Scan-convert a circle of radius r centered at origin (later translated) using only integer arithmetic, exploiting 8-way symmetry.

8-Way Symmetry

For a pixel (x, y) on the circle, the points (+/-x, +/-y) and (+/-y, +/-x) are also on the circle. We compute one octant (from (0, r) clockwise to where x = y) and mirror it.

Decision Variable (Midpoint)

At step k we are at (x_k, y_k). Next candidates are E = (x_k+1, y_k) and SE = (x_k+1, y_k-1). The midpoint is M = (x_k+1, y_k - 0.5). The implicit circle function f(x, y) = x^2 + y^2 - r^2.

• If f(M) < 0, midpoint is inside circle -> choose E.
• If f(M) >= 0, midpoint is outside or on -> choose SE.

To stay integer, define p_k = f(M) and update incrementally:

• p_0 = 1 - r (after multiplying out and simplifying).
• If p_k < 0: p_(k+1) = p_k + 2*x_(k+1) + 1.
• Else: p_(k+1) = p_k + 2x_(k+1) + 1 - 2y_(k+1).

Worked Example, r = 10

Start (x, y) = (0, 10), p = 1 - 10 = -9. Plot 8 symmetric points each step.

Octant pixels: (0,10) (1,10) (2,10) (3,10) (4,9) (5,9) (6,8) (7,7). Mirror to fill the full circle.

Why Midpoint

Pure Bresenham circle uses a slightly different decision; the midpoint formulation is cleaner and generalizes to ellipses (two-region midpoint algorithm where the slope crosses 1).

Properties

• Integer-only arithmetic.
• At most 1 unit normal error.
• 8x speedup vs naive scan from symmetry.
• Easily extended to filled circle by drawing horizontal spans between symmetric pairs.