Bresenham's circle algorithm

Circles have the property of being highly symetrical, which is handy when it comes to drawing them on a display screen.

      |y          (This diagram is supposed to be a circle, try viewing
      |           it in 50 line mode).
  \ ..... /
   .  |  .        We know that there are 360 degrees in a circle. First we
  . \ | / .       see that a circle is symetrical about the x axis, so
  .  \|/  .       only the first 180 degrees need to be calculated. Next
--.---+---.--     we see that it's also symetrical about the y axis, so now
  .  /|\  . x     we only need to calculate the first 90 degrees. Finally
  . / | \ .       we see that the circle is also symetrical about the 45
   .  |  .        degree diagonal axis, so we only need to calculate the
  / ..... \       first 45 degrees.
      |
      |

Bresenham's circle algorithm calculates the locations of the pixels in the first 45 degrees. It assumes that the circle is centered on the origin. So for every pixel (x,y) it calculates we draw a pixel in each of the 8 octants of the circle :

PutPixel(CenterX + X, Center Y + Y)
PutPixel(CenterX + X, Center Y - Y)
PutPixel(CenterX - X, Center Y + Y)
PutPixel(CenterX - X, Center Y - Y)
PutPixel(CenterX + Y, Center Y + X)
PutPixel(CenterX + Y, Center Y - X)
PutPixel(CenterX - Y, Center Y + X)
PutPixel(CenterX - Y, Center Y - X)

So let's get into the actual algorithm. Given a radius for the circle we perform this initialisation:

d := 3 - (2 * RADIUS)
x := 0
y := RADIUS

Now for each pixel we do the following operations:

Draw the 8 circle pixels
if d < 0 then
    d := d + (4 * x) + 6
else
  begin
    d := d + 4 * (x - y) + 10
    y := y - 1;
  end;

And we keep doing this until x = y. Note that the values added to the decision variable in this algorithm (x and y) are constantly changing, so we cannot precalculate them. The muliplications however are by 4, and we can accomplish this by shifting left twice.