Draw A Circle - Microsoft Interview

http://petercai.com/the-microsoft-sde-interview/

The question was to code an algorithm to draw a circle. Of course, the general equation is x2 + y2 = r2. My first attempt was to do the following: set x = -r, and then continually increment x until it was equal to r. At each step, use the equation to calculate the value of y given x, and then plot it. This gives a semi-circle. I observed that since a circle is symmetrical, I could simply draw the other half of the circle by reversing the y axis. However, this wasn’t fast enough, so I was forced to rethink my algorithm. It turns out that a circle is also symmetrical along the y axis, so I only needed to calculate a single quadrant of the circle, and could simply mirror along the x and y axes. This was still not fast enough for my interviewer.

After a carefully placed hint, I realized that a quarter circle is actually symmetrical as well – so that only 1/8 of the circle needs to be calculated. The rest of the interview consisted of me refining the algorithm — namely, accounting for any gaps that might appear in my circle (which can be fixed by taking into the account the slope of the line that is being plotted and choosing to either use x or y as the given).

Midpoint circle algorithm
https://en.wikipedia.org/wiki/Midpoint_circle_algorithm
https://problem4me.wordpress.com/2007/07/28/midpoint-circle-java-code/
http://sourcecodesforfree.blogspot.com/2013/05/28-midpoint-circle.html
http://rosettacode.org/wiki/Bitmap/Midpoint_circle_algorithm#Java

 private void drawCircle(final int centerX, final int centerY, final int radius) {
  int d = (5 - r * 4)/4;
  int x = 0;
  int y = radius;
  Color circleColor = Color.white;
 
  do {
   image.setPixel(centerX + x, centerY + y, circleColor);
   image.setPixel(centerX + x, centerY - y, circleColor);
   image.setPixel(centerX - x, centerY + y, circleColor);
   image.setPixel(centerX - x, centerY - y, circleColor);
   image.setPixel(centerX + y, centerY + x, circleColor);
   image.setPixel(centerX + y, centerY - x, circleColor);
   image.setPixel(centerX - y, centerY + x, circleColor);
   image.setPixel(centerX - y, centerY - x, circleColor);
   if (d < 0) {
    d += 2 * x + 1;
   } else {
    d += 2 * (x - y) + 1;
    y--;
   }
   x++;
  } while (x <= y);
 
 }

https://github.com/jianminchen/AlgorithmsProblems/blob/master/DrawACircle.cs

http://people.cs.uchicago.edu/~kaharris/15200/Labs/lab3/circle.html