Circle drawing: DDA, Bresenham and midpoint algorithms
Clear, exam-focused notes on circle drawing algorithms: DDA (parametric), midpoint and Bresenham, with definitions, derivations, formulas, diagram instructions, two C++ programs (midpoint and Bresenham), worked steps, common mistakes and quick checks.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Drawing circles on a pixel grid is a basic graphics primitive used in GUIs, CAD, games and any system that rasterizes curves. Efficient circle algorithms let an engineer draw smooth circles using integer arithmetic, exploit symmetry to reduce computation, and avoid floating-point cost in real-time or embedded systems.
Key ideas
Define octant symmetry: because x^2 + y^2 is symmetric under swapping x and y and changing sign, one needs to compute only the first octant (0 <= x <= y) and mirror the plotted pixels into the other seven octants. Draw: Cartesian axes, circle centred at O, mark a point P in first octant with coordinates (x, y). Draw lines showing the 8 symmetric pixels produced from P. Label the 45 degree line (y = x).
Define the parametric (DDA) approach for circles: use the parametric equations x(θ) = r cos θ, y(θ) = r sin θ and step θ from 0 to 2π in small increments Δθ. A DDA (Digital Differential Analyzer) style incremental form uses the rotation relation for small Δθ:
- exact: [x_{k+1}; y_{k+1}] = [cos Δθ -sin Δθ; sin Δθ cos Δθ] [x_k; y_k]
- approximated (first order): x_{k+1} = x_k - y_k Δθ, y_{k+1} = y_k + x_k Δθ, valid when Δθ is small. Often choose Δθ ≈ 1/r so the spacing between adjacent points near the circle is about 1 pixel. The method uses floating-point arithmetic and rounding.
Define the midpoint circle algorithm: choose next pixel between East (E) with coordinates (x+1, y) and South-East (SE) with coordinates (x+1, y-1) by evaluating the circle function at the mid-point M = (x+1, y-1/2). If f(M) = (x+1)^2 + (y-1/2)^2 - r^2 < 0, choose E, else choose SE. This gives an integer decision parameter and incremental integer updates.
- Derivation: start with f(x, y) = x^2 + y^2 - r^2. For the mid-point M = (x+1, y-1/2) compute p = f(M). Simplify and derive recurrence for p_{k+1} when choosing E or SE. Universities typically ask you to show p0 = 1 - r when starting at (0, r), and to derive the update formulas.
- Stopping criterion: compute while x <= y (first octant), then mirror.
Define Bresenham's circle algorithm: an integer-only form equivalent to the midpoint algorithm obtained by multiplying the midpoint decision by 4 to remove the 1/2 fraction and simplifying constants. A common textbook form uses initial decision d = 3 - 2r and integer updates:
- if d <= 0: d = d + 4x + 6
- else: d = d + 4(x - y) + 10 and y = y - 1
- always increment x by 1 each step This algorithm uses only integer additions, subtractions and comparisons and is very efficient.
Practical points: use symmetry to emit eight points per calculated (x,y). For border cases (x=0, x=y) duplicates happen; handle or accept them. Use termination x > y to stop the first-octant loop. For a circle centered at (xc, yc), translate the symmetric points by adding offsets: plot (xc ± x, yc ± y) and (xc ± y, yc ± x).
Diagram to draw for exam answers: draw a small pixel grid, centre O, radius r, a sample pixel at (x, y) in first octant. Mark E at (x+1, y), SE at (x+1, y-1), and the midpoint M at (x+1, y-1/2). Label the decision f(M). Also draw the 45 degree line and indicate that the algorithm runs until x crosses y.
Formulas
circle equation: x^2 + y^2 = r^2 where x,y are coordinates in pixels, r in pixels. Applies to continuous circle.
parametric: x(θ) = r·cos θ y(θ) = r·sin θ θ in radians. Use to sample circle points.
DDA approx: x_{k+1} = x_k - y_k·Δθ y_{k+1} = y_k + x_k·Δθ where Δθ is small, unitless, and x,y in pixels. Applies when cos Δθ ≈ 1 and sin Δθ ≈ Δθ.
midpoint initial p0 = 1 - r where r is radius in pixels. Applies for starting point (x=0, y=r).
midpoint update when choosing E: p_{k+1} = p_k + 2x_k + 3 (x increments by 1)
midpoint update when choosing SE: p_{k+1} = p_k + 2(x_k - y_k) + 5 (x increments by 1, y decrements by 1)
Bresenham initial d0 = 3 - 2r where d is integer decision variable.
Bresenham update if d <= 0: d = d + 4x + 6 (x increments)
Bresenham update if d > 0: d = d + 4(x - y) + 10 (x increments, y decrements)
All coordinates are in pixels. These integer updates are algebraic rearrangements of the midpoint decision multiplied by 4.
Worked examples
Example 1: Midpoint algorithm, r = 3, centre (0,0). Show the step-by-step decision and final pixels in first octant, then list all symmetric pixels.
Steps (start x = 0, y = 3, p = 1 - r = -2):
- x=0, y=3, p=-2 < 0 -> choose E. New p = p + 2x + 3 = -2 + 0 + 3 = 1. x = 1, y = 3.
- x=1, y=3, p=1 >= 0 -> choose SE. New p = p + 2(x - y) + 5 = 1 + 2(1-3) + 5 = 2. x = 2, y = 2.
- x=2, y=2, p=2 >= 0 -> choose SE. New p = 2 + 2(2-2) + 5 = 7. x = 3, y = 1. Now x > y stop.
First-octant points produced: (0,3), (1,3), (2,2). Mirror to get full-circle integer pixels (unique): (-3,-1), (-3,0), (-3,1), (-2,-2), (-2,2), (-1,-3), (-1,3), (0,-3), (0,3), (1,-3), (1,3), (2,-2), (2,2), (3,-1), (3,0), (3,1).
Example 2: C++ program 1 - midpoint circle algorithm. This program reads xc, yc, r and outputs unique pixel centres for the full circle.
#include <bits/stdc++.h>
using namespace std;
int main() {
int xc, yc, r;
if (!(cin >> xc >> yc >> r)) return 0;
set<pair<int,int>> pixels;
int x = 0, y = r;
int p = 1 - r;
while (x <= y) {
pixels.insert({xc + x, yc + y});
pixels.insert({xc - x, yc + y});
pixels.insert({xc + x, yc - y});
pixels.insert({xc - x, yc - y});
pixels.insert({xc + y, yc + x});
pixels.insert({xc - y, yc + x});
pixels.insert({xc + y, yc - x});
pixels.insert({xc - y, yc - x});
if (p < 0) p = p + 2*x + 3;
else { p = p + 2*(x - y) + 5; y = y - 1; }
x = x + 1;
}
for (auto pr : pixels) cout << pr.first << ' ' << pr.second << endl;
return 0;
}
Sample input: 0 0 3
Exact output (lines may appear in ascending order because we used set; one possible exact order from a typical set iterator): -3 -1 -3 0 -3 1 -2 -2 -2 2 -1 -3 -1 3 0 -3 0 3 1 -3 1 3 2 -2 2 2 3 -1 3 0 3 1
Example 3: C++ program 2 - Bresenham circle algorithm (integer-only, equivalent results).
#include <bits/stdc++.h>
using namespace std;
int main() {
int xc, yc, r;
if (!(cin >> xc >> yc >> r)) return 0;
set<pair<int,int>> pixels;
int x = 0, y = r;
int d = 3 - 2*r;
while (x <= y) {
pixels.insert({xc + x, yc + y});
pixels.insert({xc - x, yc + y});
pixels.insert({xc + x, yc - y});
pixels.insert({xc - x, yc - y});
pixels.insert({xc + y, yc + x});
pixels.insert({xc - y, yc + x});
pixels.insert({xc + y, yc - x});
pixels.insert({xc - y, yc - x});
if (d <= 0) d = d + 4*x + 6;
else { d = d + 4*(x - y) + 10; y = y - 1; }
x = x + 1;
}
for (auto pr : pixels) cout << pr.first << ' ' << pr.second << endl;
return 0;
}
Sample input: 0 0 3
Exact output (same set as above): -3 -1 -3 0 -3 1 -2 -2 -2 2 -1 -3 -1 3 0 -3 0 3 1 -3 1 3 2 -2 2 2 3 -1 3 0 3 1
Note: The order of lines depends on the set iteration order; the content should match the listed points.
Common mistakes
- Using the wrong stopping condition: loop must run while x <= y for first octant. Using x < y or x < r leads to missing points or duplicates.
- Off-by-one updates in the recurrence constants (2x + 3 vs 2x + 1 etc). Check algebra carefully during derivation.
- Mixing floating-point DDA without rounding carefully causes gaps and asymmetric pixels.
- Forgetting special case when x == y or x == 0 which produces duplicate symmetric points; handle or accept duplicates.
For your exam
Typical question types: short definitions (pixel, octant, midpoint), derivation of midpoint decision parameter (step-by-step algebra), giving update recurrences, writing pseudocode/C++ for midpoint/Bresenham, numeric trace for a small radius, and diagram labeling E/SE and midpoint.
What full-marks answers include:
- Define all terms used in one line.
- Clear diagram showing centre O, sample point (x,y), E, SE, midpoint M and the 45 degree line.
- Derivation: start from f(x,y) = x^2 + y^2 - r^2, substitute M = (x+1, y-1/2), expand, simplify, show p0 = 1 - r and then derive the two update formulas and stopping criterion.
- Short correct pseudocode that uses symmetry and integer updates; mention complexity O(r) pixel decisions and constant-time per decision.
Quick check
- What is the mid-point M used to decide between E and SE when you are at pixel (x,y)?
- Give the initial midpoint decision parameter p0 when starting at (0, r).
- State the Bresenham initial decision value d0 when using integer updates.
Answers: M = (x + 1, y - 1/2). p0 = 1 - r. d0 = 3 - 2r.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?