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

[Shashwat Anand]

@DaveA: thanks for pointing it out.

For a origin-centre circle x**2 + y**2 = r**2, I assumed r to be integer,
however it was r**2 which was integer. A mistake on my part.

On Mon, Nov 16, 2009 at 6:41 AM, Dave Angel <davea at ieee.org> wrote:

> spir wrote:
>
>> 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 =**2
>>> (as
>>>
>>> Origin is the centre of the circle.)
>>> Now I want a table of these points for say r = to upper bound.
>>> So for r =, the only point lying on it is (0,0)
>>> For r =, 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 =pper 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= you would
>> step on (0,2), (1,1), (2,0), (1,-1),... For each pair, simply check whether
>> x² + y² = 2².
>>
>> Got an algorithm used for antialiasing and plotting circle known as
bresanham's algorithm (
http://en.wikipedia.org/wiki/Midpoint_circle_algorithm) but hadn't actually
worked on it.

>
>> * 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
>>
>>
>>
> What you don't know is that the OP's original unstated (and probably at
> that time unknown) requirement included circles of non-integer radius, as
> long as three of the points on such a circle land on integer vertices.  For
> example, the points  (8, 1), (1, -8), (-4, 7).  That little tidbit never
> made it into the thread.
>
> DaveA
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> To unsubscribe or change subscription options:
> http://mail.python.org/mailman/listinfo/tutor
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20091116/a196e935/attachment.htm>