drawing circle without floating point calculation

Question

This is common interview question (according to some interview sites) but I can find no normal answers in Internet - some are wrong and some point to complex theory I expect not looked for in interview (like Bressenham algorithm).

The question is simple:

The circle equation is: x^2 + y^2 = R^2. Given R, draw 0,0-centered circle as best as possible without using any floating point (no trigo, square roots, and so on, only integers)

Answer 1

Honestly, isn't the Midpoint circle algorithm enough? Just mirror it in all quadrants. And by all means no -- unless you're trying to get a job as a window application tester, Bresenham's Line Algorithm isn't complex theory.

Answer 2

From the second method on this page:

for each pixel, evaluate x²+y² and see if it is in the range from R²-R+1 to R²+R inclusive. If so, color the pixel on the screen, and if not, don't.

Further details and explanation given on the aforementioned page, but the crux is that you are looking for pixels that are a distance between R-0.5 and R+0.5 from the origin, so the distance squared is x²+y² and the threshold distances squared are R²-R+0.25 and R²+R+0.25.

For other methods, Google "draw a circle using integer arithmetic only".

Answer 3

Here would be my interview answer (no research, this is on the spot)...

Set up two nested for loops that collectively loop over the square defined by {-R, -R, 2R, 2R}. For each pixel, calculate (i^2 + j^2) where i and j are your loop variables. If this is within some tolerance to R^2, then color that pixel black, if not then leave that pixel alone.

I'm too lazy to determine what that tolerance should be. You may need to store the last calculated value to zero-in on which pixel best represents the circle... But this basic method should work pretty well.

Answer 4

You can easily calculate the x in x^2= r^2- y^2 using the first order Taylor approximation

sqrt(u^2 + a) = u + a / 2u

This is a program for that in Mathematica (short, but perhaps not nice)

 rad=87; (* Example *)
 Calcy[r_,x_]:= ( 
     y2 = rad^2 - x^2;
     u = Ordering[Table[ Abs[n^2-y2], {n,1,y2}]] [[1]]; (* get the nearest perfect square*)
     Return[ u-(u^2-y2)/(2 u) ]; (* return Taylor approx *)
 )

 lista = Flatten[Table[{h Calcy[rad, x], j x}, {x, 0, rad}, {h, {-1, 1}}, {j, {-1, 1}}], 2];
 ListPlot[Union[lista, Map[Reverse, lista]], AspectRatio -> 1];

This is the result

Not too bad IMHO ... I don't know anything about graphic algorithms ...

Answer 5

Bresenham-like algorithms are probably the expected answer, and can be derived without "complex theory". Start from a point (x,y) on the circle: (R,0) and maintain the value d=x^2+y^2-R^2, initially 0. D is the squared distance from the current point to the circle. We increment Y, and decrement X as needed to keep D minimal:

// Discretize 1/8 circle:
x = R ; y = 0 ; d = 0
while x >= y
  print (x,y)
  // increment Y, D must be updated by (Y+1)^2 - Y^2 = 2*Y+1
  d += (2*y+1) ; y++
  // now if we decrement X, D will be updated by -2*X+1
  // do it only if it keeps D closer to 0
  if d >= x
    d += (-2*x+1) ; x--