Circle Drawing Algorithms
Drawing a circle efficiently is important in graphics. The standard approach exploits the eight-way symmetry of circles to reduce computation.
Circle Equation
Standard form:
(x - cx)² + (y - cy)² = r²
Parametric form:
x = cx + r * cos(θ)
y = cy + r * sin(θ)
Where:
(cx, cy) = center
r = radius
θ = angle (0 to 2π)Eight-Way Symmetry
A circle centered at the origin is symmetric about both axes and both diagonals. Computing one octant gives us 8 pixels at once.
Symmetry of a circle:
| (x,y)
* | *
* | *
* | *
*---------+---------*
* | *
* | *
* | *
If (x, y) is on the circle:
( x, y), (-x, y), ( x, -y), (-x, -y)
( y, x), (-y, x), ( y, -x), (-y, -x)Midpoint Circle Algorithm
Similar to Bresenham's line algorithm, it uses a decision parameter to determine which pixel to plot. It only increments one coordinate and uses a decision variable.
Midpoint Circle Algorithm:
Input: center (cx, cy), radius r
x = 0
y = r
p = 1 - r (initial decision parameter)
while x ≤ y:
plot 8 symmetric points (cx±x, cy±y), (cx±y, cy±x)
if p < 0:
p = p + 2*x + 3
else:
y = y - 1
p = p + 2*(x - y) + 5
x = x + 1
Decision parameter:
p < 0 → choose E (x+1, y)
p ≥ 0 → choose SE (x+1, y-1)Bresenham's Circle Algorithm
An equivalent algorithm using a slightly different decision parameter formulation. Both algorithms produce the same pixel selections with integer-only arithmetic.
Bresenham's Circle:
d = 3 - 2*r
while x ≤ y:
plot 8 points
if d < 0:
d = d + 4*x + 6
else:
y = y - 1
d = d + 4*(x - y) + 10
x = x + 1