Intersecting a circle with the integer lattice

Question

Looking for a method to find all the integer coordinates on the edge of a circle using a known radius.

The assumption is that we have a known radius $R$ (e.g. $R=254$). How would you calculate all the available integer points on the circle between $0$ and $90$ degrees?

Is there a Java Package that uses Big Decimal that can be used with the above methodology?

Answer 1

Assuming the center of the circle is the origin (or at least a lattice point), you want integer solutions to $x^2+y^2=N(=R^2=254^2)$, or a Gauß lattice point $x+iy\in\Bbb Z[i]$ of norm $R^2$. The existence of such solutions depends on the prime factorization of $N$, that corresponds to possible factorizations of $x+iy$. We can always multiply a solution by $i$ or $-1$ or $-i$ (i.e., swap the $x$ and $y$ and change signs).

• Every factor of $2$ in $N$ gives us $1+i$ as a factor of $x+iy$.
• Every prime factor $p$ with $p\equiv 1\pmod 4$ allows an essentially unique solution of $u^2+v^2=p$ and thereby a factor of $u\pm iv$ of $x+iy$.
• Every prime factor $p$ with $p\equiv -1\pmod 4$ does not have such a decomposition. We can only hope that it appears twice or any even number of times (which it does because $N=R^2$ is a prefect square) and then multiply $x+iy$ by $p$ for each $p^2$.

We find the prime factorization of $N$ as $N=254^2=2^2\cdot127^2$. Following the above, we find exactly the following: $$x+iy = u\cdot (1+i)^2\cdot 127 \qquad \text{with }u\in\{1,i,-1,-i\} $$ i.e., $$ x+iy\in\{254i,-254,-254i,254\}.$$ In other words, one of $x,y$ must be $=0$, the other $=\pm 254$, there are no non-trivial lattice points. As you want to restrict to the range from $0°$ to $90°$, we are left wuth $(254,0)$ and $(0,254)$.

Answer 2

You only need Big Decimal if $R$ is big. For $R$ not too large, not only can you use ordinary integers, you can brute-force the solution.

For example, with $R=254,$ just try each integer value of $x$ from $x=0$ to $x=254,$ and set $s = R^2 - x^2.$ Apply the floating-point square root function to that result, that is, take q = sqrt(s), round the return value q to an integer, set $y$ to the rounded value, and then check whether $y^2 = R^2 - x^2.$ If it is equal, that value of $(x,y)$ is a point on the circle, otherwise there is no such lattice point with that $x$-coordinate.

You can even avoid floating-point calculations entirely if you just "guess" the value of $y$ each time. When $R=254,$ for $x=0$ you know $y=254,$ and you know that $y$ for the next lattice point will be less, so for $x=1$ you guess $y=254- 1 = 253$ and see if $(x,y)$ is a lattice point. Each time you make such a guess, if it turns out $x^2 + y^2 > R^2$ then you decrease $y$ by $1$ and try again with the same $x$; if $x^2 + y^2 < R^2$ then you keep the same $y$ but increase $x$ by $1$; and if $x^2 + y^2 = R^2$ then you remember the fact that $(x,y)$ is a lattice point on the circle, and for your next guess you add $1$ to $x$ and subtract $1$ from $y.$

If you use $64$-bit integers these "brute force" approaches work up to $R \approx 2{,}000{,}000{,}000,$ although somewhere between $R=254$ and $R = 2{,}000{,}000{,}000$ you might find that the brute-force approach takes so much computing time that you want to implement the cleverer solution already explained in another answer (involving the factorization of $R$).