Sean Barrett, February 2011

The following chart represents my analysis of moderately small circles rendered as pixels.

Pixelated Circles

Analysis

What qualifies as a pixelated circle?

Imagine a grid of pixels as a grid of little squares. We consider only circles where the center of the circle falls at the center of a pixel, or where the center of the circle falls at the corner between four pixels.

A circle consists of points which lie within some distance from the center of the circle; this distance is known as the radius of the circle.

For this analysis, I considered a "proper" pixelated circle to be one that contains only pixels whose center point lies within the center of the circle; this distance is also known as the "radius" of the circle (although the corners of the outermost pixels will actually be further than this distance). Alternate definitions, e.g. considering the nearest or furthest point of each pixel, should be considered to see if they produce different results.

"Odd" versus "Even"

As noted above, I consider both circles centered on pixels and circles centered on pixel corners. When considering the bounding box of the circles, due to symmetry, the pixel-centered circles will have bounding boxes that are an odd number of pixels, and the corner-centered circles will have bounding boxes that are an even number of pixels.

In an actual circle, the length of a bounding box side is exactly the diameter of the circle. In all of these circles, the centermost row or column are also exactly that many pixels long. So this number reasonably qualifies as an integer diameter approximation for the circle, and so "odd" and "even" really refers to this integral diameter.

Valid circles: Is that really all of them?

Importantly, we allow the radius to be a non-integer value. However, because there are only discrete pixels that can be considered in or out of the circle, we find that there are only so many non-integer values between any two integers which produce different results. The table above shows all such unique values (up to a particular size of circle).

In general, we can sort the pixels based on their distance from the center; as we increase the radius of the circle, pixels will become part of the circle in that sorted order. Again, this is illustrated in the above diagram; the pixels added at a given step are shown in a different color.

Because of the circle symmetry, there are always 4 or 8 pixels that are truely at the same distance. Sometimes two non-symmetric pixels will also be at the same distance under the chosen center-point metric. When this happens, the two alternatives are shown stacked vertically, and the next step shows the two combined. This is because the two might not be at the same distance under other metrics, so it seemed best to consider them as distinct options.

(The reason you get two non-symmetric pixels appearing at the same time is because the distance from each to the center is identical; e.g. sqrt(x1^2 + y1^2) = sqrt(x2^2 + y2^2). One reason this occurs is if, say, y2=0, in which case it's a pythagoran theorem effect; e.g. a pixel at <3,4> should be the same distance as one at <5,0> because 3^2 + 4^2 = 5^2. This is exactly what happens in the smallest alternation in the "all odd widths" section.)

Preferred circles

The prefered circles shown offer one or two for each possible integer radius, although they mostly are non-integral. They represent my aesthetic judgement of the ones that are most visually pleasing. They may not represent other people's aesthetic judgements; if we really cared we should make a poll or something.

The most obvious aesthetic criteria is that I dislike circles which have "sharp" one-pixel protrusions. This is most obvious on odd-sized circles, with the 4-way pixels that lie on the center diameters; when you first reach a new integer size, these are the only pixels that qualify (this is why you sometimes see terrible circles drawn by computers--they used an integer size and a less-than-equal rule).

A similar case occurs on the diagonals, although sometimes I allow those through -- one each of the 8, 9, and 11-diameter circle variations have this artifact.

I also prefer to avoid circles which look more like pixelated octagons; this isn't an issue as circles get large enough, but you can still see them occurring in the all-valid list (such as the third-to-last even-sized). In fact, the reason the 8 and 9 variations with the displeasing protruding corner appear is because the other best variation looks like an octagon, and I preferred to give the reader the choice between the two artifacts.