Develop the Bresenham’s Circle drawing algorithm using C language, The Bresenham’s circle drawing Algorithm.

It is not easy to display a continuous smooth arc on the computer screen as our computer screen is made of pixels organized in matrix form. So, to draw a circle on a computer screen we should always choose the nearest pixels from a printed pixel so as they could form an arc. There are two algorithm to do this:

1. Mid-Point circle drawing algorithm
2. Bresenham’s circle drawing algorithm 

Bresenham’s circle drawing algorithm uses the key feature of circle that it is highly symmetric. So, for whole 360 degree of circle we will divide it in 8-parts each octant of 45 degree. In order to that we will use Bresenham’s Circle Algorithm for calculation of the locations of the pixels in the first octant of 45 degrees.

8- point symmetry in circles

 

Concept

•      Circles have the property of being highly symmetrical, which is handy when it comes to  drawing them on a display screen.

•      We know that there are 360 degrees in a circle. First we see that a circle is symmetrical  about the x axis, so only the first 180 degrees need to be calculated.

•      Next, we see that it's also symmetrical about the y axis, so now we only need to calculate  the first 90 degrees. Finally, we see that the circle is also symmetrical about the 45  degree diagonal axis, so we only need to calculate the first 45 degrees.

Interpolation

Bresenham's circle algorithm calculates the locations of the pixels in the first 45  degrees. It assumes that the circle is centered on the origin shifting the original  center coordinates (centerx,centery). So for every pixel (x,y) it calculates, we draw  a pixel in each of the 8 octants of the circle :

putpixel(centerx + x, center y + y) 

putpixel(centerx + x, center y - y) 

putpixel(centerx - x, center y + y) 

putpixel(centerx - x, center y - y) 

putpixel(centerx + y, center y + x) 

putpixel(centerx + y, center y - x) 

putpixel(centerx - y, center y + x) 

putpixel(centerx - y, center y - x)

   

Derivation

Now, consider a very small continuous arc of the circle interpolated below, passing by  the discrete pixels as shown.

At any point (x,y), we have two  choices – to choose the pixel on  east of it, i.e. N(x+1,y) or the  south-east pixel S(x+1,y-1). To  choose the pixel, we determine the  errors involved with both N & S  which are f(N) and f(S)  respectively and whichever gives  the lesser error, we choose that  pixel.

 

Let d_i = f(N) + f(S), where d can be called as "decision  parameter", so that

 

if (d_i<=0),

then, N(x+1,y) is to be chosen as next pixel

i.e. x_i+1 = x_i+1 and y_i+1 = y_i,

and if (d_i>0),

then, S(x+1,y-1) is to be chosen as next pixel

i.e. x_i+1 = x_i+1 and y_i+1 = y_i-1.

We know that for a circle,

x² + y² = r²,

where r represents the radius of the circle, an input to the  algorithm.

Now for each pixel, we will do the following operations:

1. Set initial values of (xc, yc) and (x, y)
2. Set decision parameter d to d = 3 – (2 * r).
3. Repeat steps 4 to 8 until x < = y
4. call drawCircle(int xc, int yc, int x, int y) function.
5. Increment value of x.
6. If d < 0, set d = d + (4*x) + 6
7. Else, set d = d + 4 * (x – y) + 10 and decrement y by 1.
8. call drawCircle(int xc, int yc, int x, int y) function.

Below is a C program of Bresenham’s  circle drawing algorithm with

output:-

#include<stdio.h>

#include<conio.h>

#include<graphics.h>

#include<math.h>

void circleplotpoints(int xc,int yc,int x,int y)

{

            putpixel(xc+x,yc+y,5);

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

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

            putpixel(xc-x,yc-y,5);

            putpixel(xc+y,yc+x,5);

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

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

            putpixel(xc-y,yc-x,5);

}

void main()

{

            int xc,yc,r,p,x,y;

            int gd=DETECT,gm;

            clrscr();

            initgraph(&gd,&gm,"");

            printf("\n Enter the value of circle center x and y:");

            scanf("%d %d",&xc,&yc);

            outtextxy(xc,yc,"(x,y)");

            printf("\n Enter the value of circle radius:");

            scanf("%d",&r);

            setbkcolor(0);

            x=0;

            y=r;

            p=1-r;

            circleplotpoints(xc,yc,x,y);

            printf("\nx=%d,\t y=%d",x,y);

            while(x<y)

            {

                        x++;

                        if(p<0)

                        p+=2*x+1;

                        else

                        {

                                    y--;

                                    p+=2*(x-y)+1;

                        }

                        circleplotpoints(xc,yc,x,y);

                        printf("\nx=%d,\t y=%d",x,y);

            }

            getch();

}

Output:

 

                                                     THANK YOU!!!!