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.
