Skip to content
Tutorials Center
My learning

Topics

Lesson 7 of 50 ยท Line and Circle Algorithms

The Midpoint Ellipse Algorithm

Learn how the midpoint ellipse algorithm plots an ellipse with only additions: two regions, decision parameters, four-way symmetry and a live pixel plot.

A circle has one radius, so the midpoint circle algorithm can exploit eight-way symmetry and only compute one octant. An ellipse has two radii, rx (horizontal) and ry (vertical), and that breaks the diagonal symmetry. Swapping x and y no longer maps the curve onto itself, because the ellipse is not the same shape when you rotate it by 90 degrees. What remains is four-way symmetry: reflecting across the horizontal axis, the vertical axis, or both.

So we compute one quadrant and mirror it. The extra difficulty is that, unlike the circle, one quadrant of an ellipse cannot be walked with a single rule. Near the top the curve is flat and we step in x. Near the right side it is steep and we must step in y. The midpoint ellipse algorithm handles this by splitting the quadrant into two regions and using a decision parameter in each.

The ellipse equation

For an ellipse centered at the origin with semi-axes rx and ry:

TEXT
x^2 / rx^2 + y^2 / ry^2 = 1

Multiplying both sides by rx^2 * ry^2 removes the fractions and gives an implicit function we can evaluate with integers:

TEXT
f(x, y) = ry^2 * x^2 + rx^2 * y^2 - rx^2 * ry^2

The sign of f tells us where a point is relative to the curve:

  • f(x, y) < 0: the point is inside the ellipse.
  • f(x, y) = 0: the point is exactly on the ellipse.
  • f(x, y) > 0: the point is outside.

This is the same trick the midpoint circle algorithm uses. We never solve for y. We only ask which side of the curve a candidate midpoint lies on. To draw an ellipse centered at (xc, yc) instead, compute everything around the origin and add xc and yc when plotting.

Four-way symmetry

If (x, y) is on the ellipse, so are (-x, y), (x, -y) and (-x, -y). So each computed point is plotted four times:

TEXT
plot(xc + x, yc + y)   plot(xc - x, yc + y)
plot(xc + x, yc - y)   plot(xc - x, yc - y)

Points with x = 0 or y = 0 are plotted twice at the same place, which is harmless.

Two regions

We start at the top of the ellipse, (0, ry), and walk clockwise toward the right end, (rx, 0). Along the way the slope of the curve changes from 0 (flat) to infinite (vertical). The boundary between the two regions is where the slope is exactly -1.

The slope of the curve is dy/dx = -(ry^2 * x) / (rx^2 * y). It equals -1 when ry^2 * x = rx^2 * y. Doubling both sides gives the form most code uses:

TEXT
Region 1 (slope magnitude < 1):   2 * ry^2 * x  <  2 * rx^2 * y
Region 2 (slope magnitude >= 1):  2 * ry^2 * x  >= 2 * rx^2 * y
  • In region 1 the curve is flat, so x is the fast axis. We step x by 1 every time and decide whether y stays or drops by 1.
  • In region 2 the curve is steep, so y is the fast axis. We step y down by 1 every time and decide whether x stays or grows by 1.
flowchart LR
  S["Start at (0, ry)"] --> R1["Region 1<br/>step x each time<br/>y stays or drops"]
  R1 -->|"2*ry^2*x >= 2*rx^2*y"| R2["Region 2<br/>step y each time<br/>x stays or grows"]
  R2 -->|"y reaches 0"| E["End at (rx, 0)<br/>mirror 4 ways"]

One quadrant is traced in two regions, then mirrored into the other three.

The decision parameter in region 1

Suppose we just plotted (x, y). The next x is x + 1, and the choice is between pixels (x + 1, y) and (x + 1, y - 1). The midpoint between them is (x + 1, y - 1/2). The decision parameter is the value of f at that midpoint:

TEXT
p1 = f(x + 1, y - 1/2)
   = ry^2 * (x + 1)^2 + rx^2 * (y - 1/2)^2 - rx^2 * ry^2
  • If p1 < 0, the midpoint is inside the ellipse, so the curve passes closer to the upper pixel: keep y.
  • Otherwise the midpoint is outside, so the lower pixel (x + 1, y - 1) is closer: decrease y.

Expanding the difference between consecutive parameters gives these incremental updates, where x and y are the values after the step has been taken (x already increased, y already decreased if it was):

TEXT
p1 < 0:   p1 += 2*ry^2*x + ry^2
p1 >= 0:  p1 += 2*ry^2*x - 2*rx^2*y + ry^2

The starting value at (0, ry) is:

TEXT
p1 = ry^2 - rx^2 * ry + rx^2 / 4

The rx^2 / 4 term is the only non-integer part. Real implementations either multiply every parameter by 4 to stay in integers or round it, because the sign of p1 hardly changes. We use floating-point numbers in the code below for readability. The point is that the loop needs only additions and one comparison per pixel.

The decision parameter in region 2

