Midpoint circle drawing algorithm, pixel by pixel

Same radius. Different pixels.

At radius 5, the midpoint outline and the four-neighbor boundary both use 28 pixels. Yet 32 positions differ between their sets. Equal material counts do not guarantee the same shape. The eight-neighbor boundary uses 36 pixels, and the filled disk contains 81.

How the midpoint circle drawing algorithm works

The UIC circle-drawing notes describe choosing between neighboring pixels in one octant, then reflecting the choice around the center. This reference uses the following integer recurrence:

x = 0; y = r; d = 1 - r
while x <= y:
    emit the eight reflections of (x, y)
    if d < 0:
        d = d + 2*x + 3
    else:
        d = d + 2*(x - y) + 5
        y = y - 1
    x = x + 1

The coordinates here are relative to the center. Add (r, r) to place them in the 2r + 1 grid. If d is zero, this recurrence takes the SE branch. Axis and diagonal reflections can repeat a coordinate; the count includes each selected pixel only once.

What the comparison rules select

Filled disk

Keep a pixel when its center satisfies (x − r)² + (y − r)² ≤ r². Centers exactly on the circle are included.

Four-neighbor boundary

Keep a disk pixel if at least one neighbor directly above, below, left or right is outside the disk.

Eight-neighbor boundary

Also inspect the four diagonal neighbors. A disk pixel remains if any of these eight neighbors is outside.

These rules answer different questions. The boundary rules keep only centers inside the disk. Midpoint stepping follows the curve and can choose centers just outside it. A larger pixel count or a smaller difference does not establish better visual quality.

Red Blob Games’ circle-on-a-grid explanation discusses fills, outlines, center positions and radius conventions. Stefan Gustavson’s original midpoint demonstration provides another integer formulation. Those sources explain the algorithms; the comparison data below were computed for this reference.

Results for 64 integer radii

We computed radii 1–64, four pixel sets per radius: 256 method cases. Midpoint and four-neighbor masks differ at 63 of 64 radii; midpoint and eight-neighbor masks differ at all 64. The four-neighbor mask agrees with midpoint only at radius 1 in this range.

“Differing positions” means the symmetric difference: the number of coordinates included by exactly one method. It measures a change in selected pixels, not distance from the curve, aesthetic quality or drawing speed.

Download the data and reproduce the results

Download all seven files into one folder. With Node.js 20 or later, run node reproduce.mjs --check to compare the generated CSV and JSON with the downloaded bytes. Run without --check to regenerate them. No additional packages are required.

• Summary results · CSV
• Complete pixel masks and traces · JSON
• Methods and source notes · JSON
• Scope and limitations · JSON
• Circle algorithms · JavaScript
• Reproduction script · Node.js
• File sizes and SHA-256 checksums · JSON

The JSON stores each mask as inclusive column ranges for every row. For example, [2, 4] means columns 2, 3 and 4. Both column and row indices start at zero. The CSV summarizes counts and differences; the manifest records each other file’s byte size and SHA-256 checksum.

What we checked

All 64 midpoint masks were checked against a separate calculation that rounds the circle equation’s square-root result to the nearest integer in one octant. We also exhaustively checked disk membership, both neighbor predicates, row totals, reflections, transposition symmetry and set differences. The independent check passed 640 assertion groups. This is a computational check, with no claim of external peer review.

Original code and generated data are released under CC0 1.0. Cited sources retain their own rights. To identify a result, cite this page’s version, radius, method and the linked data file.

Scope, corrections and use for block builds

This reference covers integer radii and integer centers on binary grids. It does not test antialiasing, even-width center-gap layouts, half-integer radii, ellipses, 3D shapes, running time or which outline looks best.

The Minecraft circle generator uses a different size convention: its diameter D uses radius D/2. An 11-block plan therefore uses radius 5.5; the 11-cell research grid above uses radius 5. Do not substitute this example’s rows for the generator’s blueprint just because the widths match. For construction, use the generator’s own row instructions or the circle chart.

This study is published by the operator of the circle tool. The cited authors have not endorsed it. Version 1 files stay fixed; corrections will receive a new version and a dated note. Report a correction with the radius, method and coordinate so it can be reproduced.