Bresenham's circle algorithm

Question

I have the following code for drawing a circle :

#include<stdio.h>
#include<conio.h>
#include<graphics.h>
#include<math.h>

void main()
{
    int xc, yc, x, y, p[100], r, k;
    int gdriver=DETECT, gmode, errorcode;
    printf("\nEnter the center point(xc,yc): ");
    scanf("%d%d", &xc, &yc);
    printf("\nEnter the radius: ");
    scanf("%d", &r);
    printf("\nPlotting...\n");
    sleep(5);
    clrscr();

    initgraph(&gdriver, &gmode, "");
    p[0]=1-r;
    x=0;
    y=r;
    for(k=0;k<=y;k++)
    {
        putpixel(xc+x, yc+y, 9);
        putpixel(xc-x, yc-y, 9);
        putpixel(xc+x, yc-y, 9);
        putpixel(xc-x, yc+y, 9);
        putpixel(xc+y, yc+x, 9);
        putpixel(xc-y, yc-x, 9);
        putpixel(xc+y, yc-x, 9);
        putpixel(xc-y, yc+x, 9);

        if(p[k]>0)
        {
            p[k+1]= p[k]+ 2*(x+1)+1-2*(y+1);
            x++;
            y--;
        }
        else
        {
            p[k+1]=p[k]+2*(x+1)+1;
            x++;
        }
    }
        getch();
}

This part of code :

putpixel(xc+x, yc+y, 9);
            putpixel(xc-x, yc-y, 9);
            putpixel(xc+x, yc-y, 9);
            putpixel(xc-x, yc+y, 9);
            putpixel(xc+y, yc+x, 9);
            putpixel(xc-y, yc-x, 9);
            putpixel(xc+y, yc-x, 9);
            putpixel(xc-y, yc+x, 9);

Is mainly for plotting the points with respect to the circle, and it works because of the symmetric property of circle.

But I couldn't figure out what this part of code is exactly doing ;

if(p[k]>0)
        {
            p[k+1]= p[k]+ 2*(x+1)+1-2*(y+1);
            x++;
            y--;
        }
        else
        {
            p[k+1]=p[k]+2*(x+1)+1;
            x++;
        }

Can anyone explain me what it does? Thanks in advance.

Answer 1

The update formulae look a little weird, and I will give what I think are the correct steps below:

You are starting from the topmost point in the circle and rotating clockwise until the angle reaches 45 degrees.

Now, the points on the circle roughly satisfy (x^2 + y^2 = r^2).

The idea is to draw one pixel at a time, moving in the positive x direction. If you find that the next point (without shifting down) is too far from the center of the circle, then that point should be drawn one unit lower. For example, if you look at pixellated circles, you will see that they can be essentially broken down into a series of horizontal lines and pixels. Each end of the horizontal line marks a point where extending the line would be too far from the circle, and hence you see a drop.

Note that there is some element of discretion here regarding which points you choose. There are 3 circle drawing disciplines:

1. Inner circle: Choose points such that no point is drawn outside of the circle (so that x^2 + y^2 < (r+1)^2 for each point r -- note that its r+1 here and not r)
2. Outer circle: Choose points such that no point is drawn inside of the circle (so that x^2 + y^2 > (r-1)^2 for each point r -- note that its r-1 here and not r)
3. Middle circle: Choose points that minimize abs(x^2 + y^2 - r^2).

You can choose any of these disciplines in the algorithm. The methods are identical except for that code block (and the changes there are minor).

In each case, you have to calculate how far each point deviates from the circle. This requires knowing x^2 + (y-1)^2 - r^2. Let's call that sequence p[k]. If x^2 + (y-1)^2 - r^2 <= 0, then moving down would show the point too close to the center of the circle, so the next point should be (x+1, y). In that circumstance, then the next deviation will be:

p[k+1] = (x+1)^2 + (y-1)^2 - r^2 = x^2 + (y-1)^2 - r^2 + 2x + 1 = p[k] + 2*(x + 1) - 1

If x^2 + y^2 - r^2 > 0, then the next point should be (x+1,y-1), so that

p[k+1] = (x+1)^2 + (y-2)^2 - r^2 = x^2 + (y-1)^2 - r^2 + 2x + 1 - 2y + 3 = q[k] + 2*(x + 1) - 2*(y - 1) = p[k] + 2*(x+1) - 2 * (y + 1)

These formulae change based on whether you are interested in finding the outer circle (pixels are never too close), inner circle (pixels are never too far), or center circle (roughly in line), but this is the essential idea.