The midpoint circle algorithm

This is an applet I wrote for demonstration purposes. It draws a circle using the "midpoint algoritm", which requires only integer aritmetic, and manages without even a single multiplication. (Seriously, have a look at the source code!)

Please note that this algorithm is not particularly well suited to a Java implementation. In Java, the actual pixel drawing takes more time than the decisions regarding which pixels to paint. I only used Java because it was a convenient demonstration language. In a more machine-oriented language like C or C++, this would be a very efficient circle drawing algorithm.

The main loop of the circle drawing algorithm looks like this. All variables are integers. Note the lack of complicated arithmetic.

// Midpoint algorithm with forward difference update of decision variable d
  x = 0;
  y = R; // Start at the top of the circle and draw 2nd octant only
  d = 5-(R<<2); // Potential function f(x,y)=x*x+y*y-R*R, scaled by 4
                // and evaluated at the first midpoint: x=1, y=R-0.5
  ddx = 12; // Intital value for ddx
  ddxy = 20 - (R<<3);  // Intital value for ddxy

  while(x<=y) { // Keep going until we cross the line x=y
    setpixel(x0+x, y0+y); // Mirror (x,y) to all eight octants.
    setpixel(x0+x, y0-y); // The circle center is at (x0, y0).
    setpixel(x0-x, y0+y);
    setpixel(x0-x, y0-y);
    setpixel(x0+y, y0+x);
    setpixel(x0+y, y0-x);
    setpixel(x0-y, y0+x);
    setpixel(x0-y, y0-x);

    if(d>0) {
      d = d + ddxy; // Update d for the next midpoint
      y = y - 1; // Take a step down when d is positive
      ddxy = ddxy + 16; // Update ddxy for one step down
    }
    else {
      d = d + ddx; // Update d for the next midpoint
      ddxy = ddxy + 8; // Update ddxy for no step down
    }
    ddx = ddx + 8; // Update ddx for one step right
    x = x + 1; // Always take a step to the right
  } // end while
		

• Detailed presentation (PDF)