Number of cells inside a circle

Question

Suppose we have a circle with diameter `r˙ whose center is in the center of a cell. I would like to calculate how many cells are inside this circle (even if only a fraction of the cell is inside). How can I do this?

Currently I used other cell's center points and checked if they fall in the diameter zone but obviously this doesn't work for cells where only corners are inside but not the centers.

So for the example below the correct number is 21 (with my current method I get 9).

Answer 1

Suppose the four corners of a cell are P1, P2, P3, P4. Let M1, M2, M3, M4 be the mid-points of the sides of the cell. Then the cell "touches" the circle if (and only if) at least one of the eight points P1, P2, P3, P4, M1, M2, M3, M4 is inside the circle.

The pseudocode would be something like this:

inputs: 
   cell with corners P1, P2, P3, P4
   circle center point C
   circle radius r

if distance(P1, C) < r then return true;
if distance(P2, C) < r then return true;
if distance(P3, C) < r then return true;
if distance(P4, C) < r then return true;

M1 = (P1 + P2)/2;   if distance(M1, C) < r then return true;
M2 = (P2 + P3)/2;   if distance(M2, C) < r then return true;
M3 = (P3 + P4)/2;   if distance(M3, C) < r then return true;
M4 = (P4 + P1)/2;   if distance(M4, C) < r then return true;

return false;

This code is very inefficient -- it's written for clarity, not speed. Many optimizations are possible. For example, you should work with squared distances, to avoid calculating square roots, and you can often avoid testing a cell because you know the test results for some of its neighbours.

Answer 2

Take $\frac{1}{8}$ of the circle, the sector starting at angle $0$ and ending at angle $\pi/4$. Suppose the cell has size $1$ to ease the counting.

You have to count things separately. So you have always $1$, the center piece. Then the radius of the circle will span horizontally to the right, giving a number of additional squares, that the integer part of $(2r-1)/2$. Multiply by 4 (for each direction). For diagonals you have the same, but with $\sqrt{2}$ involved: $int(\frac{2r-1}{\sqrt{2}})$. Again take 4 times that number. Finally, count the number of points in the grid that are not exactly in the perimeter of the sector. Each of those point will be a cell. Multiply by 8 and sum.