Circle fill on a grid

from Red Blob Games
11 Nov 2019

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(1)}}

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:

{{radius.toFixed(1)}}{{radius.toFixed(1)}}
All tiles with distance ≤ {{radius.toFixed(1)}}
bool inside_circle(Point center, Point tile, float radius) {
    float dx = center.x - tile.x,
          dy = center.y - tile.y;
    float distance = sqrt(dx*dx + dy*dy);
    return distance <= radius;
}

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

This is a fine solution if the grid is small. The test is fairly cheap. However, there are three improvements we can make to run faster. The first is to avoid the square root. Even though sqrt is much faster than it used to be, it's unnecessary in this case. The condition distance < radius is true exactly when if distance² < radius² is true, since both numbers are non-negative.

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;
}

This is a code optimization. The other two are algorithm optimizations.

 2  Bounding box#

We're checking distances on the entire grid. We can save a lot of time by checking a much smaller area, the bounding box around the circle. We don't look at the rest of the grid.

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

In this case, the bounding box is a square. Try resizing the circle to see how the bounding box changes.

int top    = floor(center.y - radius),
    bottom =  ceil(center.y + radius),
    left   = floor(center.x - radius),
    right  =  ceil(center.x + radius);

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

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

If you also need to clip the circle to a rectangle, the simplest approach is to check that (x,y) is inside the rectangle before drawing each tile, but a more streamlined solution is to modify the calculation of the bounds so that every visited tile is always inside bounds:

int top    = max(bounds.top    , floor(center.y - radius)),
    bottom = min(bounds.bottom ,  ceil(center.y + radius)),
    left   = max(bounds.left   , floor(center.x - radius)),
    right  = min(bounds.right  ,  ceil(center.x + radius));

 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(1)}} with a bounding circle

For each row we'll find the left and right tile using the Pythagorean Theorem. Then we can fill all the tiles in between. Using a bounding circle, we no longer need the distance check, because every tile is in the circle.

int top =    center.y - radius,
    bottom = center.y + radius;

for (int y = top; y <= bottom; y++) {
    int   dy  = y - center.y;
    float dx  = sqrt(radius*radius - dy*dy);
    int left  = ceil(center.x - dx),
        right = floor(center.x + dx);
    for (int x = left; x <= right; x++) {
         // draw tile (x, y)
    }
}

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. Note the use of ceil and floor instead of round.

I've never had to worry about the sqrt call performance, but if your profiler says it's a problem (especially on non-x86), you can precompute the dx values for each row for the circle sizes you care about:

dx = [
  …
];

 4  Outlines#

In the previous section we calculated the left and right boundary for each scan line. This gives us a way to draw circle outlines without filling the circle. For each row, draw the left and right tiles but don't draw the tiles in between:

Partial outline at radius {{radius.toFixed(1)}}
int top    = ceil(center.y - radius),
    bottom = floor(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  = center.x - dx;
        right = center.x + dx;
    // draw tile (left, y)
    // draw tile (right, y)
}

Unfortunately … this doesn't work! It leaves gaps at the top and bottom of the circle:

Circle outline at radius {{radius.toFixed(1)}}

The bad news is that the logic only works reliably when the triangle's angle is ≤45°. The good news is that circles are symmetric so we can reuse the same logic to draw the top and bottom parts of the circle in the same loop.

Let's restructure the code. Iterate over r, the length of the shorter leg of the right triangle. From r we calculate d, the longer leg of the right triangle. With the lengths of the legs we can draw 8 tiles at once:

for (int r = 0; r <= floor(radius * sqrt(0.5)); r++) {
    int d = int(floor(sqrt(radius*radius - r*r)));
    // draw tile (center.x - d, center.y + r)
    // draw tile (center.x + d, center.y + r)
    // draw tile (center.x - d, center.y - r)
    // draw tile (center.x + d, center.y - r)
    // draw tile (center.x + r, center.y - d)
    // draw tile (center.x + r, center.y + d)
    // draw tile (center.x - r, center.y - d)
    // draw tile (center.x - r, center.y + d)
}

Here are the eight right triangles generated at each step:

Circle outline at radius {{radius.toFixed(1)}}

There will be some tiles that are drawn more than once. If this is a problem in your application, you'll want modify the algorithm to check for duplicates at the boundaries (r = 0 and r = d).

Here's the result:

Circle outline at radius {{radius.toFixed(1)}}

 5  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:

Circular fill to radius {{radius.toFixed(1)}} vs {{(radius+0.5).toFixed(1)}}

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(1)}}

For best results, the sides of the circle should be at the boundary between tiles , not in the middle of a tile .

 6  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], or explained visually here[5].

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(1)}},{{center.y.toFixed(1)}} with radius {{radius.toFixed(1)}}

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

There are two techniques on this page that are useful elsewhere:

  1. Using a bounding box and then checking if the tile is inside the shape: also useful for triangle fills, as described on the ryg blog[7].
  2. Calculating the left and right tiles on a single row and then filling that span: also useful for triangle fills, also described on the same page of the ryg blog[8].

The left/right scan line approach visits fewer tiles, but is harder to parallelize than the bounding box + check approach.

Email me , or tweet @redblobgames, or comment: