# 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

```
That's all there is to it. The derivation of the algorithm is a bit hairy, but it's really not difficult to follow. If you want a detailed presentation of all the gory stuff, please have a go with the following link.

Stefan Gustavson 2003 (stegu@itn.liu.se)