Basic Concept of Circle drawing:-

A circle is a symmetrical figure. It has eight-way symmetry as shown in the figure above Thus, any circle generating algorithm can take advantage of the circle symmetry to plot eight points by calculating the coordinates of any one point. if Point A in the figure above is calculated with a circle algorithm, seven more points could be found just by reflection.

There are two standard methods of mathematically representing a circle centered at the origin.

1. Polynomial Method :-

In this method circle is represented by a polynomial equation.

x2  +  y2  =  r2

where
x : the x coordinate

y : the y coordinate

r : radius of the circle

Here, polynomial equation can be used to find y coordinate for the known x coordinate. Therefore, the scan converting circle using polynomial method is achieved by stepping x from 0 to r √2. and each y coordinate is found by evaluating √(r^2- x^2 ) for each step of x. This generates the 1/8 Portion (90° to 45°) of the circle. Remaining part of the circle can be generated just by reflection.

The polynomial method of circle generation is an inefficient method. In this method for each point both x and r must be squared and x2 must be subtracted from r2; then the square root of the result must be found out.

2. Trigonometric Method :-

In this method. the circle is represented by use of trigonometric functions

x = rcos⁡θ and y=rsin⁡θ

where

θ : current angle

r : radius of the circle

x : the x coordinate

y : the y coordinate

The scan converting circle using trigonometric method is achieved by stepping 0 from 0 to л/4 radians. and each value of x and y is calculated. However, this method is more inefficient than the polynomial method because the computation of the values of sinθ and cosθ is even more time-consuming than the calculations required in the polynomial method.

There are three efficient circle drawing algorithm.

1. Vector generation / DDA algorithm and

2. Bresenham’s algorithm.

3. Midpoint algorithm.

Midpoint Circle Drawing Algorithm :-

The midpoint circle drawing algorithm also uses the eight-way symmetry of the circle to generate it. It plots 1/8 part of the circle, i.e. from 90° to 45°, as shown in the figure below. As circle is drawn from 90° to 45°, the x moves in the positive direction and y moves in the negative direction.

To draw a 1/8 part of a circle we take unit steps in the positive x direction and make use of decision parameter to determine which of the two possible y positions is closer to the circle path at each step.

The figure below shows the two possible y Positions (yi and yi + 1) at sampling position xi + 1. Therefore, we have to determine whether the pixel at Position (xi + 1, yi - 1) is closer to the circle. For this purpose decision parameter is used. It uses the circle function (fcircle(x, y) = x2 + y2 - r2) evaluated at the midpoint between these two pixels.

If di < 0, this midpoint is inside the circle and the pixel on the scan line yi is closer to the circle boundary.

If di ≥ 0 , the midposition is outside or on the circle boundary, and yi – 1 is closer to the circle boundary.

The incremental calculation can be determined to obtain the successive decision parameters. we can obtain a recursive expression for the next decision parameter by evaluating the circle function at sampling position xi+1 + 1 = xi + 2 .

Looking at equation ( 1 ) and ( 2 ) we can write

The initial value of decision parameter can be obtained by evaluating circle function at the start Position (x0, y0) = (0, r).

Algorithm :-

1. Read the radius (r) of the circle.

2. Initialize starting position as 
     x =  0     y = r .
3. Calculate initial value or decision parameter as 
             P = 1.25 – r. 

4. do 
   {
      plot (x, y) 
      if (d  <  0) 
      {
         x = x + 1 
         y = y 
         d = d + 2x + 1 
     else 
     {    
         x = x + 1 
         y = y -  1 
        d  = d + 2x + 2y + 1 
      }
       while(x < y) 

5. Determine symmetry points 

6. Stop.