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

[Shashwat Anand]

>
> 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).
>
> 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.

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.
>
>
> The bruteforce code is working for me but that's an unacceptable option. So
I tried pythagorean triplets. But I'm not sure as to where am I doing
mistake.
>>> d = collections.defaultdict(list)
I created a dictionary.
>>> 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)]))
for u = (0,9) and v > u, the triplets are u**2+v**2, v**2 - u**2, 2*u*v. So,
I stored them. However it looks for only half of positive quadrant. set
logic is to remove  duplicate elements. Now for each value (p, q) there will
be seven more possible values i.e. (q, p), (q, -p), (-q, p), (-q, -p), (p,
-q), (-p, q), (-p, -q). In case of either of p or q value = 0, the values
are reduced to 3.
>>> [d[k].append(v) for k,v in s]
I stored all the values.

Hope I did not made this post really messy. I think I'm unable to apply my
logic. How to implement / Can there be better logic, optimizations and
implementations ?
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20091115/71f1e1f6/attachment.htm>