When the slope magnitude reaches 1 we switch. Now the next y is y - 1, and the choice is between (x, y - 1) and (x + 1, y - 1), with midpoint (x + 1/2, y - 1):

TEXT
p2 = f(x + 1/2, y - 1)
   = ry^2 * (x + 1/2)^2 + rx^2 * (y - 1)^2 - rx^2 * ry^2
  • If p2 > 0, the midpoint is outside, so the curve is closer to the left pixel: keep x.
  • Otherwise the curve is closer to the right pixel: increase x.

The first p2 is computed once from the last point of region 1, then updated incrementally. The loop ends when y goes below 0.

The full algorithm

Keeping the running values dx = 2*ry^2*x and dy = 2*rx^2*y means each update is just an addition:

JavaScript
function midpointEllipse(rx, ry, plot) {
  const rx2 = rx * rx, ry2 = ry * ry;
  let x = 0, y = ry;
  let dx = 2 * ry2 * x;          // grows by 2*ry2 per x step
  let dy = 2 * rx2 * y;          // shrinks by 2*rx2 per y step

  let p1 = ry2 - rx2 * ry + 0.25 * rx2;
  while (dx < dy) {              // region 1
    plot(x, y, 1);
    x++;
    dx += 2 * ry2;
    if (p1 < 0) {
      p1 += dx + ry2;
    } else {
      y--;
      dy -= 2 * rx2;
      p1 += dx - dy + ry2;
    }
  }

  let p2 = ry2 * (x + 0.5) ** 2 + rx2 * (y - 1) ** 2 - rx2 * ry2;
  while (y >= 0) {               // region 2
    plot(x, y, 2);
    y--;
    dy -= 2 * rx2;
    if (p2 > 0) {
      p2 += rx2 - dy;
    } else {
      x++;
      dx += 2 * ry2;
      p2 += dx - dy + rx2;
    }
  }
}

The plot callback receives the quadrant point and the region number. Your callback mirrors the point four ways. The next example does exactly that on a magnified pixel grid: blue pixels came from region 1, orange from region 2, and the thin line is the exact mathematical ellipse. Drag the sliders and watch where the colors change over.

Midpoint ellipse on a pixel grid

Set rx equal to ry and the ellipse becomes a circle: region 1 and region 2 meet at the 45-degree point, exactly where the circle algorithm would switch octants.

Tracing the decision parameters

It helps to watch the numbers once. This console example runs the algorithm on a small ellipse (rx = 8, ry = 6) and prints the pixel chosen at each step with the decision parameter that led to it. Notice that region 1 always increases x and region 2 always decreases y.

JS Decision parameter trace

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

No output.

Practical notes

  • Integers only. Multiply p1 and p2 by 4 (and adjust the constants) and every quantity stays an integer, so the whole loop runs without a floating-point unit. That mattered a great deal on early hardware.
  • Small and thin ellipses. When ry is tiny the first loop may run zero or one time. The second loop still draws the right end. Always test a 1-pixel-tall ellipse.
  • Rotated ellipses. The algorithm only draws axis-aligned ellipses. A tilted one is usually drawn by rotating a polygon approximation or by solving the general conic equation.
  • Filled ellipses. Plot horizontal spans between mirrored points instead of single pixels, or use scanline polygon filling on a polygon approximation.
  • Canvas. In real canvas code you would just call ctx.ellipse(...). The algorithm is how that call, in principle, reaches the screen when no GPU helps. The browser's actual rasterizer is more sophisticated and also antialiases, which is the next topic.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does the midpoint ellipse algorithm use two regions instead of one rule for the whole quadrant?

    Where the slope magnitude is below 1, x is the fast axis. After it passes 1, y is the fast axis. A single decision rule cannot step correctly in both situations.
  2. 2. How many symmetric copies of each computed point are plotted for an axis-aligned ellipse?

    An ellipse is symmetric about both axes, so each point is mirrored four ways. Eight-way symmetry would need rx = ry, which is a circle.
  3. 3. In region 1, what does a negative decision parameter p1 mean?

    f is negative inside the curve. A midpoint inside means the curve passes nearer the upper pixel, so y is kept.
  4. 4. Which condition marks the switch from region 1 to region 2?

    The slope dy/dx equals -1 where ry^2x = rx^2y. Past that point the curve is steeper than 45 degrees.
  5. 5. What happens if you pass rx equal to ry?

    With equal radii the ellipse equation is the circle equation, and the slope is -1 exactly at 45 degrees.

Summary

  • An ellipse has only four-way symmetry, so one quadrant is computed and mirrored.
  • The implicit function f(x, y) = ry^2*x^2 + rx^2*y^2 - rx^2*ry^2 is negative inside, zero on, and positive outside the curve.
  • Region 1 (slope magnitude below 1) steps x and decides about y; region 2 steps y and decides about x.
  • The regions meet where 2*ry^2*x >= 2*rx^2*y.
  • Decision parameters update incrementally with additions, and scaling by 4 makes them integers.
  • With rx = ry the algorithm draws a circle.

Next: Aliasing and Antialiasing.