Circle fill on a grid

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:

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:

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.

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

int top    =  ceil(center.y - radius),
    bottom = floor(center.y + radius),
    left   =  ceil(center.x - radius),
    right  = floor(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    ,  ceil(center.y - radius)),
    bottom = min(bounds.bottom , floor(center.y + radius)),
    left   = max(bounds.left   ,  ceil(center.x - radius)),
    right  = min(bounds.right  , floor(center.x + radius));

The distance filter approach also works for other shapes. On this page I find all hexagons inside a circle by using a distance test.

 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:

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    =  ceil(center.y - radius),
    bottom = floor(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 may be slightly slower than the bounding box code, so I prefer the bounding box approach when filling circles. But this code will be useful when constructing circle outlines in the next section.

 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:

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

for (int y = top; y <= bottom; y++) {
    int dy = y - center.y,
        dx = 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:

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

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:

 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:

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:

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

 6  Cones / sectors#

A "cone" view in 2D is called a sector^[3]. It's all tiles that fit in the circle and are within some range of angles.

One way to calculate this is to calculate the angle for a tile, using atan2(). If the angle is within the desired angle range, then include the tile in the output. However, that is conservative. A more permissive algorithm is to calculate the angle at each of the tile's four corners. If any of those angles are within the desired angle range, then include the tile in the output.

Calculating angle differences is a little tricky because of wraparound; I use this code.

I'm not sure this output matches what people want from a cone algorithm.

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

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:

If you're always using integer tile positions and half-integer radius, you can optimize the inside_circle function by using integer math only:

bool inside_circle(Point center, Point tile, int diameter) {
    int dx = center.x - tile.x,
        dy = center.y - tile.y;
    int distance_squared = dx*dx + dy*dy;
    return 4 * distance_squared <= diameter*diameter;
}

Raph Levien recommends John Hobby's work on digitization of shapes^[7] 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^[8].
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^[9].

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