# A simple Circle drawing algorithm

Equation of circle is:​​

x2+y2=r2

Where​​ r= radius of the circle

Simple​​ algorithm​​ is to solve​​ the equation for y at unit x intervals using:

y=±r2-x2

But this algorithm is not efficient because:

• Resulting circle has large gaps.

• Calculations (multiply, square root) are not very efficient.

## Eight-Way Symmetry

For efficient algorithm, we should consider that circle centered at (0, 0) have 8-way symmetry.

## Mid-Point circle algorithm

In mid point algorithm, we use eight-way symmetry. So only ever calculate the points for the top right eighth of a circle(first octant)​​ and then use symmetry to get points​​ in other octant.

The mid-point circle drawing algorithm is developed by​​ Jack Bresenham.

Assume we have just plotted point​​ (xk, yk)​​ .​​

​​ The next point is a choice between ​​ (xk+1 , yk)​​ and​​ (xk+1 , yk-1)

We like to choose the point that is nearest to the actual circle using the below steps:

• Find the midpoint pk​​ between above 2 pixels i.e. (​​ xk+1,yk-12​​ )

• If pk​​ lies inside or on the circle then we plot the pixel​​ (xk+1 , yk)​​ , otherwise plot the pixel​​  (xk+1 , yk-1)​​ .

We can make the decision by evaluating the below function at the midpoint.

fx,y=x2+y2-r2

The equation evaluates as follows:

fx,y= <0,  if x,yis inside the circle boundary.=0,  if x,y is on the circle boundary>0,  if x,y is outside the circle boundary ​​

The decision variable defined as:

Pk=fxk+1, yk-12=(xk+1)2+( yk-12)2-r2

Similarly

Pk+1=fxk+1+1, yk+1-12=xk+1+12+ yk+1-122-r2

Pk+1=xk+1+12+ yk+1-122-r2
Pk+1-Pk=xk+1+12+ yk+1-122-r2-[xk+12+ yk-122-r2]

Pk+1-Pk=xk+1+12-xk+12+ yk+1-122- yk-122

Pk+1-Pk=xk+12+2xk+1+1-xk+12+ yk+12-yk+1+14- yk2-yk+14

Pk+1=Pk+2xk+1+ yk+12-yk2- yk+1-yk+1

Case 1:​​ Pk<0,  so yk+1=yk

Pk+1=Pk+2xk+1+1​​

Case 2:​​ Pk>0,  so yk+1=yk-1

Pk+1=Pk+2xk+1-2(yk+1)+1​​

## Calculation of initial decision variable (P0):

Pk=fxk+1, yk-12

Put k=0 .Also x0=0 and y0=r because we will start from point S having coordinate (0,​​ r​​ )​​

Then,

​​ ​​ P0=fx0+1, y0-12=f0+1, r-12

P0=f1, r-12=1+r-122-r2

P0=54-r1-r

## Algorithm

• Input radius r and circle center (xc,Yc) and obtain the first point on the circumference of circle.

x0=0;y0=r

• Calculate the initial value of decision parameter.

P0=54-r1-r

• At each xk​​ position , starting xk=0, perform the following test

Case 1:​​ Pk<0,    yk+1=yk

​​​​ Pk+1=Pk+2xk+1+1

​​ Case 2:​​ Pk>0,    yk+1=yk-1

Pk+1=Pk+2xk+1-2(yk+1)+1

• Determine symmetry points in other seven octets.

• Move each calculate pixel position (x,y) onto the circular path centered (xc,Yc) and plot the coordinate.

x=x+xc; y=y+yc

• Repeat step (c )​​ through(e)​​ until​​ x​​ ≥​​ y

Example:​​ Draw the circle for radius =6 and centre (0,0)