Circle fill on a grid

from Red Blob Games
11 Nov 2019

Table of Contents

Sometimes I want to find find all grid locations in a circular area. For example, if a player is standing in a field and we want to know every tile the player can toss a ball to, we'll want to find all locations within a certain distance:

Circular fill to radius {{radius.toFixed(2)}}

How can we implement this?

 1  Distance test#

A circle is all points a given distance from the center. A filled circle is all points with that distance or lower:

We can solve this problem with a distance test. Check each tile and calculate the distance to the circle's center. If it's less than the radius, then mark it. Here are the distances from the center to each tile:

Circular fill to radius {{radius.toFixed(2)}}
bool inside_circle(Point center, Point tile, float radius) {
    float dx = center.x - tile.x,
          dy = center.y - tile.y;
    float distance_squared = dx*dx + dy*dy;
    return distance_squared < radius*radius;
}

for (int y = 0; y < height; y++) {
    for (int x = 0; x < width; x++) {
        if (inside_circle(center, Point(x, y), radius)) {}
    }
}

This is a fine solution if the grid is small. The test is fairly cheap. However, there are two improvements we can make to run faster:

 2  Bounding box#

A bounding box is a rectangular area that covers the shape we care about. In this case, it's a a square that's just big enough to include the circle.

Circular fill to radius {{radius.toFixed(2)}} with a bounding box

Instead of checking all tiles on the grid, check only the tiles inside the box.

int top = max(0, center.y - radius),
    bottom = min(height, center.y + radius),
    left = max(0, center.x - radius),
    right = min(width, center.x + radius);

for (int y = top; y <= bottom; y++) {
    for (int x = left; x <= right; x++) {
        if (in_circle(radius)(center, Point(x, y), radius)) {}
    }
}

This is easy and it's a big win, so I recommend it.

 3  Bounding circle#

We can go one step further. Instead of a bounding box, we can use a bounding circle. Each row of the circle will have a different width. We use the Pythagorean Theorem to calculate the width. There's a right triangle formed with the circle radius as the hypotenuse and the row as one leg of the triangle. The other leg of the triangle will tell us the width of the row.

Drag the row selector to see the bounds for that row:

Circular fill to radius {{radius.toFixed(2)}} with a bounding circle

When we use a bounding circle, we no longer need the distance check, because every tile is in the circle!

int top = max(0, center.y - radius),
    bottom = min(height, center.y + radius);

for (int y = top; y <= bottom; y++) {
    int dy = y - center.y,
        dx = int(floor(sqrt(radius*radius - dy*dy)));
    int left = max(0, center.x - dx),
        right = min(width, center.x + dx);
    for (int x = left; x <= right; x++) {}
}

This code will fill a circle. The code is slightly longer and might be slightly slower than the bounding box code but it gives you the precise shape of the circle. If you are concerned with the sqrt call being slow (especially on non-x86), precompute the dx values for each row for the circle sizes you care about:

dx = [
  …
];

 4  Aesthetics#

Regardless of which approach you use, I've noticed the circles seem to look nicer when the radius is 1.5, 2.5, 3.5, etc. than when it's 1.0, 2.0, 3.0, etc. Compare:


Set radius to:
Circular fill to radius {{radius.toFixed(2)}} vs {{(radius+0.5).toFixed(2)}}

Josh Horowitz has investigated this more[1] and found that it really does help to set the radius to N.5 instead of N.0.

@JobvdZwan says[2] that when the radius is N.0 instead of N.5, the circles look nice when centered on the vertices instead of the tiles:

Circular fill to radius {{radius.toFixed(2)}}

 5  More#

I usually use and share the simplest approach I can find.

Circle fills are simpler than circle outlines. The usual approach for circle outlines is the Bresenham algorithm[3]; it's optimized for CPUs without floating point. If you want to understand how Bresenham's circle algorithm works, see it explained step by step here[4].

The circle fill algorithm can be extended to work when the circle center isn't on a tile, but the circles don't look as nice. Try moving the center around:

Circle at {{center.x.toFixed(2)}},{{center.y.toFixed(2)}} with radius {{radius.toFixed(2)}}

Raph Levien recommends John Hobby's work on digitization of shapes[5] but I haven't read through it.

Email me, or tweet @redblobgames, or comment: