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

[Dave Angel]

Shashwat Anand wrote:
> How to find all possible integer co-ordinates lying on a circle of given
> radius 'r'.
> If given the upper bound of 'r', I want to calculate all given co-ordinates
> lying for 0 <= r <= n
>
> Let's say the upper bound of radius is 5
> All possible results are:
> 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)
>
> Also for a particular radius, lots of possible combination of (x, y) is
> possible so best datastructure could be defaultdict for further operations
> IMHO.
> So my desired output is:
> defaultdict(<type 'list'>, {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)]})
>
> My approach using pythagorean triplets:
>   
>>>> d = collections.defaultdict(list)
>>>> s = list(set([((u*u + v*v), (v*v - u*u, 2*u*v)) for u in range(10) for v
>>>>         
> in range(u+1, 10)]))
>   
>>>> [d[k].append(v) for k,v in s]
>>>>         
> However it sure is wrong and fails in my case.
>
> Any suggestions as to how can I reach my desired goal, or are there any
> other options to tackle this problem?
>
>   
Your "all possible results" isn't even close to all the points that 
match the 0<= r <= 5.  And I don't know how either spec justifies the 
set logic you quoted.

So I have to start over.  I think you're trying to find all integer 
co-ordinates which lie on or within a circle of given radius (sample 5).

Taking only the first quadrant to keep the number of values smaller, I see:

( 0 , 0 ) ( 0 , 1 ) ( 0 , 2 ) ( 0 , 3 ) ( 0 , 4 ) ( 0 , 5 )
( 1 , 0 ) ( 1 , 1 ) ( 1 , 2 ) ( 1 , 3 ) ( 1 , 4 )
( 2 , 0 ) ( 2 , 1 ) ( 2 , 2 ) ( 2 , 3 ) ( 2 , 4 )
( 3 , 0 ) ( 3 , 1 ) ( 3 , 2 ) ( 3 , 3 ) ( 3 , 4 )
( 4 , 0 ) ( 4 , 1 ) ( 4 , 2 ) ( 4 , 3 )
( 5 , 0 )

To find them, just write a doubly nested loop, each with range from 
-radius to radius, checking x*x + y*y <= radius*radius.  Add to the 
result set, each value that meets the comparison.


There are some optimizations you can do, but first get it working in the 
form you want.


DaveA