[Tutor] Find Integer co-ordinates lying on a circle

[spir]

Le Sun, 15 Nov 2009 09:11:16 +0530,
Shashwat Anand <anand.shashwat at gmail.com> s'exprima ainsi:

> > No, I'm trying to find all integer co-ordinates which lies on a circle.  
> Say for a circle of radius 5 the co-ordinates are [(5, 0), (0, 5), (-5, 0),
> (0, -5), (3, 4), (4,3), (3, -4), (4, -3), (-3,
> 4), (-4, 3), (-3, -4), (-4, -3)] which lies on circle x**2 + y**2 = 5**2 (as
> Origin is the centre of the circle.)
> Now I want a table of these points for say r = 0 to upper bound.
> So for r = 0, the only point lying on it is (0,0)
> For r = 1, the points lying on them (the circle x**2 + y**2 = 1**2) is [(1,
> 0), (0, 1), (-1, 0), (0, -1)]
> And so forth.
> 
> Thus the table shows the points (x,y) which are lying on the circle of
> radius 'r'.
> 
> radius 'r' - (x, y)
> 0 - (0, 0)
> 1 - (1, 0), (0, 1), (-1, 0), (0, -1)
> 2 - (2, 0), (0, 2), (-2, 0), (0, -2)
> 3 - (3, 0), (0, 3), (-3, 0), (0, -3)
> 4 - (4, 0), (0, 4), (-4, 0), (0, -4)
> 5 - (5, 0), (0, 5), (-5, 0), (0, -5), (3, 4), (4,3), (3, -4), (4, -3), (-3,
> 4), (-4, 3), (-3, -4), (-4, -3)
> 
> Which is correct. I'm not trying to find all integer co-ordinates within a
> circle but trying to create a table of points lying on the circle of radius
> 'r', varying the radius from '0' to upper bound 'r'.
> The bruteforce can be done as:
> 
> #R = upper bound
> for r in range(0, R+1):
>     for x in range(0, R+1):
>         for y in range(0, R+1):
>             if x**2 + y**2 == r**2:
>                 #store them
> 
> However the complexity reaches O(n**3) and it's not optimized at all. So I
> though of using pythagorean triplets.

Interesting! As some said previously, you only need to find point for a quadrant, then extrapolate.
I can see two approaches to find _integer_ coordinate pairs on a circle of given radius:

* Walk the circle itself. I mean start with a point on it (0,r), then find an algorithm to walk step by step (unit by unit) while keeping as close as possible to the circle. This means rounding to next int. Eg for r=2, you would step on (0,2), (1,1), (2,0), (1,-1),... For each pair, simply check whether x² + y² = 2².

* Solve the above equation in integer domain, again by an approaching algorithm, maybe taking profit of know points (where either x or y is 0).

I guess such approaches can  be interesting, compared to brute force, only in case of very big number of radii or very big radii.

Denis
--------------------------------
* la vita e estrany *

http://spir.wikidot.com/