Bresenham's circle algorithm

Instruction

Bresenham's circle algorithm, also called midpoint circle algorithm, is an algorithm used to determine the points needed for drawing a circle.

The reason of using this algorithm is, when drawing circle, we need to calculate the floating point numbers of each coordinate points, which may be slow when processing multiple objects.

This method provides a simplified way to draw the circle by estimating the midpoint of arcs.

The Algorithm

for each point p(x,y)
we can take the next approximate points N(x,y+1) , NW(x-1,y+1) by estimating midpoint M(x-1/2,y+1)
that is: if the point M is in the circle, the point N is closer to the circle, therefore the N should be chooses for next point, otherwise, the NW point should be chooses.

so, we can calculate the distance from M to circumference by the formula:
Rd = r - Rm
if Rd < 0, M is outside the circle, if Rd > 0, M is inside the circle.
from x^2 + y^2 = r^2,
we can know that
Xm^2 + Ym^2 - Rm^2 = Xm^2 + Ym^2 - (r - Rd)^2 = 0
therefore, we can Defined D(M) = Xm^2 + Ym^2 - r^2 = Rd^2 - 2Rd = Rd(Rd -2)
because midpoint will be close to the circle, we can ignore the case when Rd > 2.
So if D(M) > 0,Rd < 0 ,M is outside the circle , NW should be chooses if D(M) < 0,Rd > 0 ,M is inside the circle , N should be chooses

We can get the algorithm as below in javascripts:

var drawCircle = function(ctx , x , y , r){
  var cx = r;
  var cy = 0;
  //init draw 4 points on top,right,left and bottom.    
  init(ctx,x,y,r);
  
  //we only need to calculate 1/8 of the arcs, 
  //that is when angle = 45degree, cx = xy 
  while(cx > cy){
    if(cx*cx + cy*cy -r*r > 0){ // D(M) , if D(M) > 0, NW(x-1,y+1) is chooses
      cx--;
    }
    cy++;

    //draw point and mirrow the points to other 7 places on circle
    mirrowing(ctx,x,y,cx,cy);
  }
}

Optimize

The algorithm is fast now and without any floating points,
but we can optimize more by simplify the calculation of D(M)

for each D(M) = D(x-1/2,y) = x^2 - x +1/4 + y^2 -r^2
the next D(Mnew) = D(x-1/2,y+1) = x^2 - x +1/4 + y^2 +2y +1 - r^2
so we can get the difference of each level of D(M), dy = 2y + 1
let D(Mnew) = D(M) + 2y + 1

also, don't forget when the D(M) > 0 , we should move x too,
so D(Mnew) = D(x-3/2,y+1) = x^2 - 3x +9/4 + y^2 +2y + 1
= D(M) -2x +2 +2y +1
so we can get the difference when x moved: dx = -2x +2

for the optimize above we can get the new algorithm:

var drawCircle = function(ctx, x, y, r){

  // d start from D(M) = r^2 - r^2 + r-1/4 = r- 1/4 , but we can ignore constant because r>1/4
  var d = r; 
  var dx = (-2) * r; //dx = -2x +2 , constant move to loop
  var dy = 0; //dy = 2y + 1 , constant move to loop

  var cx = r; //starting point:
  var cy = 0;
    
  init(ctx,x,y,r);

  while(cx > cy){
    if(d > 0){
      cx--;
      d += (-2)*cx + 2;
    }
    cy++;
    d += 2*cy + 1;

    mirrowing(ctx,x,y,cx,cy);
  }
}

you can watch the demo on javascript canvas here.(firefox and chrome/safari only)

ref:
Wiki
http://www.ecse.rpi.edu/