A simple Circle drawing algorithm
Equation of circle is:
Where r= radius of the circle
Simple algorithm is to solve the equation for y at unit x intervals using:
But this algorithm is not efficient because:
Resulting circle has large gaps.
Calculations (multiply, square root) are not very efficient.
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 .
The next point is a choice between and
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. ( )
If pk lies inside or on the circle then we plot the pixel , otherwise plot the pixel .
We can make the decision by evaluating the below function at the midpoint.
The equation evaluates as follows:
The decision variable defined as:
Calculation of initial decision variable (P0):
Put k=0 .Also x0=0 and y0=r because we will start from point S having coordinate (0, r )
Input radius r and circle center (xc,Yc) and obtain the first point on the circumference of circle.
Calculate the initial value of decision parameter.
At each xk position , starting xk=0, perform the following test
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.
Repeat step (c ) through(e) until x ≥ y
Example: Draw the circle for radius =6 and centre (0,0)
Answer: x=0, y=6, d=1-6=-5