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