# Gird Boxes Intersected by a Circle

General Questions: Given a circle on a grid, what are the coordinates of the boxes it intersects?

Okay, I'm trying to figure out how to create a square circle basically, for example, given the google image circle below:

I want to find the following (apologies for my ms paint) (red point is an example; I want all the boxes):

where the grid boxes are where coordinates are located, instead of at the intersections of the grid lines.

I'm currently using the circle equation:

$x = cx + r * cos(θ)$

$y = cy + r * sin(θ)$

(where $(cx, cy)$ is the center, $r$ is the radius, and $θ$ is the angle)

to obtain points on the circle. I wrote a program to test a bunch of radii, but it does not check for boxes, it uses the traditional coordinate plane, checks a whole bunch of angles, and spits out the number of unique points of the form $( ⌊x⌋, ⌊y⌋)$. The number of unique points appears to be equal to $8r$, but this is the number of unique floored points (not boxes). The above circle intersects 44 boxes. My overall goal, however, is to obtain the coordinates of each box intersected, rather than the number, and that is where I'm stuck. I think that what I need to do is calculate an angle interval, and then check every angle between $0$ and $360$ by adding the interval to $0$ some number of times. So, to sum things up, I need help calculating the coordinates of the grid boxes intersected by a circle (with known radius and center), and I think I can do this by using the parametric equation and an angle interval. Any help is appreciated!

• Maybe you should look at one of those circle drawing algorithm e.g Midpoint circle algorithm and see whether it does what you want. – achille hui Oct 2 '16 at 4:47
• @achillehui that looks like exactly what I'm looking for! Thanks – Socratic Phoenix Oct 2 '16 at 4:54