1
$\begingroup$

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!

  • 0
    To clarify: are you asking how to find lattice points that cross a circle of arbitrary radius?2010-11-29

2 Answers 2

2

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. Discard those cells of which closest point is further.

  • 0
    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.2013-07-05