Scan Converting a Circle

Scan Converting a circle

A circle is a geometric figure which is round, and can be divided into 360 degrees. A circle is a symmetrical figure which follows 8-way symmetry.

8-Way symmetry: Any circle follows 8-way symmetry. This means that for every point (x,y) 8 points can be plotted. These (x,y), (y,x), (-y,x), (-x,y), (-x,-y), (-y,-x), (y,-x), (x,-y). 

For any point (x+a, y+b), points (x ± a, y ± b) and (y ± a, x ± b) also lie on the same circle. So it is sufficient to compute only 1/8 of a circle, and all the other points can be computed from it.

Drawing a circle: To draw a circle we need two things, the coordinates of the centre and the radius of the circle.

Radius: The radius of a circle is the length of the line from the centre to any point on its edge.

Equation of the circle: For any point on the circle (x,y) and the centre at point (x_c,y_c), the equation of the circle is

(x-x_c)²+ (y-y_c) ²- r² = 0

Here r is the radius of the circle. If the circle has origin (0,0) as its centre then the above equation can be reduced to

x² + y² = r²

Using polar coordinate system the point on the circle can be represented as:

x = r * cos θ
y = r * sin θ

θ is the angle which the point makes With x-axis.

Direct Method (Polynomial method) of Scan converting a circle :

From equation of the circle   x² + y² = r²    we can derive that the value of   y.

If we increment the value of   x   from 0 to r, and find the corresponding value of   y   for each   x, we can draw a circle very easily, by plotting the pixels (x,y), (-x,y), (-x,-y), (x,-y).

Advantages :

• ·         This method is easy to understand.
• ·         Fairly easy to implement.

Disadvantages:

• ·         Inefficient method as time required for calculation of square and square root is very large.
• ·         Does not take full advantage of 8-way symmetry.
• ·         Value of  y  needs to be converted to integer every time.
• ·         The resulting circle has large gaps where the slope approaches the vertical. i.e. Increase in x direction is uniform but the gap in y is not uniform, it increases as the circle approaches the x-axis.

Polar Equations method :

                                                           The polar equations of the circle are    x = r * cos θ 

                                                         y = r * sin θ

In this method we increment the value of   θ   from  0 to 2π , and we find the corresponding values of x and y. For every value of (x,y) thus calculated we can plot 7 other points taking advantage of 8-way symmetry.

Disadvantages:

·           The main issue with this method is that calculation of cos and sin at each step take a lot of time.

·           This method is also inefficient, as it takes a lot of time.

Bresenham’s Algorithm :

This is a circle drawing algorithm, in which the value of   x   is incremented from  0  to 

r/2^1/2 .  

Were r  is the radius of the circle. In this derivation we assume that the circle is centered at the origin. 

As  x  increases in this sector , the value of  y  will either remain same as the previous point or will be one less than the previous point.

Point A (x_i + 1, y_i) is to the right of the i^th point. Point B (x_i + 1, y_i -1) is below and to the right.

The algorithm proceeds by selecting point A or point B depending on which pixel is closer to the actual point P on the circle.

             

                     OB²  = (x_i + 1)² +  (y_i -1)²

        OA²  = (x_i + 1)² +  (y_i)²

         d(A) =  PA²  =  OA² – OP²

                 =  (x_i + 1)² +  (y_i)² – r²

        d(B)  =  BP²  =  OP² – OB²

                 =  r²  - (x_i + 1)² -  (y_i -1)²

            S_i  =  d(A) - d(B)

                 =  (x_i + 1)² +  (y_i)² – r² – r²  + (x_i + 1)² +  (y_i -1)²

                             =  2 (x_i + 1)² + (y_i -1)² + y_i² – 2r^{2                                  ...............Eq1}

                 Replacing i with i+1 in the equation 1 we get

                   S_{i + 1}  =  2 (x_i+1 + 1)² + (y_i+1 -1)² + y_i+1² – 2r²

                             =  2 ((x_i + 1) + 1)² + (y_i+1 -1)² + y_i+1² – 2r²           (Since x_i+1 is equal to x_i + 1)

                             =  2 (x_i + 1)² +2 + 4(x_i + 1) + (y_i+1 -1)² + y_i+1² – 2r²   ...............Eq2

Subtracting equation 1 from equation 2 we get:   


S_{i + 1}  - S_i    =  2 (x_i + 1)² +2 + 4(x_i + 1) + (y_i+1 -1)² + y_i+1² – 2r² – (2 (x_i + 1)² + (y_i -1)² + y_i² – 2r²)

                    =  2 (x_i + 1)² +2 + 4(x_i + 1) + (y_i+1 -1)² + y_i+1² – 2r² – 2 (x_i + 1)² - (y_i -1)² - y_i² + 2r²

                    =  2 + 4(x_i + 1) + (y_i+1 -1)² + y_i+1² - (y_i -1)² - y_i²

                    =  4x_i + 6 + (y_i+1 -1)² + y_i+1² - (y_i -1)² - y_i²               ...............Eq3 

Therefore :

To find the initial value of the decision parameter S_i , Substitute i with 1 in equation 1.

           S₁  =  2 (x₁ + 1)² + (y₁ -1)² + y₁² – 2r²

                 =  2 (0 + 1)² + (r -1)² + r² – 2r²              ( *Since the starting pixel is (0,r) thus x₁=0 and y₁=r)

                 =  2 + r² +1 - 2r + r² – 2r²

                 =  3 + 2r² - 2r – 2r²

                 =  3 - 2r

Thus we calculate the decision parameter for the starting point (0,r) as  S_i = 3 – 2r. We use this to calculate the S_i+1 using the equations we derived.