Simple method for detecting grid intersection with circle I have a uniform grid of square cells and a point on that grid.  I want to calculate the intersection of cells on the grid, with a circular area centered on the point, with a radius R.
Does anyone know of an efficient way of doing this?
Thanks!
 A: I am perhaps replying late, but I was googling the same question right now :-)
Provided the number of expected cells you cross is "small", you can compute bounding box for all cells which can touch rectangel bounding the circle; if the circle is at $x_r$ and $y_r$, you get some $i_{\min}$, $j_{\min}$, $i_{\max}$, $j_{max}$. Then walk through all cells with coordinates $(i,j)\in\{i_{\min},\cdots,i_{\max}\}\times\{j_{\min},\cdots,j_{\max}\}$ and see if it its closest point $p_{ij}$ (draw it on paper to see which one it is) satisfies $|p_{ij}|^2<r^2$. Discard those cells of which closest point is further.
A: As an addition to the solution of @eudox, you can also only check the top right corner of the circle (provided that the coordinates of the cells's corner point to the bottom-left). When a cell is inside, then add the other three corners as well. With this, you don't need to find the closest point. 
A cell that could be missed in an edge case, is the most outer cell to the right (if slightly graced).
C#/Unity code example:
int xMin = Mathf.FloorToInt(pos.x - radius);
int xMax = Mathf.CeilToInt(pos.x + radius);
int xCenter = xMin + (xMax - xMin) / 2;
int yMin = Mathf.FloorToInt(pos.y - radius);
int yMax = Mathf.CeilToInt(pos.y + radius);
int yCenter = yMin + (yMax - yMin) / 2;

float radiusSquared = radius * radius;

// The trick here is that we only look at a quarter of the circle.
// As a circle is symmetrical, we can add the three other points of the other three quarters.
for (int y = yMin; y <= pos.y; y++)
{
    for (int x = xCenter; x <= xMax; x++)
    {
        if ((new Vector2(x, y) - pos).sqrMagnitude < radiusSquared)
        {
            m_PointsInRadiusResult.Add((x, y));
            m_PointsInRadiusResult.Add((xCenter-(x-xCenter), y));
            m_PointsInRadiusResult.Add((x, yCenter+yCenter-y));
            m_PointsInRadiusResult.Add((xCenter-(x-xCenter), yCenter+yCenter-y));
        }
        else
        {
            break;
        }
     }
}

