We have already discussed DDA and Bresenham Line Drawing Algorithm, now in this article we are going to learn Bresenham Circle Drawing Algorithm.

# Bresenham Circle Drawing Algorithm

We know, circle itself has eight-way symmetry where any point P on the boundary is reflected seven times shown in fig (A) as a result, scan conversion of 1/8 th of the circle is enough to generate its remaining seven octants.

Bresenham has modified line scan conversion algorithm using mid-point to generate circles. For circle with radius R and origin at (0, 0), the equation is given by

\[f(x,y)={{x}^{2}}+{{y}^{2}}-{{R}^{2}}\]

Referring to fig(B) for the current mid-point M_{C},

\[f\left( {{M}_{C}} \right)=f\left( x+1,y-\frac{1}{2} \right)\]

\[\Rightarrow f\left( {{M}_{C}} \right)={{\left( x+1 \right)}^{2}}+{{\left( y-\frac{1}{2} \right)}^{2}}-{{R}^{2}}……..(1)\]

If f(M_{C}) < 0, E is chosen, else SE is selected. Let us consider these two cases separately. If E is chosen, for the next mid-point M_{n}^{E},

\[f\left( M_{n}^{E} \right)=f\left( x+2,y-\frac{1}{2} \right)\]

\[\Rightarrow f\left( M_{n}^{E} \right)={{\left( x+2 \right)}^{2}}+{{\left( y-\frac{1}{2} \right)}^{2}}-{{R}^{2}}……..(2)\]

Therefore, in this case, the increment is

\[\Delta E=f\left( M_{n}^{E} \right)-f\left( {{M}_{C}} \right)\]

\[=\left\{ {{\left( x+2 \right)}^{2}}+{{\left( y-\frac{1}{2} \right)}^{2}}-{{R}^{2}} \right\}-\left\{ {{\left( x+1 \right)}^{2}}+{{\left( y-\frac{1}{2} \right)}^{2}}-{{R}^{2}} \right\}\]

\[\therefore \Delta E=2x+3……..(3)\]

If SE is chosen, again for the next mid-point M_{n}^{SE},

\[f\left( M_{n}^{SE} \right)=f\left( x+2,y-\frac{3}{2} \right)\]

\[\Rightarrow f\left( M_{n}^{E} \right)={{\left( x+2 \right)}^{2}}+{{\left( y-\frac{3}{2} \right)}^{2}}-{{R}^{2}}……..(4)\]

Therefore, the increment in this case is

\[\Delta SE=f\left( M_{n}^{SE} \right)-f\left( {{M}_{C}} \right)\]

\[=\left\{ {{\left( x+2 \right)}^{2}}+{{\left( y-\frac{3}{2} \right)}^{2}}-{{R}^{2}} \right\}-\left\{ {{\left( x+1 \right)}^{2}}+{{\left( y-\frac{1}{2} \right)}^{2}}-{{R}^{2}} \right\}\]

\[\therefore \Delta SE=2x-2y+5……..(5)\]

Now similar to line scan conversion, the problem remains to detect the first mid-point which should be at (1. R – ½ ) for circle of radius R and at center (0, 0).

Then,

\[f\left( 1,R-\frac{1}{2} \right)=1+{{R}^{2}}-R+\frac{1}{4}-{{R}^{2}}=\frac{5}{4}-R\]

## Bresenham Circle Drawing Algorithm Implementation in C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
#include<graphics.h> #include<stdio.h> void pixel(int xc,int yc,int x,int y); int main() { int gd,gm,xc,yc,r,x,y,p; detectgraph(&gd,&gm); initgraph(&gd,&gm,"C://TurboC3//BGI"); printf("Enter center of circle :"); scanf("%d%d",&xc,&yc); printf("Enter radius of circle :"); scanf("%d",&r); x=0; y=r; p=3-2*r; pixel(xc,yc,x,y); while(x<y) { if(p<0) { x++; p=p+4*x+6; } else { x++; y--; p=p+4*(x-y)+10; } pixel(xc,yc,x,y); } getch(); closegraph(); return 0; } void pixel(int xc,int yc,int x,int y) { putpixel(xc+x,yc+y,WHITE); putpixel(xc+x,yc-y,WHITE); putpixel(xc-x,yc+y,WHITE); putpixel(xc-x,yc-y,WHITE); putpixel(xc+y,yc+x,WHITE); putpixel(xc+y,yc-x,WHITE); putpixel(xc-y,yc+x,WHITE); putpixel(xc-y,yc-x,WHITE); } |