Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


share|cite|improve this question
To clarify: are you asking how to find lattice points that cross a circle of arbitrary radius? – J. M. Nov 29 '10 at 12:44

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.

share|cite|improve this answer
there's a minor problem with this algorithm - it doesn't find cells where the circle "grazes" one edge of the cell (i.e. enters and leaves on the same edge). – Alnitak Jul 4 '13 at 15:35
The algorithm will find it, provided you compute $p_{ij}$ correctly: it the circle's center is in the same grid row or column as the cell in question, the closest point $p_{ij}$ will be on the cell edge, not in the corner (one coordinate will be the same as the center's coordinate). – eudoxos Jul 5 '13 at 12:26
Right, I interpreted your "closest points" as meaning the cell corners. In my implementation I use a simple combination of min and abs operators to find the closest corner, and then have a special (simple) case when looking at the central column and row to see if that edge is within the circle's radius. – Alnitak Jul 5 '13 at 13:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.