alt Hacker NewsThe circle outlining one seems interesting to me. I definitely didn't read the algorithm ahead of time, and I'm probably not as smart as a revolutionary genius computer scientist, but I thought of 2 basic algorithms in a few minutes.
You could iterate over the degrees 0 to 360, use trig functions to figure out where the point at that angle is, and plot the closest point. Might need to be a bit tricky about the step size, but I bet you could compute a decent guess from the radius using more trig functions. Of course that probably doesn't work if you don't have floating point and trig functions.
You could also split it into four quadrants. Plot each of the top, bottom, right, and left points by direct computation of adding/subtracting the radius, then for each quadrant, you start from the computed point, check 3 specific points in the appropriate direction for which way you're going in that quadrant, plot whichever one is closest to the radius away from the center, then repeat from that plotted point until you reach the computed point for the next quadrant. It would be tedious and repetitive, but should be doable. You could probably also avoid computing square roots by comparing the squares instead. So I guess you'd want something based on that idea to do it fast on 90s hardware.
Replies
An optimal algorithm is shockingly simple
Your second one is somewhat in the right direction, I think. My guess would be that you split the circle into eights, that keeps the tangent slope between zero and one. Then you can go along one axis from 0 to sin(45°) times the radius and the value along the other axis will always either stay the same or change by one as the derivative is between zero and one. As you move along your primary axis, you generally keep the value along the secondary axis unchanged but you accumulate the error. When the error crosses 0.5, you move one pixel along the secondary axis and adjust the error accordingly. And of course you always draw eight mirrored and rotated pixels. In some way an adaptation of the Bresenham algorithm for drawing lines.
Exactly! I used this question regularly. It wasn’t a gotcha question or even an impossible-without-experience question as the author thinks. It was a show me HOW you think through something question. There are a lot of ways to solve it, from scanline to sin/cos to using the circle equation, but you can _progress_ from naive to advanced solutions, and all solutions above plus the DDA or Bresenham solutions have symmetries (hint: more than four quadrants are symmetrical) that you can use to optimize it. A practiced interviewer can learn a lot about the candidate with this question.
Your second idea is pretty much the direction the classic solution takes: walk along the curve incrementally, avoid square roots, and use symmetry to fill in the other parts