Pixel Circle Generator

There is no such thing as a circle on a square grid, only the best argument for one, and the argument is always the same: draw the real circle, then keep every cell whose middle falls inside it. That single rule handles both awkward cases at once. An odd diameter puts one block at the centre and the ring comes out symmetrical about it; an even diameter puts the centre on a corner, four blocks meet in the middle, and the ring is symmetrical about that instead. Neither is a special case in the code, and neither needs a fudge. What you choose after that is how much of the disc to keep: the thin outline is the cells with a face pointing outwards, which is the ring builders draw; the thick outline also keeps the cells with only a corner pointing out, so a wall built on it has no diagonal seams to see through; and the filled version is the whole disc, for a floor or a roof.

How it is calculated

(x − c)² + (y − c)² ≤ (d / 2)², where c = (d − 1) / 2

Number the cells from zero. The middle of cell x sits at x, the middle of the grid sits at (d − 1) / 2, and the circle has radius d / 2. A cell is in the disc when the distance between those two points is no greater than the radius. For an odd diameter this is exactly the count OEIS records as A036704, the Gaussian integers with modulus at most n + 1/2 — 1, 9, 21, 37, 69, 97 for diameters 1, 3, 5, 7, 9 and 11. For an even diameter the offsets are half-integers instead, which is why the same formula gives a sensible ring without a separate branch.

Source: OEIS A036704 — "a(n) = number of Gaussian integers z=a+bi satisfying |z| <= n+1/2", which counts the grid cells a circle of diameter 2n+1 covers: 1, 9, 21, 37, 69, 97, 137, 177, 225, 293, 349, 421

Questions people ask

Which outline should I build?

The thin one, unless you can see through it. It is the cells of the disc with at least one flat side facing outwards, so it steps diagonally at the shoulders — fine for a floor marking or a pond edge, and fine for a wall you only ever look at straight on. The thick one adds the cells that touch the outside at a corner only, which closes every diagonal, so a wall built on it is solid from any angle. It costs exactly four blocks for every step of the diameter minus one.

Why is a diameter of three a solid square?

Because at that size there is nothing else it could be. Every cell of a three by three grid has its centre within one and a half blocks of the middle, so every cell is in the disc. The outline takes the middle out again and leaves you a ring of eight. Circles only start to look like circles at about five across, and they only start to look good at nine or more.

Do the even diameters really work?

Yes, and they are not a compromise. With an even diameter the centre of the grid falls on the corner where four blocks meet rather than in the middle of one, so the cell centres sit half a block off the axis. The shape stays symmetrical about both axes and about the diagonal, and the top and bottom of the ring come out flat and even instead of pointed. A four across circle is twelve blocks; a six is twenty.

How many blocks will the filled circle take?

The count is printed under the grid, and for odd diameters it is a sequence somebody catalogued long before anyone built anything out of blocks: 1, 9, 21, 37, 69, 97, 137, 177, 225 for diameters 1 through 17. It grows with the square of the diameter, so doubling the size of a floor costs four times the material.

Is this Bresenham's circle?

Not quite, and the difference is worth knowing. Bresenham's algorithm walks an integer radius one step at a time and decides each step with integer arithmetic, which was the point in 1977. This page tests every cell against the circle of radius d / 2 instead. For some diameters the two agree exactly; for others they pick a slightly different ring, because they are drawing circles of slightly different radius. Testing every cell is slower and completely uninteresting on a grid this small, and it has the advantage of handling even diameters without a second algorithm.

Related tools