### Bresenham's circle/ellipse drawing algorithm

Algorithm

Here the general approach is based on lines drawing and sqrt function. Using Bresenham's approach we exclude sqrt function, only sum and multiplication. It is supposed we have next graphical primitive methods MoveTo(), LineTo() and DrawPixel().

Let us have a look at the result of general and Bresenham's algorithms for circles.

C-code for the sqrt-based procedure for circle
 void DrawCircle (int x, int y, int radius){    int sqrRoot, prevSR, r_2;    int i;        prevSR = sqrRoot = 0;    r_2 = radius * radius;    for (i = 1; i < 2 * radius + 1; i++)    {        sqrRoot = sqrt (r_2 - ((radius - i)*(radius - i)));        MoveTo(i - 1, radius + prevSR);        LineTo(i, radius + sqrRoot);        MoveTo(i - 1, radius - prevSR);        LineTo(i, radius - sqrRoot);        prevSR = sqrRoot;    }}

C-code for the Bresenham's procedure
 void DrawCircle (int xc, int yc, int radius){    int x = 0;    int y = radius;    int delta = 2 - 2 * radius;    int error = 0;    while(y >= 0)    {         DrawPixel (xc + x, yc + y);         DrawPixel (xc - x, yc + y);         DrawPixel (xc + x, yc - y);         DrawPixel (xc - x, yc - y);        error = 2 * (delta + y) - 1;        if(delta < 0 && error <= 0) {            ++x;            delta += 2 * x + 1;            continue;        }        error = 2 * (delta - x) - 1;        if(delta > 0 && error > 0) {            --y;            delta += 1 - 2 * y;            continue;        }        ++x;        delta += 2 * (x - y);        --y;    }}

Bresenham's circle is on the right, the radius is 20 pixels for both of them. Could you find 10 differences?

Let us continue with ellipses. C-code for the sqrt-based procedure for ellipce

 void DrawEllipse (int x, int y, int width, int height){    int sqrRoot, prevSR;    int h_2, w_2;    int  i;    prevSR = sqrRoot = 0u;    h_2 = height * height;    w_2 = width * width;    for (i = 1; i < 2 * width; i++)    {        sqrRoot = sqrt (h_2 - (((h_2 * (width - i)) * (width - i)) / w_2));        MoveTo (i - 1, height + prevSR);        LineTo (i, height + sqrRoot);        MoveTo (i - 1, height - prevSR);        LineTo (i, height - sqrRoot);        prevSR = sqrRoot;    }}

C-code for the Bresenham's procedure to draw an ellipse in two steps

 void DrawEllipse (int xc, int yc, int width, int height) {    int a2 = width * width;    int b2 = height * height;    int fa2 = 4 * a2, fb2 = 4 * b2;    int x, y, sigma;    /* first half */    for (x = 0, y = height, sigma = 2*b2+a2*(1-2*height); b2*x <= a2*y; x++)    {        DrawPixel (xc + x, yc + y);        DrawPixel (xc - x, yc + y);        DrawPixel (xc + x, yc - y);        DrawPixel (xc - x, yc - y);        if (sigma >= 0)        {            sigma += fa2 * (1 - y);            y--;        }        sigma += b2 * ((4 * x) + 6);    }    /* second half */    for (x = width, y = 0, sigma = 2*a2+b2*(1-2*width); a2*y <= b2*x; y++)    {        DrawPixel (xc + x, yc + y);        DrawPixel (xc - x, yc + y);        DrawPixel (xc + x, yc - y);        DrawPixel (xc - x, yc - y);        if (sigma >= 0)        {            sigma += fb2 * (1 - x);            x--;        }        sigma += a2 * ((4 * y) + 6);    }}

Bresenham's ellipse is also on the right, w = 20, h = 15 for both of them.

Appendix

1. Graham Toal added the ellipse-drawing code to one of the Scratch projects (a graphical programming language for kids) - http://scratch.mit.edu/projects/50039326/
Thanks Graham! =)

2. Well known screen recorder CamStudio uses sqrt-approach to visualize circle/ellipse cursor view. I would not say that they are circle and ellipse:

3. IE also uses terrible sqrt-approach to portray its progress bar.