Home »
Computer Graphics
Mid-Point Circle Algorithm in Computer Graphics
Computer Graphics | Mid-Point Circle Algorithm: In this tutorial, we are going to learn about the mid-point circle drawing algorithm. Here, we will be studying about its algorithm and how it is implemented in the drawing of a circle. Apart from that, the pros and cons of this algorithm are also mentioned.
By Monika Sharma Last updated : April 05, 2024
What is a circle?
A circle is defined as a set of points that all are the same distance from a common point known as the center and the distance from the center of the circle to any point on its circumference is called a radius.
It is an eight-way symmetric figure which can be divided into four quadrants and each quadrant has two octants. This symmetry helps in the implementation of any circle drawing algorithm.
Introduction to Mid-Point Circle Drawing Algorithm
In computer graphics, the mid-point circle drawing algorithm is used to calculate all the perimeter points of a circle. In this algorithm, the mid-point between the two pixels is calculated which helps in calculating the decision parameter.
The value of the decision parameter will decide which pixel should be chosen for drawing the circle.
This algorithm only calculates the points for one octant and the points for other octants are generated using the eight-way symmetry for the circle.
Working of the Mid-Point Circle Drawing Algorithm
The algorithm works in the following way:
Suppose a mid-point with coordinates (x', y') is put in the general equation of the circle is
x2 + y2 - r2 = 0
gives these three values,
- If 0 : the given point lies on the circle boundary, then any pixel can be chosen.
- If < 0 : the given point lies inside the circle boundary, then the upper pixel can be chosen.
- If > 0 : the given point lies outside the circle boundary, then the lower pixel is chosen.
Let there be two pixels:
One pixel which is outside (A), and the other pixel which is inside (B) the circle boundary,
Let their coordinates be:
For A: (xk+1, yk)
and
For B: (xk+1, yk-1)
Derivation
Then, the co-ordinates of mid-point be
MP= [((xk+1+xk+1)/2) , ((yk+yk-1) /2)]
(xk +1 , yk-1 / 2)
Now, put MP in the equation of circle x2 + y2 - r2 = 0
(xk +1 )2 + (yk-1 / 2)2 - r2
Let us define this equation as the decision parameter, using the mid-point MP:
Pk = ( xk+1 )2 + ( yk-1 / 2 )2 - r2 -----(1)
Let us define the successive decision parameter, Pk+1:
Pk+1 = ( xk+1 + 1 )2 + ( yk+1-1 / 2 )2 - r2 -----(2)
Subtracting eq.(1) from eq.(2);
Pk+1- Pk = ( xk+1+1 )2 + ( yk+1-1 / 2 )2- r2 - [ (xk+1)2 + ( yk-1 /2 )2 - r2]
Now put xk+1 = xk+1
= (xk+1 + 1)2 + (yk+1-1 / 2)2 - r2 - [ (xk+1)2 + (yk-1 / 2)2 - r2 ]
= (xk+1 + 1)2 - (xk+1)2 + ( yk+1-1 / 2 )2- ( yk-1 / 2 )2
Pk+1= Pk + 2xk +3 + (yk+1)2 – yk+1- (yk)2 + yk
If Pk < 0: yk+1 = yk (choose point A)
Pk+1= Pk+ 2xk + 3
If Pk > 0: yk+1 = yk - 1 (choose point B)
Pk+1 = Pk + 2xk + 2yk + 5
Let us calculate the initial decision parameter (P0) where the initial points will be defined as (0, r) [which is the first point to be plotted of the first octant].
On putting these coordinates in eq. (1) in place of xk and yk, we get:
P0= ( 0 + 1 )2 + ( r-1 / 2 )2 - r2
P0 = 5/4 - r
If r is an integer:
P0 = 1 - r
If r is a floating point:
P0 = 5/4 - r
The Mid-Point Circle Drawing Algorithm
Step 1: Start.
Step 2: Declare x, y, r, xc , yc , P as variables, where (xc , yc) are coordinates of the center.
Step 3: Put x = 0 and y = r
Step 4: Repeat the steps while x ≤ y;
Step 5: Plot (x, y).
Step 6: if (P < 0):
Set P = P + 2x + 3
else if (P >= 0):
Set P = P + 2(x-y) + 5
y = y - 1
Step 7: Do x = x + 1
Step 8: End
Formulas used:
For Pk < 0 :
Pk+1=Pk+ 2xk+3
For Pk ≥ 0 :
Pk + 2xk+2yk+5
Advantages
- The mid-point circle algorithm is an efficient algorithm in drawing a circle.
- The implementation of the algorithm is easy from the programmer’s point of view.
Disadvantages
- The time consumption of this algorithm is high.