Computer Graphics (rasterisation, ray tracing, WebGPU) Module 3 – Classic raster algorithms: lines, circles and fills

Midpoint circle and ellipse algorithms

How the midpoint test draws circles and ellipses with whole-number additions, eight-way symmetry without repeated pixels, and the ellipse's two regions.

Beginner
25 minutes
Examples run with Node.js 24.21.0 and quickjs 0.32.0
By MySmartCoPilot

Free: the whole lesson. With a pass: the model answers to its 2 interview questions.

What you will learn

Derive the midpoint circle algorithm's decision variable and its whole-number updates
Use eight-way symmetry to draw a whole circle from one octant without repeated or missing pixels
Derive the midpoint ellipse algorithm and switch from region 1 to region 2 at the right pixel
Draw filled discs and rings by testing pixel centres against the circle's equation

Before you start

Line drawing: DDA and Bresenham's algorithm

What you’ll learn · Before you start

What you will learn

Derive the midpoint circle algorithm's decision variable and its whole-number updates
Use eight-way symmetry to draw a whole circle from one octant without repeated or missing pixels
Derive the midpoint ellipse algorithm and switch from region 1 to region 2 at the right pixel
Draw filled discs and rings by testing pixel centres against the circle's equation

Before you start

Line drawing: DDA and Bresenham's algorithm

On this page

The outline of a circle of radius 8 is 44 pixels, and a program that found each one with a square root would compute a root for every column of every octant. The midpoint algorithms light the same pixels by testing the curve’s equation halfway between two candidate pixels, in whole-number arithmetic and with no root at all.

You will derive the circle’s decision variable from its equation, trace one octant of radius 8 decision by decision, and use symmetry to draw the other seven without lighting any pixel twice. Then you will split an ellipse into its two regions, repair the cases where its pixels go missing, and fill discs and rings by testing pixel centres, with every count taken from programs that run on this page.

A circle’s equation tells inside from outside

Take the circle of radius 8 around the pixel (0, 0). The point (6, 6) gives 6² + 6² − 8² = 8, while its neighbour (5, 6) gives 25 + 36 − 64 = −3, so the circle passes between them. That is the whole test: the implicit function: A function F(x, y) that is 0 on a curve, negative on one side of it and positive on the other, such as x² + y² − r² for a circle. Its sign tells which side a point lies on. F(x, y) = x² + y² − r² is negative inside the circle, 0 on it and positive outside, and computing it needs no square root.

The algorithm walks one octant, from (0, r) on the y axis to the 45° line. There the circle’s slope stays between 0 and −1, so as for a gentle line each column has exactly two candidates: straight on, (x + 1, y), and one row nearer the centre, (x + 1, y − 1). The midpoint test: Choosing between two candidate pixels by evaluating a curve's implicit function at the point halfway between their centres: the sign says which candidate the curve passes nearer. evaluates F halfway between their centres, at M = (x + 1, y − ½). If F(M) is below 0, M is inside, so the circle passes beyond it and the straight pixel is nearer; otherwise the diagonal pixel is. Here is the decision in column 5, with y growing downwards as in a framebuffer, so the centre lies above the drawing:

d is the circle's equation at the midpoint between two candidates

Text description of the diagram

A close-up of four pixels of the circle of radius 8 around (0, 0), with y growing downwards, so the centre is far above the drawing. Pixel (4, 7), bottom left, is lit: it has a thick outline and a dot at its centre. In the next column the two candidates have dashed outlines: (5, 7), straight on in the same row, and above it (5, 6), one row nearer the centre, the diagonal step. Pixel (4, 6) is not a candidate.

An arc of the circle rises from the lower left to the upper right. In column 5 it passes y = 6.24, drawn as a filled dot. An open circle marks the midpoint between the candidates, M = (5, 6.5).

The text under the drawing reads: F(M) = 5² + 6.5² − 8² = 3.25, which is more than 0, so M is outside the circle and the circle passes nearer (5, 6). With the quarter dropped, d = 3, which is not below 0, so the step is diagonal.

The loop has lit (4, 7). At x = 5 the circle passes y = 6.24, inside the midpoint (5, 6.5), and F(5, 6.5) = 3.25 is positive: the next pixel is (5, 6), one row nearer the centre. With y growing downwards that step goes up the screen, but the arithmetic is the same either way.

Checkpoint

Check: The midpoint test on the circle's equation

Question 1 of 2 For the circle of radius 8 around (0, 0), F(x, y) = x² + y² − 64. Where is the point (6, 6)?
Choose one answer.

On the circle, because 6 + 6 is close to 8 + 4 Inside the circle, because 6 is less than the radius 8 Outside the circle, because F(6, 6) = 72 − 64 = 8 is above 0 It cannot be told without a square root

Show the answer: Question 1 of 2

Answer: Outside the circle, because F(6, 6) = 72 − 64 = 8 is above 0

F(6, 6) = 36 + 36 − 64 = 8 > 0, so (6, 6) lies outside. Its neighbour (5, 6) gives 25 + 36 − 64 = −3 < 0, just inside: the circle passes between them.
Question 2 of 2 In the octant from (0, 8) to the 45° line, the loop has lit (2, 8). Which two pixels are the candidates for column 3, and which point does it test?
Choose one answer.

(2, 7) and (3, 7), and the midpoint (2.5, 7) (3, 8) and (3, 9), and the midpoint (3, 8.5) (3, 8) and (3, 7), and the midpoint (3, 7.5) between them All eight pixels around (2, 8)

Show the answer: Question 2 of 2

Answer: (3, 8) and (3, 7), and the midpoint (3, 7.5) between them

Between (0, r) and the 45° line the slope of the circle lies between 0 and −1, so as for a gentle line there are two candidates in each column, and F at the midpoint between them decides.

Whole-number updates trace one octant

Evaluating F from scratch would cost two multiplications a pixel. The decision variable: A whole number that a raster algorithm updates with additions and compares with 0 to choose between two candidate pixels, such as D in Bresenham's line algorithm. More in “Line drawing: DDA and Bresenham's algorithm” d follows F from one midpoint to the next instead. At the first midpoint, (1, r − ½), F equals 5/4 − r. After a straight step the next midpoint is one column on, and after a diagonal step one column on and one row in:

d \leftarrow d + 2x + 3 \ \text{(straight)} \qquad d \leftarrow d + 2(x - y) + 5 \ \text{(diagonal)}

In words: a straight step adds 2x + 3, a diagonal step adds 2(x − y) + 5, both computed with the x and y of the pixel just lit. For radius 8 the first update is 2 × 0 + 3 = 3. The quarter in 5/4 − r can be dropped: every midpoint’s y ends in .5, so F(M) is always a whole number plus exactly 1/4, and a whole-number d = F(M) − 1/4 is below 0 exactly when F(M) is. So d starts at 1 − r, every update is a whole number, and an exact tie can never happen, because F(M) is never 0 when the radius is a whole number.

Step through the octant of radius 8; each step names the midpoint, where the circle crosses that column, and the update:

Interactive · step by step The midpoint circle loop for one octant of radius 8 Step through the decisions from (0, 8). Each compares d with 0, lights the next pixel and updates d by a whole number.

The drawing shows the whole scene; its 7 steps are listed below.

Every step as text

