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