Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|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

1 Answer 1

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|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

 
discard

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