Midpoint Circle Algorithm & Integer Steps

High-Speed Curved Rasterization

While naive Cartesian and polar algorithms suffer from expensive square roots and trigonometric calls, the Midpoint Circle Algorithm (a specialized adaptation of Bresenham's raster formulation) renders circles using pure integer additions, subtractions, and bit shifts. By testing the position of the midpoint between candidate grid pixels relative to the implicit circle boundary, the algorithm decides pixel steps incrementally with mathematical precision. In this article, we rigorously derive the initial decision parameter, establish the recurrence formulas, and walk through a concrete numeric execution.

1. Implicit Circle Function & The Midpoint Test

Consider the implicit function for a circle of radius $r$ centered at $(0, 0)$:

F(x, y) = x^2 + y^2 - r^2

The value of $F(x, y)$ provides an exact spatial relationship for any point $(x, y)$:

$F(x, y) < 0$: The point lies strictly inside the circle boundary.
$F(x, y) = 0$: The point lies precisely on the circle boundary.
$F(x, y) > 0$: The point lies strictly outside the circle boundary.

In the second octant (from $x = 0$ to $x = y$, where the slope magnitude $|dy/dx| \le 1$), we initialize rasterization at $(0, r)$ and step $x$ incrementally by $+1$. Having plotted pixel $(x_k, y_k)$, the next candidate pixel is either:

East (E): $(x_k + 1, y_k)$
South-East (SE): $(x_k + 1, y_k - 1)$

The spatial midpoint $M$ between these candidate pixels is $M = (x_k + 1, y_k - \frac{1}{2})$. The decision parameter $P_k$ is defined by evaluating the implicit circle function at this midpoint:

P_k = F\left(x_k + 1, y_k - \frac{1}{2}\right) = (x_k + 1)^2 + \left(y_k - \frac{1}{2}\right)^2 - r^2

2. Derivation of the Decision Recurrence

At the subsequent step $k+1$, the decision parameter is:

P_{k+1} = F\left(x_{k+1} + 1, y_{k+1} - \frac{1}{2}\right) = ((x_k + 1) + 1)^2 + \left(y_{k+1} - \frac{1}{2}\right)^2 - r^2

Subtracting $P_k$ from $P_{k+1}$ gives the difference formula:

P_{k+1} = P_k + 2(x_k + 1) + 1 + \left(y_{k+1}^2 - y_k^2\right) - (y_{k+1} - y_k)

Case 1: $P_k < 0$ (Midpoint Inside)

The circle perimeter passes above the midpoint. Select pixel E $(x_k + 1, y_k)$. Since $y_{k+1} = y_k$:

P_{k+1} = P_k + 2x_{k+1} + 1

Case 2: $P_k \ge 0$ (Midpoint Outside)

The circle perimeter passes below the midpoint. Select pixel SE $(x_k + 1, y_k - 1)$. Since $y_{k+1} = y_k - 1$:

P_{k+1} = P_k + 2x_{k+1} + 1 - 2y_{k+1}

3. Initial Parameter $P_0$ & Integer Optimization

The circle begins at $(x_0, y_0) = (0, r)$. Evaluating $P_0$:

P_0 = F\left(1, r - \frac{1}{2}\right) = 1^2 + \left(r - \frac{1}{2}\right)^2 - r^2 = 1 + r^2 - r + \frac{1}{4} - r^2 = \frac{5}{4} - r

Because all pixel coordinates and the radius $r$ are strictly integers:

If $r$ is an integer, $\frac{5}{4} - r$ is negative whenever $1 - r < 0$.
We can round $\frac{5}{4}$ to $1$ with zero impact on integer sign decisions:
P_0 = 1 - r

4. Step-by-Step Numeric Execution ($r = 10$)

Step $k$	Decision $P_k$	Plotted $(x, y)$	$2x_{k+1}$	$2y_{k+1}$	Next $P_{k+1}$
0	-9 ($1 - 10$)	(0, 10)	2	20	-9 + 2(1) + 1 = -6
1	-6 (< 0)	(1, 10)	4	20	-6 + 2(2) + 1 = -1
2	-1 (< 0)	(2, 10)	6	20	-1 + 2(3) + 1 = +6
3	+6 (>= 0)	(3, 10)	8	18	6 + 2(4) + 1 - 2(9) = -3
4	-3 (< 0)	(4, 9)	10	18	-3 + 2(5) + 1 = +8
5	+8 (>= 0)	(5, 9)	12	16	8 + 2(6) + 1 - 2(8) = +5
6	+5 (>= 0)	(6, 8)	14	14	Loop terminates: $x \ge y$ ($7 \ge 7$)