Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 50 ยท Line and Circle Algorithms

The Midpoint Circle Algorithm

Learn the midpoint circle algorithm: the circle equation, eight-way symmetry and the integer decision parameter, with a live circle plotter and worked example.

Circles are everywhere on screens: buttons, clocks, pie charts, wheels, dots on a scatter plot. Drawing one on a pixel grid raises the same question as drawing a line: which pixels best approximate a perfectly round curve? You could evaluate x = r * cos(t) and y = r * sin(t) for many angles, but trigonometry is expensive and you would still have to worry about gaps and duplicate pixels. Square roots have the same problems.

The midpoint circle algorithm (a close relative of Bresenham's line algorithm, sometimes called Bresenham's circle algorithm) draws a perfect pixel circle using only integer additions. It does two clever things. It computes just one eighth of the circle and gets the other seven by symmetry, and it chooses pixels with a tiny integer decision parameter, exactly like the line algorithm you saw in the previous lesson.

The circle equation

A circle of radius r centered at the origin contains every point (x, y) with:

TEXT
x^2 + y^2 = r^2

Define a function f(x, y) = x^2 + y^2 - r^2. It tells us where any point lies relative to the circle:

  • f < 0: the point is inside the circle.
  • f = 0: the point is on the circle.
  • f > 0: the point is outside the circle.

This inside/outside test is the heart of the method. Moving the circle to a center (cx, cy) just means adding cx and cy to every pixel we plot, so we derive everything for the origin.

Eight-way symmetry

A circle is extremely symmetric. If (x, y) is on it, then so are (-x, y), (x, -y), (-x, -y), and the same four with x and y swapped: (y, x), (-y, x), (y, -x), (-y, -x). That is eight points from a single computed one.

So we only need to compute the arc from the top of the circle (0, r) to the 45-degree point where x equals y. Everything else is a mirror image.

flowchart LR
  A["Compute one octant:<br/>from (0, r) to x = y"] --> B["For each point (x, y)<br/>plot 8 mirror points"]
  B --> C["Full circle"]

One octant of work, eight times the pixels.

Why stop at 45 degrees? In that octant the slope of the circle is between 0 and -1 (flat to diagonal), so x always increases by exactly 1 per step while y either stays or decreases by 1, which is the same two-candidate situation as Bresenham's line. Beyond 45 degrees the curve gets steep and the roles of x and y would swap, but symmetry hands us those pixels for free.

The decision parameter

Suppose we just plotted (x, y) in the first octant. The next pixel is in column x + 1, and there are two candidates:

  • E (east): (x + 1, y), staying at the same height;
  • SE (south-east): (x + 1, y - 1), one step down.

(Here "down" is toward the 45-degree point; on a screen with y pointing down, the picture is flipped but the algebra is the same.)

Look at the midpoint between the two candidates: M = (x + 1, y - 1/2). If M is inside the circle (f(M) < 0), the true arc passes below M, closer to the upper candidate E, so choose E. If M is outside (f(M) > 0), the arc passes above M, closer to SE, so choose SE. On the tie, either is acceptable; the usual convention is to pick SE.

flowchart TD
  P["Last pixel (x, y)"] --> M["Evaluate p = f(x + 1, y - 1/2)"]
  M --> Q{"p < 0 ?"}
  Q -->|"yes: midpoint inside"| E["Choose E: (x + 1, y)"]
  Q -->|"no: midpoint outside or on"| SE["Choose SE: (x + 1, y - 1)"]

The sign of p, the circle function at the midpoint, picks the next pixel.

Call the value at the midpoint p. Expanding the function:

TEXT
p = f(x + 1, y - 1/2) = (x + 1)^2 + (y - 1/2)^2 - r^2

