Computer Graphics
Introduction to Computer Graphics
Circle Drawing Techniques
6.1 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 . 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
6.2 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.
6.3 Circle drawing using Cartesian coordinates
This technique uses the equation for a circle on radius r centered at (0, 0) given as:
x2 + y2 = r2,
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):
(x- xc) 2 + (y-yc)2 = r2, which
implies that ,
y = yc ±
Using above equation a circle can easily be drawn. The value of x varies from r-x c to
r+xc. and y will be calculated using above formula. Using this technique a simple
algorithm will be:
Computer Graphics
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.
6.4 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.
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
Computer Graphics
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 45 o 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.
2 2 2
Let us consider only the first octant of a circle of x +y -r =0 x=y
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
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 – r2
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 Yk X2+Y2-r2=0
just plotted the pixel at (xk, yk), we next need to determine Yk-1
whether the pixel at position (xk + 1, yk), we next need to
determine whether the pixel at position (x k+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 between these two pixels:
Xk Xk+1
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 y k 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 )
Computer Graphics
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
Pk+1 = Pk + 2( xk + 1 ) + ( y2k+1 - y2k ) – ( 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 - y2k ) – ( 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 - y2k ] – ( yk -1- yk ) + 1
Pk+1 = Pk + 2( xk + 1 ) + (y2 k - 2 y k +1 - y2k ] – ( 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 P k 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 + r 2 - 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
Computer Graphics
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 xY
-9 0 10
-6 1 10
-1 2 10
6 3 10
-3 4 9
8 5 9
5 6 8
6 7 7