spir wrote:
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.Le Sun, 15 Nov 2009 09:11:16 +0530, Shashwat Anand <anand.shash...@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². * 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
DaveA _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
