I'm trying to determine if there is a way to calculate the number of points, considered as intersections of a grid, and that either lie inside or on the circumference of a circle. The circle is centered on the origin and has radius R. I've defined the points as P={Px,Py} = {x1+Cw,y1+Dh} where C and D are any given pair of integers. Accordingly they should satisfy the equation
$(x1+Cw)^2+(y1+Dh)^2 <= R^2$
$x1$, $y1$, $w$, $h$, and $R$ are all constant.
I'm interested in approaches that give exact answer and are applicable to data sets like $R = 100,000$, $W=1$, $H$ = 1 implying at least a billion points. From a computational point of view I'd be interested in any ideas that could help speed up the process. Please note too I'm interested in exact solutions, not approximations.
I may have misunderstood the problem. If so, please advise.
Let $\lfloor r\rfloor$ denote the floor of $r$
(i.e. the largest integer $\leq r).$
I am assuming that the circle is of radius $R$ and centered at the origin [i.e. centered at (0,0)].
Bypassing any attempt at elegance, I will calculate the grid points on the positive portion of the $x$ axis, and then multiply that by 4. By symmetry, that should give all grid points that are on the $x$ or $y$ axis, except for the origin. I will then add 1 for the grid point that represents the origin.
Thus, this first computation is $T_1 = 1 + \left(4 \times \lfloor R \rfloor\right).$
Next, I will compute all the grid points that are in the interior of the 1st quadrant. By symmetry, this computation will then be multiplied by 4 and then (subsequently) added to the first computation.
Let $h$ go from 1 to $\lfloor R \rfloor,$ and
let $f(h)$ denote the number of grid points interior to the 1st quadrant when $y = h.$
From the pythagorean theorem, we have that
$f(h) = \lfloor \sqrt{(R^2 - h^2)}\rfloor.$
Thus the 2nd computation is
$\displaystyle T_2 = 4 \times \left[\sum_{h = 1}^{\lfloor R \rfloor} f(h)\right].$
The final computation is $T_1 + T_2.$