Bresenham Circle Algorithm

Question

I have the following code to draw 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 piece 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); 

Mostly for building points in a circle, and it works because of the symmetrical properties of the circle.

But I could not understand what exactly this part of the code does;

 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 someone explain to me what he is doing? Thanks in advance.

Answer 1

The update formulas look a little strange and I will give that I think these are the right steps below:

You start at the highest point in the circle and rotate 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 moving down) is too far from the center of the circle, then this point should be drawn one unit lower. For example, if you look at the pixel circles, you will see that they can essentially be divided into a series of horizontal lines and pixels. Each end of the horizontal line indicates the point at which the line extension is too far from the circle, and therefore you see a drop.

Please note that there is some element of discretion regarding which points you choose. There are three disciplines of drawing in a circle:

• Inner circle: select points so that no point is drawn outside the circle (so x^2 + y^2 < (r+1)^2 for each point r - note that its r+1 here, not r )
• Outer circle: select points at which no points will be drawn inside the circle (so x^2 + y^2 > (r-1)^2 for each point r - note that its r-1 here, and not r )
• Middle circle: select points that minimize abs(x^2 + y^2 - r^2) .

You can select any of these disciplines in the algorithm. The methods are identical, with the exception of this code block (and the changes there are minor).

In each case, you need to calculate how far each point deviates from the circle. This requires knowledge of x^2 + (y-1)^2 - r^2 . Let us call this sequence p[k] . If x^2 + (y-1)^2 - r^2 <= 0 , then a downward movement would show a point located too close to the center of the circle, so the next point should be (x+1, y) . In this case, the following 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

 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 formulas vary depending on whether you are interested in the outer circle (pixels are never too close), the inner circle (pixels are never too far), or the center circle (about a line), but this is the main idea.

Answer 2

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