Re: [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
_______________________________________________
Tutor maillist  -  Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor