# Bresenham Circle Drawing Algorithm

Computer Graphics / Monday, November 5th, 2018
(Last Updated On: November 5, 2018)

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 MC,

$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(MC) < 0, E is chosen, else SE is selected. Let us consider these two cases separately. If E is chosen, for the next mid-point MnE,

$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 MnSE,

$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$