Circle Drawing Techniques


Circle A circle is the set of points in a plane that are equidistant from a given point O. The distance r from the center is called the radius, and the point O is called the center. Twice the radius is known as the diameter

computer graphics  Circle Drawing Techniques

The angle a circle subtends from its center is a full angle, equal to 360° or radians.

A circle has the maximum possible area for a given perimeter, and the minimum possible perimeter for a given area.

The perimeter C of a circle is called the circumference, and is given by

C=2 π r

Circle Drawing Techniques First of all for circle drawing we need to know what the input will be. Well the input will be one center point (x, y) and radius r. Therefore, using these two inputs there are a number of ways to draw a circle. They involve understanding level very simple to complex and reversely time complexity inefficient to efficient. We see them one by one giving comparative study.

Circle drawing using Cartesian coordinates This technique uses the equation for a circle on radius r centered at (0, 0) given as:

computer graphics  Circle Drawing Techniques

2 22

x + y= r , an obvious choice is to plot

y=±

Obviously in most of the cases the circle is not centered at (0, 0), rather there is a center point (xc, yc); other than (0, 0). Therefore the equation of the circle having center at point (xc, yc):

computer graphics  Circle Drawing Techniques

(x- xc) 2 + (y-yc)2 = r 2, which implies that ,

y = yc ±

Using above equation a circle can easily be drawn. The value of x varies from r-xc to r+xc. and y will be calculated using above formula. Using this technique a simple algorithm will be:

Circle1 (xcenter, ycenter, radius)

for x = radius – xcenter to radius + xcenter

y = xc +

drawPixel (x, y)

y = xc -

drawPixel (x, y)

This works, but is inefficient because of the multiplications and square root operations. It also creates large gaps in the circle for values of x close to r as shown in the above figure.

Circle drawing using Polar

coordinates A better approach, to eliminate unequal spacing as shown in above figure is to calculate points along the circular boundary using polar coordinates r and θ. Expressing the circle

equation in parametric polar form yields the pair of equations

x = xc + r cos θ y = yc + r sin θ

Using above equation circle can be plotted by calculating x and y coordinates as θ takes values from 0 to 360 degrees or 0 to 2π. The step size chosen for θ depends on the application and the display device. Larger angular separations along the circumference can be connected with straight-line segments to approximate the circular path. For a more continuous boundary on a raster display, we can set the step size at 1/r. This plots pixel positions that are approximately one unit apart.

Now let us see how this technique can be sum up in algorithmic form.

Circle2 (xcenter, ycenter, radius)

for θ = 0 to 2π step 1/r x = xc + r * cos θ y = yc+ r * sin θ drawPixel (x, y)

Again this is very simple technique and also solves problem of unequal space but unfortunately this technique is still inefficient in terms of calculations involves especially floating point calculations.

computer graphics  Circle Drawing Techniques

computer graphics  Circle Drawing Techniques

Calculations can be reduced by considering the symmetry of circles. The shape of circle is similar in each quadrant. We can generate the circle section in the second quadrant of the xy-plane by noting that the two circle sections are symmetric with respect to the y axis and circle sections in the third an fourth quadrants can be obtained from sections in the first and second quadrants by considering symmetry about the x axis. We can take this one step further and note that there is also symmetry between octants. Circle sections in adjacent octants within one quadrant are symmetric with respect to the 45o line dividing the two octants. These symmetry conditions are illustrated in above figure.

Therefore above algorithm can be optimized by using symmetric octants. Lets see:

Circle2 (xcenter, ycenter, radius)

for θ = 0 to π / 4 step 1/r

x = r * cos θ

y = r * sin θ

DrawSymmetricPoints (xcenter, ycenter, x, y)

DrawSymmeticPoints (xcenter, ycenter, x, y)

Plot ( x + xcenter, y + ycenter ) Plot ( y + xcenter, x + ycenter ) Plot ( y + xcenter, -x + ycenter ) Plot ( x + xcenter, -y + ycenter ) Plot ( -x + xcenter, -y + ycenter) Plot ( -y + xcenter, -x + ycenter) Plot ( -y + xcenter, x + ycenter) Plot ( -x + xcenter, y + ycenter)

Hence we have reduced half the calculations by considering symmetric octants of the circle but as we discussed earlier inefficiency is still there and that is due to the use of floating point calculations. In next algorithm we will try to remove this problem.

6.5 Midpoint circle Algorithm As in the Bresenham line drawing algorithm we derive a decision parameter that helps us to determine whether or not to increment in the y coordinate against increment of x coordinate or vice versa for slope > 1. Similarly here we will try to derive decision parameter which can give us closest pixel position.

Let us consider only the first octant of a circle of radius r centered on the origin. We begin by plotting point (r, 0) and end when x < y.