Start. The octant starts on the y axis at (0, 8), which is lit at once. d is F at the first midpoint, (1, 7.5), with its 1/4 dropped: 1 − r = −7.
Column 1. d = −7 is less than 0: the midpoint (1, 7.5) is inside the circle, which passes y = 7.94 in column 1, so (1, 8) is nearer. d gains 2x + 3 = 3 and becomes −4.
Column 2. d = −4 is less than 0: the midpoint (2, 7.5) is inside the circle, which passes y = 7.75 in column 2, so (2, 8) is nearer. d gains 2x + 3 = 5 and becomes 1.
Column 3. d = 1 is not less than 0: the midpoint (3, 7.5) is outside the circle, which passes y = 7.42 in column 3, so (3, 7) is nearer. d gains 2(x − y) + 5 = −7 and becomes −6.
Column 4. d = −6 is less than 0: the midpoint (4, 6.5) is inside the circle, which passes y = 6.93 in column 4, so (4, 7) is nearer. d gains 2x + 3 = 9 and becomes 3.
Column 5. d = 3 is not less than 0: the midpoint (5, 6.5) is outside the circle, which passes y = 6.24 in column 5, so (5, 6) is nearer. d gains 2(x − y) + 5 = −1 and becomes 2.
Stop. From (5, 6), d = 2 sends the loop diagonally to (6, 5), but x = 6 is now past y = 5, so the loop stops. (6, 5) is the mirror image of (5, 6), and eight-way symmetry lights it with the rest of the circle: the octant has 6 pixels.

The program prints the same decisions and draws the whole circle from them:

The octant of radius 8, decision by decision, then the circle JavaScript · circle/midpoint_circle.mjs

// The midpoint circle algorithm: walk one octant from (0, r) towards the 45°
// line, and let a whole number d decide whether y steps towards the centre as
// x steps on.
//   d < 0:  the midpoint (x + 1, y - 1/2) is inside the circle: step straight, to (x + 1, y)
//   d >= 0: it is outside: step diagonally, to (x + 1, y - 1)

function octant(r, log = () => {}) {
  let x = 0;
  let y = r;
  let d = 1 - r; // F at the first midpoint is 5/4 - r; dropping the 1/4 never changes a decision
  const points = [];
  while (x <= y) {
    points.push([x, y]);
    const before = d;
    const straight = d < 0;
    if (straight) {
      d += 2 * x + 3;
    } else {
      d += 2 * (x - y) + 5;
      y -= 1;
    }
    x += 1;
    log({ from: points[points.length - 1], before, straight, to: [x, y], after: d });
  }
  return points;
}

const show = ([x, y]) => `(${x}, ${y})`;
const r = 8;
console.log(`Radius ${r}: d starts at 1 - r = ${1 - r}`);
console.log('pixel     d before  step        next     d after');
const pts = octant(r, (s) => {
  console.log(`${show(s.from).padEnd(10)}${String(s.before).padEnd(10)}${(s.straight ? 'straight' : 'diagonal').padEnd(12)}${show(s.to).padEnd(9)}${s.after}`);
});
console.log(`x > y now, so the octant ends: ${pts.map(show).join(' ')}`);

// Each octant point (x, y) stands for eight: (±x, ±y) and (±y, ±x).
const lit = new Set();
for (const [x, y] of pts) {
  for (const [a, b] of [[x, y], [y, x]]) {
    for (const [sa, sb] of [[1, 1], [-1, 1], [1, -1], [-1, -1]]) lit.add(`${sa * a},${sb * b}`);
  }
}
console.log(`${pts.length} octant points give ${lit.size} pixels (# lit, + the centre, y grows downwards):`);
for (let y = -r; y <= r; y++) {
  let row = '';
  for (let x = -r; x <= r; x++) row += lit.has(`${x},${y}`) ? '#' : x === 0 && y === 0 ? '+' : '.';
  console.log(row.split('').join(' '));
}

// A common slip: moving x and y first, then updating d with the new values.
// Each update then comes out 2 (straight) or 4 (diagonal) too large.
function slipped(r) {
  let x = 0;
  let y = r;
  let d = 1 - r;
  const points = [];
  while (x <= y) {
    points.push([x, y]);
    if (d < 0) {
      x += 1;
      d += 2 * x + 3;
    } else {
      x += 1;
      y -= 1;
      d += 2 * (x - y) + 5;
    }
  }
  return points;
}
console.log('');
console.log(`Updated after the move, the octant becomes ${slipped(r).map(show).join(' ')}`);

Output

