.
Circle Generation Algorithms
Defining a Circle
Defining a circle using Polynomial Method
Defining a circle using Polar Co-ordinates
Bresenham's Circle Algorithm
Mid Point Circle Algorithm
.
Defining a Circle
Circle is an eight-way symmetric figure.
The shape of circle is the same in all quadrants. In each quadrant, there are
two octants.
If the calculation of the point of one octant is done, then the other seven
points can be calculated easily by using the concept of eight-way
symmetry.
For drawing circle, considers it at the origin. If a point is P1(x, y), then the
other seven points will be given as follows.
So we will calculate only 45° arc. From which the whole circle can be
determined easily.
.
Defining a Circle
.
Defining a Circle
If we want to display circle on screen then the putpixel function is used for
eight points as shown below:
putpixel (x, y, color)
putpixel (x, -y, color)
putpixel (-x, y, color)
putpixel (-x, -y, color)
putpixel (y, x, color)
putpixel (y, -x, color)
putpixel (-y, x, color)
putpixel (-y, -x, color)
Eight-way symmetry of circle
.
Defining a Circle
Example: Let we determine a point (2, 7) of the circle then other points
will be (2, -7), (-2, -7), (-2, 7), (7, 2), (-7, 2), (-7, -2), (7, -2)
These seven points are calculated by using the property of reflection. The
reflection is accomplished by reversing (x, y) co-ordinates.
There are two standards methods of mathematically defining a circle
centered at the origin. Defining a circle using Polynomial Method and
Defining a circle using Polar Co-ordinates
.
Defining a Circle using Polynomial Method
The first method defines a
circle with the second-order
polynomial equation as
shown in fig:
y2 = r2 - x2
Where x = the x coordinate,
y = the y coordinate and r =
the circle radius
With the method, each x
coordinate in the sector, from
90° to 45°, is found by
stepping x from 0 to & each
y coordinate is found by
evaluating sqrt(r2 - x2) for
each step of x.
.
Defining a Circle using Polynomial Method
Algorithm
Step1: Set the initial variables
r = circle radius
(h, k) = coordinates of circle center
x=0
i = step size
xend = r/√2
Step2: Test to determine whether the entire circle has been scan-converted.
If (x > xend) then stop.
Step 3: Compute y = √(r2-x2)
Step4: Plot the eight points found by symmetry concerning the center (h,
k) at the current (x, y) coordinates.
Plot (x + h, y +k); Plot (-x + h, -y + k); Plot (y + h, x + k); Plot (-y + h, -x + k);
Plot (-y + h, x + k); Plot (y + h, -x + k); Plot (-x + h, y + k); Plot (x + h, -y + k)
.
Defining a Circle using Polynomial Method
Algorithm
Step 5: Increment x = x + i
Step 6: Go to step 2.
Step 7: END
Example: h = 200, k = 200, r = 100;
.
Defining a Circle using Polar Co-ordinates
The second method of defining a circle makes use of polar coordinates as
shown in fig:
x=r cos θ y = r sin θ
Where θ=current angle, r = circle radius, x = x coordinate, y = y coordinate
By this method, θ is stepped from 0 to ∏/4 & each value of x & y is
calculated.
.
Defining a Circle using Polar Co-ordinates
Algorithm
Step1: Set the initial variables:
r = circle radius; (h, k) = coordinates of the circle center
i = step size; θ_end = ∏/4; θ=0
Step2: If θ>θend then stop.
Step 3: Compute x = r * cos(θ) y = r*sin(θ)
Step4: Plot the eight points, found by symmetry i.e., the center (h, k), at
the current (x, y) coordinates.
Plot (x + h, y +k); Plot (-x + h, -y + k); Plot (y + h, x + k);
Plot (-y + h, -x + k); Plot (-y + h, x + k); Plot (y + h, -x + k)
Plot (-x + h, y + k); Plot (x + h, -y + k)
• Step5: Increment θ = θ+i
• Step6: Go to step 2.
.
Bresenham's Circle Algorithm
Scan-Converting a circle using Bresenham's algorithm works as follows:
Points are generated from 90° to 45°, moves will be made only in the +x &
-y directions as shown in fig:
.
Bresenham's Circle Algorithm
We cannot display a continuous arc on the raster display. Instead, we have
to choose the nearest pixel position to complete the arc.
The best approximation of the true circle will be described by those pixels
in the raster that falls the least distance from the true circle. We want to
generate the points from 90° to 45°.
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).
Let us assume we have a point p (x, y) on the boundary of the circle and
with r radius satisfying the equation f (x, y) = 0
We assume, The distance between point P3 and circle boundary = d1 and
the distance between point P2 and circle boundary = d2
.
Bresenham's Circle Algorithm
.
Bresenham's Circle Algorithm
.
Bresenham's Circle Algorithm
Now, if we select point P3 then circle equation will be-
d1 = (xk +1)2 + (yk)2 – r2
{Value is +ve, because the point is outside the circle}
If we select point P2 then circle equation will be-
d2 = (xk +1)2 + (yk –1)2 – r2
{Value is -ve, because the point is inside the circle}
Now, we will calculate the decision parameter (dk) = d1 + d2
dk = (xk +1)2 + (yk)2 – r2 + (xk +1)2 + (yk –1)2 – r2
= 2(xk +1)2 + (yk)2+ (yk -1)2 – 2r2 …………………… (1)
If (dk < 0) then Point P3 is closer to circle boundary, and the final
coordinates are- (xk +1, yk) = (xk +1, yk)
If (dk >= 0) then Point P2 is closer to circle boundary, and the final
coordinates are- (xk +1, yk) = (xk +1, yk - 1)
.
Bresenham's Circle Algorithm
Now, we will find the next decision parameter (dk+1)
(dk+1) = 2(xk+1 +1)2 + (yk+1)2+ (yk+1 -1)2 – 2r2 …………(2)
Now, we find the difference between decision parameter equation (2) –
equation (1)
(dk+1) – (dk) = 2(xk+1+1)2 + (yk+1)2+ (yk+1 –1)2 – 2r2 – 2(xk +1)2 +
(yk)2+ (yk– 1)2 – 2r2
(dk+1) = dk + 4xk + 2(yk+12– yk2) –2 (yk+1 – yk) + 6
Now, we check following two conditions for decision parameter-
Condition 1: If(dk < 0) then yk+1 = yk (We select point P3)
(dk+1) = dk + 4xk + 2(yk2– yk2) – 2(yk – yk) + 6 = dk + 4xk + 6
Condition 2: If(dk >= 0) then yk+1 = yk -1 (We select point P2)
(dk+1) = dk + 4xk + 2{(yk– 1)2– yk2} – 2{(yk– 1) – yk} + 6
= dk + 4(xk – yk) + 10
.
Bresenham's Circle Algorithm
If it is assumed that the circle is centered at the origin, then at the first step
x = 0 & y = r.
Now, we calculate initial decision parameter (d0)
d0 = d 1 + d 2
d0 = {12 +r2– r2} + {12 +(r – 1)2 – r2}
d0 = 3 – 2r
Thereafter, if di<0,then only x is incremented.
xi+1=xi+1 di+1=di+ 4xi+6
if di≥0,then x & y are incremented
xi+1=xi+1 yi+1 =yi+ 1
di+1=di+ 4 (xi-yi)+10
.
Bresenham's Circle Algorithm
Algorithm
Step1: Start Algorithm
Step2: Declare p, q, x, y, r, d variables
p, q are coordinates of the center of the circle and r is the radius of the
circle
Step3: Enter the value of r
Step4: Calculate d = 3 - 2r
Step5: Initialize x=0 and y= r
Step6: Check if the whole circle is scan converted
If (x > = y) then Stop
Step7: Plot eight points by using concepts of eight-way symmetry. Current
active pixel is (x, y).
putpixel (x+p, y+q); putpixel (y+p, x+q); putpixel (-y+p, x+q); putpixel (-x+p, y+q);
putpixel (-x+p, -y+q); putpixel (-y+p, -x+q); putpixel (y+p, -x+q); putpixel (x+p, -y-q)
.
Bresenham's Circle Algorithm
Algorithm
Step8: Find location of next pixels to be scanned
If (d < 0)
then d = d + 4x + 6
increment x = x + 1
y=y
If d ≥ 0
then d = d + 4 (x - y) + 10
increment x = x + 1
decrement y = y – 1
Step9: Go to step 6
Step10: Stop Algorithm
.
Bresenham's Circle Algorithm
.
Bresenham's Circle Algorithm
.
Bresenham's Circle Algorithm
Advantage
The entire algorithm is based on the simple equation of Circle: X2
+Y2 = R2
It is easy to implement
Disadvantage
Like Mid Point Algorithm, accuracy of the generating points is an issue in
this algorithm.
This algorithm suffers when used to generate complex and high graphical
images.
There is no significant enhancement with respect to performance.
.
Bresenham's Circle Algorithm
Example
Plot 6 points of circle using Bresenham Algorithm. When radius of
circle is 10 units. The circle has centre (50, 50).
Solution
Let r = 10 (Given)
Step1: Take initial point (0, 10)
d = 3 - 2r = 3 - 2 * 10 = -17
d < 0, therefore d = d + 4x + 6 = -17 + 4 (0) + 6 = -11
Step2: Plot (1, 10)
d = d + 4x + 6 (∵ d < 0) = -11 + 4 (1) + 6 = -1
Step3: Plot (2, 10)
d = d + 4x + 6 (∵ d < 0) = -1 + 4 x 2 + 6 = 13
.
Bresenham's Circle Algorithm
Example
Step4: Plot (3, 9) d is > 0 so x = x + 1, y = y – 1
d = d + 4 (x-y) + 10 (∵ d > 0) = 13 + 4 (3-9) + 10 = 13 + 4 (-6) + 10
= 23-24=-1
Step5: Plot (4, 9)
d = -1 + 4x + 6 = -1 + 4 (4) + 6 = 21
Step6: Plot (5, 8)
d = d + 4 (x-y) + 10 (∵ d > 0) = 21 + 4 (5-8) + 10 = 21-12 + 10 = 19
So P1 (0,0)⟹(50,50)
P2 (1,10)⟹(51,60)
P3 (2,10)⟹(52,60)
P4 (3,9)⟹(53,59)
P5 (4,9)⟹(54,59); P6 (5,8)⟹(55,58)
.
Mid Point Circle Algorithm
It is based on the following function for testing the spatial relationship
between the arbitrary point (x, y) and a circle of radius r centered at the
origin:
Now, consider the coordinates of the point halfway between pixel T and
pixel S
This is called midpoint (xi+1,yi-1/2) and we use it to define a decision
parameter:
.
Mid Point Circle Algorithm
If Pi is -ve ⟹midpoint is inside the circle and we choose pixel T
If Pi is +ve ⟹midpoint is outside the circle (or on the circle) and we
choose pixel S.
The decision parameter for the next step is:
Since xi+1=xi+1, we have
.
Mid Point Circle Algorithm
If pixel T is chosen ⟹Pi<0 We have yi+1=yi
If pixel S is chosen ⟹Pi≥0 We have yi+1=yi-1
We can continue to simplify this in n terms of (xi,yi) and get
Now, initial value of Pi (0,r)from equation 2
.
Mid Point Circle Algorithm
.
Mid Point Circle Algorithm
.
Mid Point Circle Algorithm
It attempts to generate the points of one octant. The points for other octacts
are generated using the eight symmetry property.
Given-
Center Point = (X0, Y0)
Radius = R
Step-01: Assign the starting point coordinates (X0, Y0) as-
X0 = 0
Y0 = R
Step 02: Calculate the value of initial decision parameter P0 as-
P0 = 1 – R
Step 03: Suppose the current point is (Xk, Yk) and the next point is
(Xk+1, Yk+1).
Find the next point of the first octant depending on the value of decision
parameter Pk.
.
Mid Point Circle Algorithm
Follow the below two cases-
.
Mid Point Circle Algorithm
Step-04: If the given centre point (X0, Y0) is not (0, 0), then
do the following and plot the point-
Xplot = Xc + X0
Yplot = Yc + Y0
Here, (Xc, Yc) denotes the current value of X and Y
coordinates.
Step 05: Keep repeating Step-03 and Step-04 until
Xplot >= Yplot.
Step 06: Step-05 generates all the points for one octant. To
find the points for other seven octants, follow the eight
symmetry property of circle.
This is depicted by the following figure-
.
Mid Point Circle Algorithm
Advantage
It is a powerful and efficient algorithm.
The entire algorithm is based on the simple equation of circle X2
+ Y2 = R2.
It is easy to implement from the programmer’s perspective.
This algorithm is used to generate curves on raster displays.
Disadvantage
Accuracy of the generating points is an issue in this algorithm.
The circle generated by this algorithm is not smooth.
This algorithm is time consuming.
.
Mid Point Circle Algorithm
Example
Given the center point coordinates (0, 0) and radius as 10, generate all
the points to form a circle.
Solution
Given: Centre Coordinates of Circle (X0, Y0) = (0, 0)
Radius of Circle (R) = 10
Step 01: Assign the starting point coordinates (X0, Y0) as-
X0 = 0
Y0 = R = 10
Step 02: Calculate the value of initial decision parameter P0 as-
P0 = 1 – R
P0 = 1 – 10
P0 = -9
.
Mid Point Circle Algorithm
Step 03: As Pinitial < 0, so case-01 is satisfied. Thus,
Xk+1 = Xk + 1 = 0 + 1 = 1
Yk+1 = Yk = 10
Pk+1 = Pk + (2 * Xk+1) + 1 = -9 + (2 x 1) + 1 = -6
Step 04: This step is not applicable here as the given center point
coordinates is (0, 0).
Step 05: Step-03 is executed similarly until Xk+1 >= Yk+1 as follows-
.
Mid Point Circle Algorithm
Now, the points of octant-2 are obtained using the mirror effect by
swapping X and Y coordinates.
.
Mid Point Circle Algorithm
.
Mid Point Circle Algorithm
Example
Given the center point coordinates (4, -4) and radius as 10, generate all
the points to form a circle.
Solution
Given: Centre Coordinates of Circle (X0, Y0) = (4, -4)
Radius of Circle (R) = 10
We first calculate the points assuming the centre coordinates is (0, 0). At
the end, we translate the circle
Step-01, Step-02 and Step-03 are already completed in Problem-01.
• Step 04: Now, we find the values of Xplot and Yplot using the formula
given in Step-04 of the main algorithm.
• The following table shows the generation of points for Quadrant-1-
• Xplot = Xc + X0 = 4 + X0
• Yplot = Yc + Y0 = 4 + Y0
.
Mid Point Circle Algorithm
Example
Given the center point coordinates (4, -4) and radius as 10, generate all
the points to form a circle.
Solution
Step 05: Now, we find the values of Xplot and Yplot using the formula
given in Step-04 of the main algorithm.
The following table shows the generation of points for Quadrant-1-
• Xplot = Xc + X0 = 4 + X0
• Yplot = Yc + Y0 = 4 + Y0
.
Mid Point Circle Algorithm
Mid Point Circle Algo: Pseudocode
.
Bresenham vs Mid Point Circle Algorithm
Bresenham Algorithm: it is the optimized form of midpoint circle. it only
deals with integers because of which it consume less time as well as the
memory. This type of algorithm is efficient and accurate too because it
prevents from calculation of floating point.
Midpoint Algorithm: it prevents trigonometric calculations and only use
adopting integers. It checks the nearest possible integers with the help of
midpoint of pixels on the circle. But it still needs to use the floating point
calculations.