The decision at each step is whether to choose the pixel directly above the current pixel or the pixel; which is above and to the left (8-way stepping).

Assume:

computer graphics  Circle Drawing Techniques

Pi = (xi, yi) is the current pixel. Ti = (xi, yi +1) is the pixel directly above Si = (xi -1, yi +1) is the pixel above and to the left.

To apply the midpoint method, we define a circle function:

fcircle(x, y) = x2 + y2 – r 2

Therefore following relations can be observed:

< 0, if (x, y) is inside the circle boundary f circle (x, y) = 0, if (x, y) is on the circle boundary

> 0, if (x, y) is outside the circle boundary The circle function tests given above are performed for the midpoints between pixels near the circle path at each sampling step. Thus, the circle function is the decision parameter in the midpoint algorithm, and we can set up incremental calculations for this function as we did in the line algorithm.

Figure given above shows the midpoint between the two candidate pixels at sampling position xk+1. Assuming we have just plotted the pixel at (xk, yk), we next need to determine whether the pixel at position (xk + 1, yk), we next need to determine whether the pixel at position (xk+1, yk) or the one at position (xk+1, yk-1) is closer to the circle. Our decision parameter is the circle function evaluated at the midpoint

Xk Xk+1

between these two pixels:

Pk = f circle ( xk + 1, yk – ½ ) Pk= ( xk + 1) 2+ ( yk – ½ ) 2–r 2 …………………………( 1)

If pk < 0, this midpoint is inside the circle and the pixel on scan line yk is closer to the circle boundary. Otherwise, the mid position is outside or on the circle boundary, and we select the pixel on scan-line yk-1.

Successive decision parameters are obtained using incremental calculations. We obtain a recursive expression for the next decision parameter by evaluating the circle function at sampling position xk+2= xk+1+1=xk+1+1 = xk+2:

Pk+1= f circle ( xk+1+ 1, yk+1- ½) Pk+1= [( xk + 1) + 1] 2+ ( yk+1- ½) 2– r 2…………………………( 2)

Subtracting (1) from (2), we get

Pk+1-Pk= [( xk + 1) + 1] 2+ ( yk+1- ½ ) 2– r 2–( xk + 1) 2- ( yk – ½ ) 2+ r 2 or

computer graphics  Circle Drawing Techniques

Pk+1= Pk + 2( xk + 1 ) + ( y2k+1 – y 2k ) – ( yk+1- yk ) + 1

Where yk+1 is either yk or yk-1, depending on the sign of Pk. Therefore, if Pk < 0 or negative then yk+1 will be yk and the formula to calculate Pk+1 will be:

Pk+1= Pk + 2( xk + 1 ) + ( y2k – y 2k ) – ( yk – yk ) + 1 Pk+1= Pk + 2( xk + 1 ) + 1

Otherwise, if Pk > 0 or positive then yk+1 will be yk-1and the formula to calculate Pk+1 will be:

Pk+1= Pk + 2( xk + 1 ) + [ (y k -1)2- y 2k ] – ( yk -1- yk ) +1 Pk+1= Pk + 2( xk + 1 ) + (y2 k – 2 y k +1- y 2k ] – ( yk -1- yk) +1 Pk+1= Pk + 2( xk + 1 ) – 2 y k + 1 + 1 +1 Pk+1= Pk + 2( xk + 1 ) – 2 y k + 2 +1 Pk+1= Pk + 2( xk + 1 ) – 2 ( y k– 1 ) + 1

Now a similar case that we observe in line algorithm is that how would starting Pk be evaluated. For this at the start pixel position will be ( 0, r ). Therefore, putting this value is equation , we get

P0= ( 0+ 1) 2+ ( r – ½ ) 2–r 2

P0= 1+ r2- r + ¼ –r 2 P0= 5/4–r If radius r is specified as an integer, we can simply round p0 to: P0= 1–r Since all increments are integer. Finally sum up all in the algorithm:

MidpointCircle (xcenter, ycenter, radius)

y = r; x = 0; p = 1 – r; do

DrawSymmetricPoints (xcenter, ycenter, x, y) x =x +1 If p < 0 Then

p= p+ 2*( x + 1) + 1

else y=y-1 p= p+ 2*( x + 1) –2*( y – 1) + 1

while( x < y )

Now let us consider an example to calculate first octant of the circle using above algorithm; while one quarter is displayed where you can observe that exact circle is passing between the points calculated in a raster circle.

Example:

xcenter= 0 ycenter= 0 radius= 10

p x Y
-9 0 10
-6 1 10
-1 2 10
6 3 10
-3 4 9
8 5 9
5 6 8
6 7 7

computer graphics  Circle Drawing Techniques

VN:F [1.9.14_1148]
Rating: 0.0/10 (0 votes cast)
VN:F [1.9.14_1148]
Rating: +1 (from 1 vote)