Radius 8: d starts at 1 - r = -7
pixel     d before  step        next     d after
(0, 8)    -7        straight    (1, 8)   -4
(1, 8)    -4        straight    (2, 8)   1
(2, 8)    1         diagonal    (3, 7)   -6
(3, 7)    -6        straight    (4, 7)   3
(4, 7)    3         diagonal    (5, 6)   2
(5, 6)    2         diagonal    (6, 5)   5
x > y now, so the octant ends: (0, 8) (1, 8) (2, 8) (3, 7) (4, 7) (5, 6)
6 octant points give 44 pixels (# lit, + the centre, y grows downwards):
. . . . . . # # # # # . . . . . .
. . . . # # . . . . . # # . . . .
. . . # . . . . . . . . . # . . .
. . # . . . . . . . . . . . # . .
. # . . . . . . . . . . . . . # .
. # . . . . . . . . . . . . . # .
# . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . #
# . . . . . . . + . . . . . . . #
# . . . . . . . . . . . . . . . #
# . . . . . . . . . . . . . . . #
. # . . . . . . . . . . . . . # .
. # . . . . . . . . . . . . . # .
. . # . . . . . . . . . . . # . .
. . . # . . . . . . . . . # . . .
. . . . # # . . . . . # # . . . .
. . . . . . # # # # # . . . . . .

Updated after the move, the octant becomes (0, 8) (1, 8) (2, 8) (3, 7) (4, 6) (5, 5)

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node midpoint_circle.mjs

Change the radius

Press Edit, set r to 10 and run the program again. The octant now ends on the 45° line, at (7, 7), and the circle has 56 pixels; the next section shows what that point does to symmetry.

From (0, 8), five decisions light (1, 8), (2, 8), (3, 7), (4, 7) and (5, 6), and the sixth would cross the 45° line, so the loop stops. Jack Bresenham showed in 1977 that circular arcs can be drawn this way, with sign tests and simple arithmetic alone; ten years earlier M. L. V. Pitteway had described the same kind of step-by-step choice for ellipses and hyperbolas on a plotter.

The last line of the run shows a slip worth recognising. Moving x and y first and then applying the same updates adds 2 or 4 too much each time, and the octant turns inwards too early: (4, 6) and (5, 5) instead of (4, 7) and (5, 6).

Key idea

d is the circle’s equation at the next midpoint, kept whole: start at 1 − r, step straight while d is below 0 and add 2x + 3, otherwise step diagonally and add 2(x − y) + 5, using the x and y of the pixel just lit.

Checkpoint

Check: Whole-number updates of d

Question 1 of 2 What is d before the first step of the midpoint circle algorithm for radius 10?
Type a number.
Your answer

A hint

The loop starts at (0, r) with d = 1 − r.

Show the answer: Question 1 of 2

Answer: -9

d starts at 1 − r = 1 − 10 = −9. The exact value of F at the first midpoint, (1, 9.5), is 5/4 − 10 = −8.75; the dropped quarter never changes the sign test, so −9 decides the same way.
Question 2 of 2 The loop for radius 8 is at (4, 7) with d = 3. Which step does it take, and what is d after it?
Choose one answer.

A straight step to (5, 7), and d becomes 3 + 2 × 4 + 3 = 14 A diagonal step to (5, 6), and d becomes 3 + 2(4 − 7) + 5 = 2 The loop stops, because d is positive A diagonal step to (5, 6), and d becomes 3 + 2 × 4 + 3 = 14

Show the answer: Question 2 of 2

Answer: A diagonal step to (5, 6), and d becomes 3 + 2(4 − 7) + 5 = 2

This is the fifth decision of the traced octant: d = 3 ≥ 0, so the step is diagonal, to (5, 6), and d becomes 3 − 6 + 5 = 2, which sends the next step diagonally too.

Eight-way symmetry draws the rest, some pixels twice

A circle centred on a pixel is symmetric across both axes, which flip the signs of x and y, and across both diagonals, which swap them. That is eight-way symmetry: The symmetry of a circle centred on a pixel across both axes and both diagonals: each point (x, y) of one octant gives the eight pixels (±x, ±y) and (±y, ±x).: each octant point (x, y) stands for the eight pixels (±x, ±y) and (±y, ±x), so the six computed pixels of radius 8 give all 44:

Eight-way symmetry turns six pixels into forty-four

Text description of the diagram

A 17 by 17 grid around a centre marked +, with y growing downwards. Dashed guide lines through the centre, the two axes and the two diagonals, divide it into eight octants. The 44 pixels of the circle of radius 8 are filled.

The six pixels the loop computes have thick outlines and dots: (0, 8), (1, 8), (2, 8), (3, 7), (4, 7) and (5, 6), in the octant below the centre and to its right, from the vertical axis to the diagonal. The other 38 pixels have thin outlines; each is a mirror image of one of the six across an axis or a diagonal.

Four pixels have a dashed frame: the ends of the axes, (0, 8), (0, −8), (8, 0) and (−8, 0). Plotting all eight mirror images of the octant point (0, 8) hits each of them twice, because changing the sign of x = 0 changes nothing.

The dashed frames mark a trap. On the axis, x = 0, so (0, 8) and (−0, 8) are the same pixel, and plotting all eight images lights each axis end twice. On the 45° line, x = y does the same to four more pixels, whenever the octant ends exactly there. The program counts the repeats for every radius from 1 to 12, then draws radius 10 in black at 50 % opacity over white:

Pixels plotted twice, and pixels lost, for radii 1 to 12 JavaScript · symmetry/duplicates.mjs

// Eight-way symmetry turns each octant point into eight pixels. Where the
// octant touches an axis (x = 0) or the 45° line (x = y), two of the eight
// coincide, and plotting all eight draws those pixels twice.

function octant(r, stopAtDiagonal) {
  let x = 0;
  let y = r;
  let d = 1 - r;
  const points = [];
  // The loop should run while x <= y; "x < y" is the off-by-one version.
  while (stopAtDiagonal ? x < y : x <= y) {
    points.push([x, y]);
    if (d < 0) {
      d += 2 * x + 3;
    } else {
      d += 2 * (x - y) + 5;
      y -= 1;
    }
    x += 1;
  }
  return points;
}

// Every plot of plot8, in order, as "x,y" strings.
function plot8(points) {
  const plots = [];
  for (const [x, y] of points) {
    for (const [a, b] of [[x, y], [y, x]]) {
      for (const [sa, sb] of [[1, 1], [-1, 1], [1, -1], [-1, -1]]) plots.push(`${sa * a},${sb * b}`);
    }
  }
  return plots;
}

// The fix: on an axis (x = 0) or on the 45° line (x = y) only four of the eight
// images differ, so plot just those four there.
function plotOnce(points) {
  const plots = [];
  for (const [x, y] of points) {
    const images = x === 0 ? [[0, y], [0, -y], [y, 0], [-y, 0]]
      : x === y ? [[x, x], [-x, x], [x, -x], [-x, -x]]
      : [[x, y], [-x, y], [x, -y], [-x, -y], [y, x], [-y, x], [y, -x], [-y, -x]];
    for (const [a, b] of images) plots.push(`${a},${b}`);
  }
  return plots;
}

console.log('r   octant  plots  pixels  drawn twice  missing with x < y  plots, fixed');
for (let r = 1; r <= 12; r++) {
  const pts = octant(r, false);
  const plots = plot8(pts);
  const pixels = new Set(plots);
  const short = new Set(plot8(octant(r, true)));
  const missing = [...pixels].filter((p) => !short.has(p)).length;
  const fixed = plotOnce(pts);
  const same = fixed.length === pixels.size && fixed.every((p) => pixels.has(p));
  console.log(`${String(r).padEnd(4)}${String(pts.length).padEnd(8)}${String(plots.length).padEnd(7)}${String(pixels.size).padEnd(8)}${String(plots.length - pixels.size).padEnd(13)}${String(missing).padEnd(20)}${fixed.length}${same ? '' : ' (wrong pixels)'}`);
}

// Why "drawn twice" matters: draw r = 10 in black at 50 % opacity over white.
// A pixel drawn once ends at 50 % black; one drawn twice at 75 %.
const plots = plot8(octant(10, false));
const ink = new Map();
for (const p of plots) ink.set(p, 1 - (1 - (ink.get(p) ?? 0)) * 0.5);
const darker = [...ink].filter(([, v]) => v > 0.5).map(([p]) => `(${p.replace(',', ', ')})`);
console.log('');
console.log(`r = 10 at 50 % opacity: ${ink.size} pixels, ${darker.length} of them at 75 % instead of 50 %:`);
console.log(darker.join(' '));

Output

r   octant  plots  pixels  drawn twice  missing with x < y  plots, fixed
1   1       8      4       4            0                   4
2   2       16     12      4            0                   12
3   3       24     16      8            4                   16
4   4       32     24      8            4                   24
5   4       32     28      4            0                   28
6   5       40     32      8            4                   32
7   6       48     40      8            4                   40
8   6       48     44      4            0                   44
9   7       56     52      4            0                   52
10  8       64     56      8            4                   56
11  9       72     64      8            4                   64
12  9       72     68      4            0                   68

r = 10 at 50 % opacity: 56 pixels, 8 of them at 75 % instead of 50 %:
(0, 10) (0, -10) (10, 0) (-10, 0) (7, 7) (-7, 7) (7, -7) (-7, -7)

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node duplicates.mjs

Every radius repeats its 4 axis pixels, and the radii whose octant ends on the 45° line, 3, 4, 6, 7, 10 and 11, repeat 4 more. At 50 % opacity a repeated pixel ends 75 % dark instead of 50 %, so radius 10 shows eight darker dots, at (0, ±10), (±10, 0) and (±7, ±7). Plotting four images instead of eight on the axis and on the 45° line gives the right pixel count for every radius, as the last column shows.

Ending the loop at x < y

Stopping the loop while x < y looks like a tidy way to avoid the 45° repeats, but it skips the 45° point itself: radii 3, 4, 6, 7, 10 and 11 lose their four diagonal pixels and show holes. Loop while x ≤ y, and plot four images rather than eight where x = 0 or x = y.

Checkpoint

Check: Eight-way symmetry and its repeats

Question 1 of 2 Plotting all eight mirror images of every octant point, how many pixels of the circle of radius 10 are drawn twice?
Type a number.
Your answer pixels

A hint

Look for octant points on an axis (x = 0) and on the 45° line (x = y).

Show the answer: Question 1 of 2

Answer: 8 pixels

The octant of radius 10 starts at (0, 10), on an axis, and ends at (7, 7), on the 45° line. Each of these has only four different images among its eight, so 4 + 4 = 8 pixels are drawn twice, as the table showed.
Question 2 of 2 A version of the loop runs while x < y instead of x ≤ y. Which circles does it damage, and how?
Choose one answer.

Circles whose octant ends on the 45° line, such as radius 10: their four diagonal pixels are never lit No circle, because symmetry fills in what the loop skips Every circle, which loses its four axis pixels Only even radii, which lose one pixel each

Show the answer: Question 2 of 2

Answer: Circles whose octant ends on the 45° line, such as radius 10: their four diagonal pixels are never lit

The 45° point is the octant's last; only circles that have one are damaged. The right loop runs while x ≤ y and plots four images, not eight, at x = y.

An ellipse switches from stepping x to stepping y

An ellipse with semi-axes a along x and b along y has F(x, y) = b²x² + a²y² − a²b², and only four-way symmetry: the mirror images (±x, ±y). There is no octant to mirror across a diagonal, so one quadrant has to be walked from (0, b), where the curve is flat, to (a, 0), where it is vertical. At a point (x, y) of the curve the slope is −b²x ÷ (a²y), which reaches −1 where b²x = a²y: for a = 10 and b = 4, at (9.28, 1.49).

So the walk has two regions. In region 1 x steps by one and the midpoint (x + 1, y − ½) decides whether y steps too, exactly as for the circle. While b²x < a²y the loop stays in region 1; from the first pixel where that fails, region 2 steps y down by one and the midpoint (x + ½, y − 1) decides whether x steps too. Both decision variables are 4F at their midpoint, which keeps them whole: region 1 starts at 4b² − 4a²b + a². The figure shows the quadrant of a = 10, b = 4:

The ellipse switches from stepping x to stepping y where its slope passes −1

Text description of the diagram

A grid with x from 0 to 10 across and y from 0 to 4 down, the quadrant of the ellipse with semi-axes a = 10 and b = 4 below and to the right of its centre at (0, 0). The true curve runs from (0, 4) at the bottom left, flat at first, to (10, 0) at the top right, steep at the end. Every lit pixel has a dot at its centre.

Region 1, where x steps by one, has solid outlines: (0, 4), (1, 4), (2, 4), (3, 4), (4, 4), (5, 3), (6, 3), (7, 3), (8, 2) and (9, 2).
Region 2, where y steps by one, has dashed outlines: (10, 1) and (10, 0).

An open diamond on the curve at (9.28, 1.49) marks where the slope is exactly −1, between the last pixel of region 1 and the first of region 2.

Ten pixels come from region 1 and two from region 2. The program runs four ellipses: the figure’s, its tall twin a = 4, b = 10, the circle case a = b, and a very flat one:

Two regions for four ellipses, and what goes wrong without them JavaScript · ellipse/midpoint_ellipse.mjs

// The midpoint ellipse algorithm for x²/a² + y²/b² = 1, in whole numbers.
// Region 1, where the slope is between 0 and -1: x steps by 1 and p1 decides
// whether y steps down. Region 2, where it is steeper: y steps down by 1 and
// p2 decides whether x steps on. Both are 4 F(midpoint), so they stay whole.

function quadrant(a, b) {
  const a2 = a * a;
  const b2 = b * b;
  let x = 0;
  let y = b;
  const region1 = [];
  const region2 = [];
  const tip = [];
  let p1 = 4 * b2 - 4 * a2 * b + a2; // 4 F(1, b - 1/2)
  while (b2 * x < a2 * y) { // the slope -b²x / (a²y) has not reached -1 yet
    region1.push([x, y]);
    if (p1 < 0) {
      p1 += 4 * b2 * (2 * x + 3);
    } else {
      p1 += 4 * b2 * (2 * x + 3) - 8 * a2 * (y - 1);
      y -= 1;
    }
    x += 1;
  }
  let p2 = b2 * (2 * x + 1) * (2 * x + 1) + 4 * a2 * (y - 1) * (y - 1) - 4 * a2 * b2; // 4 F(x + 1/2, y - 1)
  while (y >= 0) {
    region2.push([x, y]);
    if (p2 > 0) {
      p2 += 4 * a2 * (3 - 2 * y);
    } else {
      p2 += 4 * a2 * (3 - 2 * y) + 8 * b2 * (x + 1);
      x += 1;
    }
    y -= 1;
  }
  // A very flat ellipse can reach y = 0 in region 1, before its tip: finish the row to (a, 0).
  for (let tx = region2[region2.length - 1][0] + 1; tx <= a; tx++) tip.push([tx, 0]);
  return { region1, region2, tip };
}

// The midpoint circle of the circle example, for the comparison.
function circle(r) {
  let x = 0;
  let y = r;
  let d = 1 - r;
  const lit = new Set();
  while (x <= y) {
    for (const [p, q] of [[x, y], [y, x]]) for (const [s, t] of [[1, 1], [-1, 1], [1, -1], [-1, -1]]) lit.add(`${s * p},${t * q}`);
    if (d < 0) d += 2 * x + 3;
    else {
      d += 2 * (x - y) + 5;
      y -= 1;
    }
    x += 1;
  }
  return lit;
}

const show = ([x, y]) => `(${x}, ${y})`;
const fourWay = (points) => points.flatMap(([x, y]) => [[x, y], [-x, y], [x, -y], [-x, -y]].map(([p, q]) => `${p},${q}`));
const pixelsOf = (a, b) => {
  const q = quadrant(a, b);
  return new Set(fourWay([...q.region1, ...q.region2, ...q.tip]));
};

for (const [a, b] of [[10, 4], [4, 10], [7, 7], [8, 1]]) {
  const { region1, region2, tip } = quadrant(a, b);
  const plots = fourWay([...region1, ...region2, ...tip]);
  const pixels = new Set(plots);
  const twice = [...pixels].filter((p) => plots.filter((q) => q === p).length > 1);
  const onAxes = twice.filter((p) => p.split(',').includes('0')).length;
  console.log(`a = ${a}, b = ${b}`);
  console.log(`  region 1 (x steps): ${region1.map(show).join(' ')}`);
  console.log(`  region 2 (y steps): ${region2.map(show).join(' ')}`);
  if (tip.length) console.log(`  region 1 reached y = 0 before the tip, so the row is finished: ${tip.map(show).join(' ')}`);
  console.log(`  ${pixels.size} pixels from ${plots.length} plots: ${twice.length} drawn twice, ${onAxes} of them on an axis`);
  if (a === b) {
    const c = circle(a);
    const same = c.size === pixels.size && [...c].every((p) => pixels.has(p));
    console.log(`  the same pixels as the midpoint circle of radius ${a}: ${same ? 'yes' : 'no'}`);
  }
}

// Is the ellipse with a and b swapped the exact mirror image?
let mirrored = 0;
for (let a = 1; a <= 20; a++) {
  for (let b = 1; b <= 20; b++) {
    const swapped = new Set([...pixelsOf(b, a)].map((p) => p.split(',').reverse().join(',')));
    const own = pixelsOf(a, b);
    if (own.size === swapped.size && [...own].every((p) => swapped.has(p))) mirrored++;
  }
}
console.log(`Swapping a and b gives the exact mirror image for ${mirrored} of the 400 ellipses with a, b from 1 to 20`);

// How many of them need the last loop, the one that finishes the row to (a, 0)?
const short = [];
for (let a = 1; a <= 20; a++) for (let b = 1; b <= 20; b++) if (quadrant(a, b).tip.length) short.push(`${a}, ${b}`);
console.log(`Without the loop that finishes the row, ${short.length} of the 400 would lose their tips: a, b = ${short.join('; ')}`);

// Stepping x across the whole quadrant, as region 1 does, breaks the steep part.
console.log('');
for (const [a, b] of [[10, 4], [4, 10]]) {
  const ys = [];
  for (let x = 0; x <= a; x++) ys.push(Math.round(b * Math.sqrt(1 - (x * x) / (a * a))));
  const jumps = ys.slice(1).map((y, i) => ys[i] - y).filter((dy) => dy > 1);
  const widest = Math.max(0, ...jumps) - 1;
  console.log(`a = ${a}, b = ${b}, one pixel per column: y = ${ys.join(', ')}; ${jumps.length} gap${jumps.length === 1 ? '' : 's'}, the widest ${widest} row${widest === 1 ? '' : 's'}`);
}

// The ellipse a = 10, b = 4 around its centre (+), y growing downwards.
const lit = pixelsOf(10, 4);
console.log('');
for (let y = -4; y <= 4; y++) {
  let row = '';
  for (let x = -10; x <= 10; x++) row += lit.has(`${x},${y}`) ? '#' : x === 0 && y === 0 ? '+' : '.';
  console.log(row.split('').join(' '));
}

Output

a = 10, b = 4
  region 1 (x steps): (0, 4) (1, 4) (2, 4) (3, 4) (4, 4) (5, 3) (6, 3) (7, 3) (8, 2) (9, 2)
  region 2 (y steps): (10, 1) (10, 0)
  44 pixels from 48 plots: 4 drawn twice, 4 of them on an axis
a = 4, b = 10
  region 1 (x steps): (0, 10) (1, 10)
  region 2 (y steps): (2, 9) (2, 8) (3, 7) (3, 6) (3, 5) (4, 4) (4, 3) (4, 2) (4, 1) (4, 0)
  44 pixels from 48 plots: 4 drawn twice, 4 of them on an axis
a = 7, b = 7
  region 1 (x steps): (0, 7) (1, 7) (2, 7) (3, 6) (4, 6)
  region 2 (y steps): (5, 5) (6, 4) (6, 3) (7, 2) (7, 1) (7, 0)
  40 pixels from 44 plots: 4 drawn twice, 4 of them on an axis
  the same pixels as the midpoint circle of radius 7: yes
a = 8, b = 1
  region 1 (x steps): (0, 1) (1, 1) (2, 1) (3, 1) (4, 1) (5, 1) (6, 1)
  region 2 (y steps): (7, 0)
  region 1 reached y = 0 before the tip, so the row is finished: (8, 0)
  30 pixels from 36 plots: 6 drawn twice, 6 of them on an axis
Swapping a and b gives the exact mirror image for 354 of the 400 ellipses with a, b from 1 to 20
Without the loop that finishes the row, 13 of the 400 would lose their tips: a, b = 8, 1; 9, 1; 10, 1; 11, 1; 12, 1; 13, 1; 14, 1; 15, 1; 16, 1; 17, 1; 18, 1; 19, 1; 20, 1

a = 10, b = 4, one pixel per column: y = 4, 4, 4, 4, 4, 3, 3, 3, 2, 2, 0; 1 gap, the widest 1 row
a = 4, b = 10, one pixel per column: y = 10, 10, 9, 7, 0; 2 gaps, the widest 6 rows

. . . . . . # # # # # # # # # . . . . . .
. . . # # # . . . . . . . . . # # # . . .
. # # . . . . . . . . . . . . . . . # # .
# . . . . . . . . . . . . . . . . . . . #
# . . . . . . . . . + . . . . . . . . . #
# . . . . . . . . . . . . . . . . . . . #
. # # . . . . . . . . . . . . . . . # # .
. . . # # # . . . . . . . . . # # # . . .
. . . . . . # # # # # # # # # . . . . . .

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node midpoint_ellipse.mjs

With a = b = 7 the ellipse gives exactly the 40 pixels of the midpoint circle of radius 7. Without region 2, one pixel per column breaks the tall ellipse a = 4, b = 10 apart: y = 10, 10, 9, 7, 0, with two gaps, the wider one 6 rows. The flat ellipse a = 8, b = 1 exposes a second boundary case. Region 1 uses up its single row at x = 7, before the slope test can fail, so region 2 starts at (7, 0) and ends at once; unless the row is finished to (8, 0), the ellipse comes out 15 pixels wide instead of 17. Among the 400 ellipses with a and b from 1 to 20, 13 need that last loop, all with b = 1.

Swapping a and b is not quite a mirror either: 354 of the 400 ellipses match their swapped twin exactly, and the other 46 differ by a pixel or two in each quadrant, near the switch, because the switch is tested at a pixel, one step behind the curve. Pitteway’s paper counted three additions and one comparison per step for curves of this kind, and Jerry Van Aken’s 1984 paper is devoted to drawing ellipses efficiently.

Checkpoint

Check: The ellipse's two regions

Question 1 of 2 When does the midpoint ellipse algorithm switch from region 1 to region 2?
Choose one answer.

When the decision variable p1 changes sign When x reaches a ÷ 2 When b²x ≥ a²y, where the slope of the curve, −b²x ÷ (a²y), has passed −1 When y reaches 0

Show the answer: Question 1 of 2

Answer: When b²x ≥ a²y, where the slope of the curve, −b²x ÷ (a²y), has passed −1

For a = 10 and b = 4 the slope is −1 at (9.28, 1.49); the test b²x < a²y holds at (9, 2), 144 < 200, and fails at (10, 1), 160 > 100, so region 2 takes over from (10, 1).
Question 2 of 2 A routine lights one pixel per column for the whole quadrant of the ellipse a = 4, b = 10, at y = round(b √(1 − x²/a²)). What goes wrong?
Choose one answer.

Every pixel is lit twice Its steep part breaks into separate pixels, with a gap of 6 rows between the last two columns Nothing, because the ellipse has only 5 columns to fill It draws a circle of radius 4 instead

Show the answer: Question 2 of 2

Answer: Its steep part breaks into separate pixels, with a gap of 6 rows between the last two columns

Where the curve is steeper than −1 it falls more than one row per column, so one pixel per column must leave gaps. Region 2 steps y instead, one row at a time.

A filled disc tests every pixel centre

An outline is not a disc. To fill a circle, light every pixel whose centre satisfies x² + y² ≤ r²: the same implicit function, now tested at every pixel centre of the bounding square rather than at midpoints. The tempting shortcut, filling each row between the two ends of the midpoint outline, gives a different answer, and the program shows why:

A disc and a ring of radius 8, from pixel centres JavaScript · disc/disc_ring.mjs

// Filling a circle: test each pixel centre against x² + y² <= r², or fill each
// row between the outermost pixels of the midpoint outline. The two disagree,
// because the outline lies on both sides of the true circle.

function outline(r) {
  let x = 0;
  let y = r;
  let d = 1 - r;
  const lit = new Set();
  while (x <= y) {
    for (const [p, q] of [[x, y], [y, x]]) for (const [s, t] of [[1, 1], [-1, 1], [1, -1], [-1, -1]]) lit.add(`${s * p},${t * q}`);
    if (d < 0) d += 2 * x + 3;
    else {
      d += 2 * (x - y) + 5;
      y -= 1;
    }
    x += 1;
  }
  return lit;
}

const r = 8;
const edge = outline(r);
const inside = (x, y) => x * x + y * y <= r * r;
let byCentre = 0;
let bySpans = 0;
let outlineOutside = 0;
for (let y = -r; y <= r; y++) {
  const xs = [...edge].map((p) => p.split(',').map(Number)).filter(([, q]) => q === y).map(([p]) => p);
  bySpans += Math.max(...xs) - Math.min(...xs) + 1;
  for (let x = -r; x <= r; x++) {
    if (inside(x, y)) byCentre++;
    if (edge.has(`${x},${y}`) && !inside(x, y)) outlineOutside++;
  }
}
console.log(`Radius ${r}, centre on a pixel centre; the true area is pi r² = ${(Math.PI * r * r).toFixed(2)} pixels`);
console.log(`  pixel centres with x² + y² <= r²: ${byCentre}`);
console.log(`  rows filled between the outline's ends: ${bySpans}`);
console.log(`  outline pixels whose centres lie outside the circle: ${outlineOutside} of ${edge.size}`);

const t = 2;
let ring = 0;
for (let y = -r; y <= r; y++) for (let x = -r; x <= r; x++) {
  const q = x * x + y * y;
  if (q > (r - t) * (r - t) && q <= r * r) ring++;
}
console.log(`A ring ${t} pixels wide, (r - ${t})² < x² + y² <= r²: ${ring} pixels; its true area is ${(Math.PI * (r * r - (r - t) * (r - t))).toFixed(2)}`);

console.log('');
console.log('# outline and inside, o outline but outside, : inside only (y grows downwards)');
for (let y = -r; y <= r; y++) {
  let row = '';
  for (let x = -r; x <= r; x++) {
    const e = edge.has(`${x},${y}`);
    row += e && inside(x, y) ? '#' : e ? 'o' : inside(x, y) ? ':' : '.';
  }
  console.log(row.split('').join(' '));
}

Output

Radius 8, centre on a pixel centre; the true area is pi r² = 201.06 pixels
  pixel centres with x² + y² <= r²: 197
  rows filled between the outline's ends: 221
  outline pixels whose centres lie outside the circle: 24 of 44
A ring 2 pixels wide, (r - 2)² < x² + y² <= r²: 84 pixels; its true area is 87.96

# outline and inside, o outline but outside, : inside only (y grows downwards)
. . . . . . o o # o o . . . . . .
. . . . o # : : : : : # o . . . .
. . . # : : : : : : : : : # . . .
. . # : : : : : : : : : : : # . .
. o : : : : : : : : : : : : : o .
. # : : : : : : : : : : : : : # .
o : : : : : : : : : : : : : : : o
o : : : : : : : : : : : : : : : o
# : : : : : : : : : : : : : : : #
o : : : : : : : : : : : : : : : o
o : : : : : : : : : : : : : : : o
. # : : : : : : : : : : : : : # .
. o : : : : : : : : : : : : : o .
. . # : : : : : : : : : : : # . .
. . . # : : : : : : : : : # . . .
. . . . o # : : : : : # o . . . .
. . . . . . o o # o o . . . . . .

Recorded with Node.js 24.21.0 on macOS 26 arm64. To run it yourself: mise exec node@24.21.0 -- node disc_ring.mjs

The centre test lights 197 pixels, against a true area of 201.06. Filling between the outline’s ends lights 221: the 24 extra pixels are exactly the outline pixels whose centres lie outside the circle, marked o in the grid. The outline lights the pixel nearest the curve on whichever side it falls, so a disc filled up to it is a little fatter than the circle.

Outline or fill

Use the midpoint algorithm for an outline one pixel wide, and the centre test for a filled disc or a ring. Filling between the ends of an outline adds the outline’s outer pixels, 24 of them at radius 8.

A ring t pixels wide is the centre test twice, (r − t)² < x² + y² ≤ r²: 84 pixels for r = 8 and t = 2, against an area of 87.96. Testing pixel centres generalises: any shape with an implicit function can be filled this way, and later modules use the same test, with a signed distance in place of F, for thick outlines and smooth edges.

UGC NET and university syllabi

Unit 3 of the UGC NET syllabus for Computer Science and Applications names “Mid-Point Circle and Ellipse Algorithms”. At GTU, course BE05000161 teaches the midpoint circle algorithm, and its practical list has students implement both the circle and the ellipse. A question in that style: trace the midpoint circle algorithm for r = 5. d runs −4, −1, 4, 3, so the octant is (0, 5), (1, 5), (2, 5), (3, 4).

Checkpoint

Check: Discs and rings from pixel centres

Question 1 of 2 How many pixel centres satisfy x² + y² ≤ r² for r = 2, with the centre on a pixel centre?
Type a number.
Your answer pixels

A hint

Count row by row from y = −2 to y = 2.

Show the answer: Question 1 of 2

Answer: 13 pixels

Rows y = ±2 have only x = 0 (1 each), rows y = ±1 have x from −1 to 1 (3 each), and row y = 0 has x from −2 to 2 (5): 1 + 3 + 5 + 3 + 1 = 13 pixels, against a true area of 4π ≈ 12.57.
Question 2 of 2 For radius 8, filling each row between the ends of the midpoint outline gives 221 pixels, while the centre test gives 197. Where do the 24 extra pixels come from?
Choose one answer.

The spans count the outline twice Rounding errors in the square roots The centre test misses pixels inside the circle They are outline pixels whose centres lie just outside the circle

Show the answer: Question 2 of 2

Answer: They are outline pixels whose centres lie just outside the circle

The outline sits on both sides of the curve, so a disc filled up to it is a little fatter than the circle. When a filled disc must match the circle's area and its neighbours, test pixel centres instead.

Practise: circles and ellipses without repeated pixels

The lab below has two steps, each with sample tests you can run in place: first the circle, lighting each pixel exactly once, then the ellipse with both regions, the flat tip and no gaps, tested on every a and b from 1 to 16:

Code lab · 2 steps

Circles and ellipses, each pixel once

Write the midpoint circle with four images on the axes and the 45° line, then the two-region ellipse that keeps its tips and leaves no gaps.

A midpoint circle with every pixel exactly once To do
A midpoint ellipse with two regions and no gaps To do

Exercise · Easy · JavaScript

A midpoint circle with every pixel exactly once

Write circlePixels(cx, cy, r) in circle.mjs. It returns every pixel of the midpoint circle of whole-number radius r around the pixel (cx, cy), as [x, y] pairs, each pixel exactly once, in any order.

Walk the octant from (0, r) with the lesson's rule: d starts at 1 - r; below 0, step straight and add 2 * x + 3; otherwise step diagonally (y goes down by one) and add 2 * (x - y) + 5; keep going while x <= y.
Turn each octant point into its mirror images, but never return a pixel twice: on an axis (x = 0) and on the 45° line (x = y) only four of the eight images differ.
A circle of radius 0 is the single pixel (cx, cy).

The starter plots all eight images of every point, so it returns some pixels twice. The sample tests check the lesson's circle of radius 8, the pixel counts of the radii 1 to 12, circles away from the origin, and every radius up to 40 for repeated pixels and for pixels more than half a pixel from the circle.

Starter code · circle.mjs

/** Every pixel of the midpoint circle of radius r around (cx, cy), each exactly once. */
export function circlePixels(cx, cy, r) {
  const pixels = [];
  let x = 0;
  let y = r;
  let d = 1 - r;
  while (x <= y) {
    // All eight mirror images of (x, y): some of them coincide.
    for (const [p, q] of [[x, y], [-x, y], [x, -y], [-x, -y], [y, x], [-y, x], [y, -x], [-y, -x]]) pixels.push([cx + p, cy + q]);
    if (d < 0) {
      d += 2 * x + 3;
    } else {
      d += 2 * (x - y) + 5;
      y -= 1;
    }
    x += 1;
  }
  return pixels;
}

The sample tests · circle.test.mjs

import { test, assert } from 'mysmartcopilot:test';
import { circlePixels } from './circle.mjs';

const key = ([x, y]) => `${x},${y}`;
const sorted = (list) => [...list].sort((p, q) => p[0] - q[0] || p[1] - q[1]);
// The eight mirror images of the points of one octant, as a sorted list without repeats.
const mirrored = (octant, cx = 0, cy = 0) => {
  const seen = new Map();
  for (const [x, y] of octant) {
    for (const [p, q] of [[x, y], [-x, y], [x, -y], [-x, -y], [y, x], [-y, x], [y, -x], [-y, -x]]) seen.set(key([cx + p, cy + q]), [cx + p, cy + q]);
  }
  return sorted(seen.values());
};

test("the lesson's circle of radius 8 around (0, 0)", () => {
  const pixels = circlePixels(0, 0, 8);
  assert.equal(pixels.length, 44, 'radius 8 lights 44 pixels, each once');
  assert.deepEqual(sorted(pixels), mirrored([[0, 8], [1, 8], [2, 8], [3, 7], [4, 7], [5, 6]]));
});

test('the pixel counts of the radii 0 to 12, with no pixel twice', () => {
  const counts = [1, 4, 12, 16, 24, 28, 32, 40, 44, 52, 56, 64, 68];
  counts.forEach((want, r) => {
    const pixels = circlePixels(0, 0, r);
    assert.equal(new Set(pixels.map(key)).size, pixels.length, `radius ${r} returns a pixel twice`);
    assert.equal(pixels.length, want, `radius ${r}`);
  });
  assert.deepEqual(circlePixels(0, 0, 0), [[0, 0]], 'radius 0 is the centre pixel alone');
});

test('a circle away from the origin, with points on the 45° line', () => {
  const pixels = circlePixels(20, 15, 10);
  assert.equal(pixels.length, 56);
  const want = mirrored([[0, 10], [1, 10], [2, 10], [3, 10], [4, 9], [5, 9], [6, 8], [7, 7]], 20, 15);
  assert.deepEqual(sorted(pixels), want);
  for (const p of [[27, 22], [13, 8], [20, 25], [30, 15]]) assert.ok(pixels.some((q) => key(q) === key(p)), `(${p[0]}, ${p[1]}) is on the circle`);
});

test('every radius up to 40: no pixel twice, each within half a pixel of the circle', () => {
  for (let r = 1; r <= 40; r++) {
    const pixels = circlePixels(5, -3, r);
    assert.equal(new Set(pixels.map(key)).size, pixels.length, `radius ${r} returns a pixel twice`);
    for (const [x, y] of pixels) {
      const u = Math.min(Math.abs(x - 5), Math.abs(y + 3));
      const v = Math.max(Math.abs(x - 5), Math.abs(y + 3));
      const s2 = 4 * (r * r - u * u); // (2 times the circle's height in that column) squared
      assert.ok((2 * v - 1) ** 2 <= s2 && s2 <= (2 * v + 1) ** 2, `radius ${r}: (${x}, ${y}) is more than half a pixel from the circle`);
    }
  }
});

A hint

Keep the octant loop as it is and change only what it plots. Before plotting a point, look at it: when x === 0 its images are (0, y), (0, -y), (y, 0) and (-y, 0); when x === y they are the four points (±x, ±x); otherwise all eight images differ. Add cx and cy to every image as you push it.

The sample tests run on this device, in your browser (QuickJS): nothing is sent to mysmartcopilot.com. The first run downloads JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.

Exercise · Medium · JavaScript

A midpoint ellipse with two regions and no gaps

Write ellipsePixels(cx, cy, a, b) in ellipse.mjs. It returns every pixel of the midpoint ellipse with whole-number semi-axes a along x and b along y, both at least 1, around the pixel (cx, cy), as [x, y] pairs, each pixel exactly once, in any order.

Region 1 starts at (0, b) with p1 = 4b² − 4a²b + a² and steps x while b²x < a²y: below 0 add 4b²(2x + 3); otherwise y goes down by one and you add 4b²(2x + 3) − 8a²(y − 1), with the values before the step.
Region 2 starts where region 1 stopped, with p2 = b²(2x + 1)² + 4a²(y − 1)² − 4a²b², and steps y down while y >= 0: above 0 add 4a²(3 − 2y); otherwise x goes up by one and you add 4a²(3 − 2y) + 8b²(x + 1).
If the quadrant stops short of (a, 0), as a very flat ellipse does, finish its last row up to (a, 0).
Mirror the quadrant into four, with no pixel twice: points on an axis have only two different images.

The starter lights one pixel per column across the whole quadrant, which leaves gaps where the ellipse is steep and repeats pixels on the axes. The sample tests check the lesson's ellipses, the circle case a = b, flat ellipses, and every a and b from 1 to 16 for repeated pixels, missing tips and gaps.

Starter code · ellipse.mjs

/** Every pixel of the midpoint ellipse with semi-axes a (along x) and b (along y) around (cx, cy), each exactly once. */
export function ellipsePixels(cx, cy, a, b) {
  const pixels = [];
  // One pixel per column across the whole quadrant: fine where the ellipse is flat, broken where it is steep.
  for (let x = 0; x <= a; x++) {
    const y = Math.round(b * Math.sqrt(1 - (x * x) / (a * a)));
    for (const [p, q] of [[x, y], [-x, y], [x, -y], [-x, -y]]) pixels.push([cx + p, cy + q]);
  }
  return pixels;
}

The sample tests · ellipse.test.mjs

import { test, assert } from 'mysmartcopilot:test';
import { ellipsePixels } from './ellipse.mjs';

const key = ([x, y]) => `${x},${y}`;
const sorted = (list) => [...list].sort((p, q) => p[0] - q[0] || p[1] - q[1]);
// The four mirror images of a quadrant's points, as a sorted list without repeats.
const mirrored = (quadrant, cx = 0, cy = 0) => {
  const seen = new Map();
  for (const [x, y] of quadrant) {
    for (const [p, q] of [[x, y], [-x, y], [x, -y], [-x, -y]]) seen.set(key([cx + p, cy + q]), [cx + p, cy + q]);
  }
  return sorted(seen.values());
};
// True when every pixel can be reached from every other through 8-neighbours.
const connected = (pixels) => {
  const all = new Set(pixels.map(key));
  const seen = new Set([key(pixels[0])]);
  const todo = [pixels[0]];
  while (todo.length) {
    const [x, y] = todo.pop();
    for (let i = -1; i <= 1; i++) {
      for (let j = -1; j <= 1; j++) {
        const k = key([x + i, y + j]);
        if (all.has(k) && !seen.has(k)) {
          seen.add(k);
          todo.push([x + i, y + j]);
        }
      }
    }
  }
  return seen.size === all.size;
};

test("the lesson's ellipses a = 10, b = 4 and a = 4, b = 10", () => {
  const flat = ellipsePixels(0, 0, 10, 4);
  assert.equal(flat.length, 44, 'a = 10, b = 4 lights 44 pixels, each once');
  assert.deepEqual(sorted(flat), mirrored([[0, 4], [1, 4], [2, 4], [3, 4], [4, 4], [5, 3], [6, 3], [7, 3], [8, 2], [9, 2], [10, 1], [10, 0]]));
  const tall = ellipsePixels(0, 0, 4, 10);
  assert.equal(tall.length, 44);
  assert.deepEqual(sorted(tall), mirrored([[0, 10], [1, 10], [2, 9], [2, 8], [3, 7], [3, 6], [3, 5], [4, 4], [4, 3], [4, 2], [4, 1], [4, 0]]));
});

test('a = b gives the midpoint circle', () => {
  const pixels = ellipsePixels(3, 4, 7, 7);
  assert.equal(pixels.length, 40, 'the circle of radius 7 has 40 pixels');
  assert.deepEqual(sorted(pixels), mirrored([[0, 7], [1, 7], [2, 7], [3, 6], [4, 6], [5, 5], [6, 4], [6, 3], [7, 2], [7, 1], [7, 0]], 3, 4));
});

test('a flat ellipse keeps its tips', () => {
  const pixels = ellipsePixels(0, 0, 8, 1);
  assert.deepEqual(sorted(pixels), mirrored([[0, 1], [1, 1], [2, 1], [3, 1], [4, 1], [5, 1], [6, 1], [7, 0], [8, 0]]));
  assert.ok(pixels.some((p) => key(p) === '8,0') && pixels.some((p) => key(p) === '-8,0'), 'the tips (8, 0) and (-8, 0) are lit');
});

test('every a and b from 1 to 16: no pixel twice, both tips, no gaps', () => {
  for (let a = 1; a <= 16; a++) {
    for (let b = 1; b <= 16; b++) {
      const pixels = ellipsePixels(10, 20, a, b);
      const set = new Set(pixels.map(key));
      assert.equal(set.size, pixels.length, `a = ${a}, b = ${b} returns a pixel twice`);
      for (const tip of [[10 + a, 20], [10 - a, 20], [10, 20 + b], [10, 20 - b]]) assert.ok(set.has(key(tip)), `a = ${a}, b = ${b}: the tip (${tip[0]}, ${tip[1]}) is missing`);
      assert.ok(connected(pixels), `a = ${a}, b = ${b} has a gap`);
    }
  }
});

A hint

Write the quadrant first, as a list of points with x ≥ 0 and y ≥ 0: one loop for region 1 and a second loop for region 2 that starts from the x and y the first loop left behind (that point is not plotted yet). Only after the quadrant is complete, and its last row finished to (a, 0) if needed, add the mirror images, (±x, ±y), skipping the repeats where x or y is 0.

Circle Calculator Work out the area of a circle of any radius and compare it with the pixel counts of the centre test, such as 197 for radius 8. Pixel Art Maker Draw the octant of radius 8 by hand, then mirror it across the axes and the diagonals and count the 44 pixels.

Then try the adaptive self-check: it picks the idea you have done least well on, raises the level as your answers come out right, and explains any wrong choice on the spot:

Interview questions

Warm-up (fresher to 2-5 years): Why does the midpoint circle algorithm compute only one octant, and what does its decision variable measure?

A circle centred on a pixel is symmetric across both axes and both diagonals, so each point (x, y) of one octant gives eight pixels, (±x, ±y) and (±y, ±x). In the octant from (0, r) to the 45° line, x steps by one each time and y either stays or moves one row towards the centre, so each column has only two candidates. The decision variable d is the circle’s equation x² + y² − r² at the midpoint between them, less a constant quarter: below 0 the midpoint is inside, so the outer candidate is nearer; otherwise the inner one is. It starts at 1 − r and changes by 2x + 3 or 2(x − y) + 5, whole numbers, so the loop needs only additions and comparisons. On an axis or the 45° line only four images differ, so plot four there.

The two questions below begin from bugs this lesson reproduced; the module’s question page gives a first step for each and the follow-ups to expect:

Model answers open with any pass: ₹79 for 1 week ($2.99), one payment that never renews.

Choose a pass

Fresher to mid

A UI library draws circle outlines at 50 % opacity with a midpoint routine. Designers see eight darker dots on some radii and four on others, and after a tidy-up of the loop some outlines have four holes instead. Explain both, with numbers, and fix the routine.

Model answer, Pro. Model answers open with any pass; prices are in the notice on this page. First step and follow-ups
Mid to senior

An ellipse routine draws wide ellipses well, but tall ones break into separate pixels near their top and bottom, and an ellipse meant to be 17 pixels wide and 3 tall comes out 15 wide. Explain both defects and fix the routine.

Model answer, Pro. First step and follow-ups

Key takeaways

The sign of x² + y² − r² tells inside from outside, so testing it at the midpoint between two candidates chooses the nearer pixel with no square root.
d starts at 1 − r and changes by 2x + 3 or 2(x − y) + 5, whole numbers; for a whole-number radius no midpoint ever lies exactly on the circle.
Eight-way symmetry turns one octant into the whole circle, but the axis and 45° points have only four distinct images: loop while x ≤ y and plot four there, or pixels are drawn twice or lost.
An ellipse has only four-way symmetry, so it steps x until b²x reaches a²y and then steps y; a very flat one also needs its last row finished to the tip.
A filled disc is the set of pixel centres with x² + y² ≤ r², 197 pixels for radius 8; filling between the outline’s ends adds 24 outside pixels.

Terms in this lesson

eight-way symmetry: The symmetry of a circle centred on a pixel across both axes and both diagonals: each point (x, y) of one octant gives the eight pixels (±x, ±y) and (±y, ±x).
implicit function: A function F(x, y) that is 0 on a curve, negative on one side of it and positive on the other, such as x² + y² − r² for a circle. Its sign tells which side a point lies on.
midpoint test: Choosing between two candidate pixels by evaluating a curve's implicit function at the point halfway between their centres: the sign says which candidate the curve passes nearer.

References

A linear algorithm for incremental digital display of circular arcs (Communications of the ACM, vol. 20, no. 2) (Association for Computing Machinery)
Algorithm for drawing ellipses or hyperbolae with a digital plotter (The Computer Journal, vol. 10, no. 3) (Oxford University Press for the British Computer Society)
An efficient ellipse-drawing algorithm (IEEE Computer Graphics and Applications, vol. 4, no. 9) (IEEE)
UGC NET syllabus: Computer Science and Applications (code 87) (University Grants Commission (UGC NET Bureau))
Computer Graphics and Visualization (BE05000161) syllabus (Gujarat Technological University)

Report a problem with this lesson

Your country

Midpoint circle and ellipse algorithms

What you will learn

Before you start

What you will learn

Before you start

A circle’s equation tells inside from outside

Whole-number updates trace one octant

Eight-way symmetry draws the rest, some pixels twice

An ellipse switches from stepping x to stepping y

A filled disc tests every pixel centre

Practise: circles and ellipses without repeated pixels

A midpoint circle with every pixel exactly once

Results of the sample tests

A midpoint ellipse with two regions and no gaps

Results of the sample tests

Interview questions

A UI library draws circle outlines at 50 % opacity with a midpoint routine. Designers see eight darker dots on some radii and four on others, and after a tidy-up of the loop some outlines have four holes instead. Explain both, with numbers, and fix the routine.

An ellipse routine draws wide ellipses well, but tall ones break into separate pixels near their top and bottom, and an ellipse meant to be 17 pixels wide and 3 tall comes out 15 wide. Explain both defects and fix the routine.

Key takeaways

References

Related tools