We never want to recompute that, so we look at how p changes. Let x' be the new x (which is x + 1):

  • Choose E: p_new = p + 2x' + 1.
  • Choose SE (also y' = y - 1): p_new = p + 2x' + 1 - 2y', which is the same as p + 2(x' - y') + 1.

The starting point is (0, r). The first midpoint is (1, r - 1/2), so p0 = 1 + (r - 1/2)^2 - r^2 = 5/4 - r. Since r is an integer, we may round this to p0 = 1 - r: because p only changes by integers, only its sign matters and the fraction 1/4 never changes a sign. All values stay integers.

The complete algorithm:

  1. x = 0, y = r, p = 1 - r. Plot the 8 symmetric points of (x, y).
  2. While x < y: increase x; if p < 0 then p += 2x + 1, otherwise y -= 1 and p += 2(x - y) + 1; plot the 8 symmetric points of (x, y).

As code:

JavaScript
function midpointCircle(cx, cy, r) {
  const pixels = [];
  const plot8 = (x, y) => {
    pixels.push(
      [cx + x, cy + y], [cx - x, cy + y], [cx + x, cy - y], [cx - x, cy - y],
      [cx + y, cy + x], [cx - y, cy + x], [cx + y, cy - x], [cx - y, cy - x]
    );
  };

  let x = 0;
  let y = r;
  let p = 1 - r;
  plot8(x, y);
  while (x < y) {
    x++;
    if (p < 0) {
      p += 2 * x + 1;
    } else {
      y--;
      p += 2 * (x - y) + 1;
    }
    plot8(x, y);
  }
  return pixels;
}

Points on the axes and on the 45-degree diagonal are generated more than once: the very first call, plot8(0, r), produces only four distinct pixels, each twice. This does not matter for opaque drawing, but it matters if you draw with transparency or XOR, where you would plot a pixel twice and see a hole. Production code uses a set or skips the duplicate cases.

Worked example: radius 10

With r = 10: x = 0, y = 10, p = 1 - 10 = -9.

Step p used Decision New point (x, y) New p
start (0, 10) -9
1 -9 p < 0, E (1, 10) -9 + 2*1 + 1 = -6
2 -6 E (2, 10) -6 + 5 = -1
3 -1 E (3, 10) -1 + 7 = 6
4 6 p >= 0, SE (4, 9) 6 + 2*(4 - 9) + 1 = -3
5 -3 E (5, 9) -3 + 11 = 8
6 8 SE (6, 8) 8 + 2*(6 - 8) + 1 = 5
7 5 SE (7, 7) 5 + 2*(7 - 7) + 1 = 6

The loop ends because x reached y. Eight points were found, which expand to the full circle through symmetry.

Draw it yourself

The demo draws on a 40 by 24 pixel grid. Choose a center and radius; the first-octant pixels, the ones the algorithm computes, are orange, and the pixels produced by symmetry are blue. A thin red circle shows the exact mathematical circle for comparison. The list below lists the computed octant. If part of the circle falls outside the grid it is simply not drawn.

Midpoint circle on a pixel grid

The orange pixels trace the octant from the top of the circle toward the 45-degree point on the upper right. The mirrored blue pixels close the shape. Try radius 10 to compare with the worked table, and a small radius like 1 or 2 to see how coarse a pixel circle can be.

How accurate is it?

For each x, the ideal pixel in the first octant would be round(sqrt(r^2 - x^2)). The midpoint algorithm picks the pixel by comparing the midpoint with the arc, which is nearly the same decision. The console below checks every radius from 1 to 60 against that formula and lists the radii where a pixel differs. Those cases involve points where the true arc passes very close to a midpoint; the midpoint rule is consistent and self-contained, while the round(sqrt()) version needs a floating-point square root per pixel.

JS Midpoint versus round(sqrt)

Press Run (or Ctrl + Enter) to see the console output here.

No output.

You will see that the two methods agree almost everywhere. Only a couple of radii out of sixty show a one-pixel difference. Neither answer is wrong; they simply decide differently when the arc passes close to the halfway point between two pixels.

Limits and what comes next

The midpoint circle algorithm draws a one-pixel-wide circle outline. It does not do antialiasing (the staircase look is inherent), thick strokes, or ellipses. For ellipses the same midpoint idea applies but there are two regions with different steps, which is the subject of the next lesson. The staircase is addressed in Aliasing and Antialiasing.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does f(x, y) = x^2 + y^2 - r^2 tell us about a point?

    The sign of f compares the squared distance from the center with r^2, so it classifies a point relative to the circle.
  2. 2. Why does the algorithm compute only one octant?

    Reflections across both axes and the diagonal map one octant onto the whole circle, giving eight points per computed point.
  3. 3. For radius r = 5, what is the initial decision parameter p0 = 1 - r?

    p0 = 1 - 5 = -4.
  4. 4. In the loop, p is 3 and x has just become 6 while y is 8 before the decrement. What happens?

    p is not negative, so the midpoint is outside the circle and the SE pixel is chosen: y decreases to 7 and p += 2*(x - y) + 1 with the new y.

Summary

  • A circle at the origin satisfies x^2 + y^2 = r^2; the function f = x^2 + y^2 - r^2 is negative inside, zero on, and positive outside.
  • Eight-way symmetry means only the octant from (0, r) to x = y is computed; each point yields eight pixels.
  • The decision parameter p is f at the midpoint between the two candidate pixels. Start with p = 1 - r; if p < 0 add 2x + 1, else decrement y and add 2(x - y) + 1.
  • Only integer addition and subtraction are needed.
  • Axis and diagonal points are produced more than once, which matters for blending or XOR drawing.

Next: The Midpoint Ellipse Algorithm.