Hacker News new | ask | show | jobs
by ventana 17 days ago
I don't believe you need trig for that, it actually makes it harder if you try to iterate the angle. I believe the expected solution is to start at (R, 0) which is known belongs to the circle, and go left/top, choosing the pixel closest to the circle on each step, which does not require any floating point arithmetic.
2 comments
HarHarVeryFunny 17 days ago
The problem is under-specified both in terms of requirements and any implementation restrictions.

Given the lack of difficulty of the other questions (and this being pre-internet, targeted for an intern), I don't think the interviewer can have been expecting too much sophistication.

The other obvious way do do it, only requiring the same minimal realization that this is about triangles (with radius as hypotenuse) is to use r^2 = x^2 + y^2 and iterate x=0..r deriving y. You could do it without sqrt if they stipulated that.

link
vikingerik 17 days ago
Right, iterating through pixels is better. The tricky part about iterating the angle is that you need to choose the step size correctly or else you could skip pixels. Like if you iterate in 1-degree increments, you'll plot 360 pixels total, but the size of the circle on your canvas might be more than 360 pixels wide. I'm sure there's a way to choose the angle iteration step size to guarantee not skipping pixels, but you'd often duplicate work and re-plot the same pixel twice.

So yes, start at (R, 0), increment the y-coordinate each time and possibly decrement the x-coordinate, until x=y which will be at 45°. If the circle's center is an integer on the pixel grid, you can reflect/translate each pixel in that first octant to all eight as you go. If the center is fractionally positioned, you'd have to calculate it all the way around, iterating primarily on y or x depending on the location.

link
HarHarVeryFunny 17 days ago
> The tricky part about iterating the angle is that you need to choose the step size correctly or else you could skip pixels

Yes, although the problem statement doesn't say if they care. In this case they are only giving a draw_pixel() primitive, but if you had draw_line() then you could use that to avoid gaps.

The other thing is that this is 90's era, with a CGA display (640x200) being mentioned in the previous question, so I'm not sure there's enough resolution to draw a real circle without gaps unless you do resort to some hack to ensure there aren't any!

link