Bresenham's circle algorithm

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

Consider the diagram below:

      |y          
      |           
  \ ..... /
   .  |  .        
  . \ | / .       
  .  \|/  .       
--.---+---.--     
  .  /|\  . x     
  . / | \ .       
   .  |  .        
  / ..... \       
      |
      |

(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 symmetrical about the x axis, so only the first 180 degrees need to be calculated. Next we see that it's also symmetrical about the y axis, so now we only need to calculate the first 90 degrees. Finally we see that the circle is also symmetrical 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 octant 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.

More articles

• http://www.asksatyam.com/2011/01/bresenhams-circle-algorithm_22.html
• http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/bresenham.html