Sunday, March 21, 2010

Grid Squares in a Circle

I know that it's a minor operation, but for a long time I couldn't help but wonder if there were an optimized way of finding out which squares in a grid fall within a given radius. However, because it is such a minor operation and because the brute force method works adequately, I never actually went out of my way to try and solve this problem -- until now. Boredom is a wonderful thing. . .

First off, the brute force approach:

Given an origin (x0, y0) and a radius r, the maximum orthogonal extents of a circle is equal to (x0±r, y0±r). Given those extents, coordinates whose distance from the origin are less than or equal to the radius are within the circle.

def brute_coords(r):
    coords = []

    for y in range(-r, r+1):
        for x in range(-r, r+1):
            if math.hypot(x, y) <= r:
                coords.append((x, y))

    return coords

Very easy and with relatively small circles it is sufficiently fast. However, there should be a way to do this without even considering squares outside of the circle. There is and the solution comes thanks to the Pythagorean Theorem. Specifically, the circle's radius is the hypotenuse of a triangle and the distance along the x-axis is another length. The number of squares above and below that axis is equal to the final length. Thus we iterate along the minimum and maximum x-coordinates and calculate the verticals.

def smart_coords(r):
    coords = []
    for x in range(-r, r+1):
        dy = int(math.sqrt(r*r - x*x))
        for y in range(-dy, dy+1):
         coords.append((x, y))
    return coords

With small radii, such as a character's vision radius in a roguelike, the performance difference is a few milliseconds at most, on my system. With a radius of 100, smart_coords is twice as fast. At 1000, it takes 12 seconds, while brute_coords takes 17. That's pretty good!

As for whether the optimization is worthwhile in practical applications, I have no idea. I haven't made any real comparison and probably won't bother to. I will use it, though, if for no other reason than because it is better and it is not a very complex solution.

Followers