drawing circle without floating point calculation

This is a common inter开发者_StackOverflowview question (according to some interview sites) but I can find no normal answers on the Internet - some are wrong and some point to complex theory I expect not to be required in an interview (like the Bresenham algorithm).

The question is simple:

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

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 >= 0
    d += (-2*x+1) ; x--

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.

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".

Pretty old question but I will try to provide the end solution with visual tests in python as an alternative to Bresenham's algorithm - the best and the shortest solution for this task. I think this idea also can have a place and perhaps is simpler to understand but needs more code. Someone maybe also end up with this solution.

The idea is based on the following facts:

1. Every point on circle lies on the same distance to circle central point
2. A circle contains 4 quadrant which starts and ends in points (r, 0), (2r, r), (r, 2r) and (0, r) if r is radius and central point is in (r, r) point.
3. A circle is a continues figure and every point can have 8 neighbor points. If move on circle in one direction only three points are interesting for us - 3 lie in opposite direction and 2 are too far from center. For example for point (r, 0) with direction to (2r, r) interesting points will be (r + 1, 1), (r, 1) and (r + 1, 0)

import matplotlib.pyplot as plt
from itertools import chain

def get_distance(x1, y1, x2, y2):
    """
        Calculates squared distance between (x1, y1) and (x2, y2) points
    """
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);

def get_next_point(x, y, dx, dy, cx, cy, r):
    """
        Returns the next circle point base on base point (x, y), 
        direction (dx, dy), circle central point (cx, cy) and radius r
    """
    r2 = r * r

    # three possible points
    x1, y1 = x + dx, y + dy
    x2, y2 = x, y + dy
    x3, y3 = x + dx, y

    # calculate difference between possible point distances 
    # with central point and squared radius
    dif1 = abs(get_distance(x1, y1, cx, cy) - r2)
    dif2 = abs(get_distance(x2, y2, cx, cy) - r2)
    dif3 = abs(get_distance(x3, y3, cx, cy) - r2)

    # choosing the point with minimum distance difference
    diff_min = min(dif1, dif2, dif3)

    if diff_min == dif1:
        return x1, y1
    elif diff_min == dif2:
        return x2, y2
    else:
        return x3, y3

def get_quadrant(bx, by, dx, dy, cx, cy, r):
    """
        Returns circle quadrant starting from base point (bx, by), 
        direction (dx, dy), circle central point (cx, cy) and radius r
    """
    x = bx
    y = by

    # maximum or minimum quadrant point (x, y) values
    max_x = bx + dx * r
    max_y = by + dy * r

    # choosing only quadrant points
    while (dx * (x - max_x) <= 0) and (dy * (y - max_y) <= 0):
        x, y = get_next_point(x, y, dx, dy, cx, cy, r)
        yield x, y

def get_circle(r, cx, cy):
    """
        Returns circle points (list) with radius r and center point (cx, cy)
    """
     north_east_quadrant = get_quadrant(cx, cy - r, 1, 1, cx, cy, r)
     south_east_quadrant = get_quadrant(cx + r, cy, -1, 1, cx, cy, r)
     south_west_quadrant = get_quadrant(cx, cy + r, -1, -1, cx, cy, r)
     north_west_quadrant = get_quadrant(cy - r, cy, 1, -1, cx, cy, r)

    return chain(north_east_quadrant, south_east_quadrant,
                 south_west_quadrant, north_west_quadrant)

# testing

r = 500

circle_points = get_circle(r, r, r)

for x, y in circle_points:
    plt.plot([x], [y], marker='o', markersize=3, color="red")

plt.show()

I will use the Bresenham's Circle drawing algorithm or the Midpoint Circle drawing algorithm. Both produce the same coordinate points. And with the symmetry between the eight octants of the circle, we just need to generate one octant and reflect and copy it to all the other positions.

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.

Has anyone considered they might be looking for a lateral answer such as "with a compass and pencil" or "use the inside of a roll of sellotape as a template".

Everyone assumes all problems have to be solved with a computer.

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 ...