4 ms·
The "clever way to do the circle calculation that only used addition and subtraction", which the article attributes to Apple employee Bill Atkinson in 1981, is
by netdog 16y ago
The "clever way to do the circle calculation that only used addition and subtraction", which the article attributes to Apple employee Bill Atkinson in 1981, is in fact a variant of the Bresenham algorithm, devised in 1962 by Jack Bresenham at IBM, when Bill was still a kid.
see http://en.wikipedia.org/wiki/Bresenham_algorithm http://en.wikipedia.org/wiki/Bresenham_algorithm
- Luc 16y agoThe circle version is here on Wikipedia (it includes the 1+3+5... trick): http://en.wikipedia.org/wiki/Midpoint_circle_algorithm http://en.wikipedia.org/wiki/Midpoint_circle_algorithm Generalized to ellipses: http://homepage.smc.edu/kennedy_john/belipse.pdf http://homepage.smc.edu/kennedy_john/belipse.pdf
- jcl 16y agoHmm... The Wikipedia article for the circle-drawing algorithm indicates that while it uses the same error-accumulation strategy as Bresenham's line-drawing algorithm, it was not actually invented by Bresenham. http://en.wikipedia.org/wiki/Midpoint_circle_algorithm http://en.wikipedia.org/wiki/Midpoint_circle_algorithm I'm not sure how correct this is, as I don't have access to the full text of the papers involved. But it looks like if Bresenham did write the algorithm (and wasn't beaten to it by, say, Pitteway as Wikipedia implies), it wasn't until his 1977 paper, "A linear algorithm for incremental digital display of digital arcs".