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.

Foo Bah · Accepted Answer · 2011-10-01T13:11:37.303

12

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:

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)
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)
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.

edited Oct 01 '11 at 13:11

answered Oct 01 '11 at 06:16

Foo Bah

25,660
5
55
79

The lines aren't clear to me `The trick here is basically to increment x each time, shifting down a row every time the distance is too far. There is some element of discretion here. If you want to stay outside the theoretical circle, which is what happens here, then you should check if moving down the y scale would not make the deviation negative.` Can you be bit more clearer? – sriram Oct 01 '11 at 08:56
1

@GroovyUser I tried to make it a little clearer. I will go back and update the wiki article later on, but before that, let me know if there are any other points that are unclear (or anything else that should be added) – Foo Bah Oct 01 '11 at 13:12
@foo bah : you said that `In each case, you have to calculate how far each point deviates from the circle`. I guess this algorithm is for drawing a circle, but how you can calculate each point that deviates from the circle, without drawing it first? Hopes my question is clear to you. – Ant's Oct 01 '11 at 13:36
@FooBah: How your saying that `If x^2 + (y-1)^2 - r^2 <= 0 then the next point will be x+1`? By the way why the circle equation in this case have changed the `y` variable to `(y-1)^2`? The same here `If x^2 + y^2 - r^2 > 0, then the next point should be (x+1,y-1)`! – sriram Oct 01 '11 at 13:43
1

@Ant's In each step, you are moving horizontally by one column. You are going to draw one point in that column. There are two possible `y` values (since you are drawing it in the `0-45 degree` octant): the current `y` value, or one step lower. Thus, you can "guess" that one choice is correct (in our case, we guess that moving down a row is correct) and check the error. If you are wrong, you just move horizontally, If you're right, you also move down a row. As a physical analogy, when you solve a maze, you look ahead to figure out the next step (I hope you dont actually draw the lines) – Foo Bah Oct 01 '11 at 13:46
1

@GroovyUser Like i tried to explain in the response for Ant's, when you move horizontally, you can either stay in the same row (dont change `y`) or move down a row (`y-1`). You are actually checking if you should shift downward (which is why you see `y-1` and `y-2` in the error formulae). If you wanted to check if moving horizontally (without going down) is correct, you would have a different loop. Why dont you try working it out :) – Foo Bah Oct 01 '11 at 13:49
@FooBah : Ya sure it was an great answer :) by the way how do you put such an answer ;) good at graphics or in C? *_* – sriram Oct 01 '11 at 13:52
@FooBah : thanks for the answer :) I will surely tweet this to my friends. Thanks once again :) – sriram Oct 01 '11 at 13:54
1

@GroovyUser After you get past the `C` language kerfluffle, it's really just math :) I also didnt know there was a wikipedia article on the matter until I saw Miguel's answer. To make sure you understand what is going on, why don't you try to write the explanation in the wiki article (and then I'll go back and clean up any points of confusion :) – Foo Bah Oct 01 '11 at 13:56
@FooBah : Me ;) I haven't written any wiki before ;) – sriram Oct 01 '11 at 13:59
@GroovyUser It's a good exercise to solidify understanding. If you deeply understand it, then you should be able to explain it to others – Foo Bah Oct 01 '11 at 14:02
@FooBah : I have to do many Graphics programming :) surely you gonna to help me out in my doubts :) – sriram Oct 01 '11 at 14:02
@FooBah : ya surely will try it :) – sriram Oct 01 '11 at 14:07

score -2 · Answer 2 · answered Oct 01 '11 at 05:59

-2

The section of the program that you are asking about is the core of the circle drawing algorithm, and it computes the x, y coordinates for one octant of the circle (the eight putpixel() calls mirror this octant into the other seven to complete the circle). The algorithm is explained in detail in this article.

answered Oct 01 '11 at 05:59

Miguel Grinberg

65,299
14
133
152

3

The article should be improved a bit, because it only explains how the calculation is run if you use two error markers to keep track of position. It doesn't explain how the single-error solution works (which is what the OP is asking about). I may clean up my answer and update the wiki page – Foo Bah Oct 01 '11 at 06:20

Bresenham's circle algorithm

2 Answers2