Midpoint Circle Drawing Algorithm in Computer Graphics
The midpoint circle drawing algorithm helps us to calculate the complete perimeter points of a circle for the first octant. We can quickly find and calculate the points of other octants with the help of the first octant points. The remaining points are the mirror reflection of the first octant points.
This algorithm is used in computer graphics to define the coordinates needed for rasterizing the circle. The midpoint circle drawing algorithm helps us to perform the generalization of conic sections. Bresenham’s circle drawing algorithm is also extracted from the midpoint circle drawing algorithm. In the algorithm, we will use the 8-way symmetry property.
In this algorithm, we define the unit interval and consider the nearest point of the circle boundary in each step.
Let us assume we have a point a (p, q) on the boundary of the circle and with r radius satisfying the equation f_{c }(p, q) = 0
As we know the equation of the circle is –
f_{c }(p, q) = p^{2 }+ q^{2} = r^{2 } …………………………… (1)
If
f_{c }(p, q) < 0
then
The point is inside the circle boundary.
If
f_{c }(p, q) = 0
then
The point is on the circle boundary.
If
f_{c }(p, q) > 0
then
The point is outside the circle boundary.
In the figure, we calculate the mid-point (m). The midpoint appears between q_{k} and q_{k }-1.
The currentposition of the pixel = p_{k }+1
The next position of the pixel = (p_{k }+1, q_{k}) and (p_{k }+1, q_{k }- 1)
Now, we will calculate the decision parameter (d_{k})
d_{k }= (p_{k }+1, q_{k }– 1/2)
Now, we replace all the values with equation (1)
d_{k }= (p_{k }+1)^{2} + (q_{k }– 1/2)^{2} – r^{2 …………………………………… }(2)
Now, there should be two conditions.
Condition 1: If
d_{k }is negative
then
The midpoint (m) is inside the circle boundary
Condition 2: If
d_{k }is positive
then
The midpoint (m) is outside the circle boundary
Now, we find the next point of x coordinates. Then,
P_{k+1 }+1 = P_{k}+2
Now, we replace all the value of equation (2) with (k+1). We get-
d_{k+1 }= (p_{k+1 }+1)^{2} + (q_{k+1 }– 1/2)^{2} – r^{2 } ……………………………. (3)
Now, we will find the difference between
d_{k+1 }– d_{k }= {(p_{k+1 }+1)^{2} + (q_{k+1 }– 1/2)^{2} – r^{2}} – {(p_{k }+1)^{2} + (q_{k }– 1/2)^{2} – r^{2}}
= d_{k }+(2p_{k }+1) + (q_{k+1}^{2} – q_{k}^{2}) – (q_{k+1} – q_{k}) +1 …………………… (4)
Here, If
d_{k} isnegativethen d_{k+1}
then
2p_{k+1} +1
Otherwise
2p_{k+1} +1 – 2q_{k+1}
Now, the next coordinate for x and y points
2p_{k+1 }= 2p_{k }+2
2q_{k+1 }= 2q_{k }–2
Now, the initial decision parameter (d_{0}) at the position (p, q) = (0, r)
We put (0, r) in circle equation and we get-
d_{0} = (1, r – 1/2)
= (1 + (r –1/2)^{2} –r^{2})
= 5/4 –r
We only take integer value = 1 – r
Algorithm of Midpoint Circle Drawing
Step 1: Start.
Step 2: First, we allot the center coordinates (p_{0}, q_{0}) as follows-
P_{0} = 0
q_{0 }=r
Step 3: Now, we calculate the initial decision parameter d_{0 }-
_{ }d_{0 }= 1 – r
Step 4: Assume,the starting coordinates = (p_{k}, q_{k})
The next coordinates will be (p_{k+1}, q_{k+1})
Now, we find the next point of the first octant according to the value of the decision parameter (d_{k}).
Step 5: Now, we follow two cases-
Case 1: If
d_{k }< 0
then
p_{k+1 }=p_{k }+ 1
q_{k+1 }=q_{k }
d_{k+1 }= d_{k }+ 2 p_{k+1 }+ 1
Case 2: If
d_{k }>= 0
then
p_{k+1 }=p_{k }+ 1
q_{k+1 }=q_{k }–1
d_{k+1 }= d_{k }- 2 (q_{k+1 }+ 2 p_{k+1})+ 1
Step 6: If the center coordinate point (p_{0}, q_{0}) is not at the origin (0, 0) then we will draw the points as follow-
For x coordinate = x_{c }+ p_{0 }
For y coordinate = y_{c }+ q_{0 } {x_{c }andy_{c }containsthe current value of x and y coordinate}
Step 7: We repeat step 5 and 6 until we get x>=y.
Step 8: Stop.
Example: The center coordinates are (0, 0), and the radius of the circle is 10. Find all points of the circle by using the midpoint circle drawing algorithm?
Solution:
Step 1: The given center coordinates of the circle (p_{0, }q_{0}) = (0, 0)
Radius of the circle (r) = 10
Step 2: Now, we will determine the starting coordinates (p_{0, }q_{0}) as follows-
P_{0 }= 0
q_{0 }= r (radius) = 10
Step 3: Now, we will determine the initial decision parameter (d_{0})
_{ }d_{0 }= 1 –r
d_{0} = 1 –10
d_{0} = -9
Step 4: The initial parameter d_{0 }< 0 then, case 1 is satisfied.
p_{k+1 }=p_{k }+ 1 = 0 + 1 = 1
q_{k+1 }=q_{k }= 10
d_{k+1 }= d_{k }+ 2 p_{k+1 }+ 1 = -9 + 2(1) + 1 = -6
Step 5: The center coordinates of circle are already (0, 0). So, move to next step.
Step 6: We will execute step 4 until we get x >= y.
The table for coordinates of octant 1-
d_{k} | d_{k+1} | (p_{k+1},q_{k+1}) |
(0, 10) | ||
-9 | -6 | (1, 10) |
-6 | -1 | (2, 10) |
-1 | 6 | (3, 10) |
6 | -3 | (4, 9) |
-3 | 8 | (5, 9) |
8 | 5 | (6, 8) |
Now, we will determine the coordinates of the octant 2 by swapping the p and q coordinates.
Points of Octant 1 | Points of Octant 2 |
(0, 10) | (8, 6) |
(1, 10) | (9, 5) |
(2, 10) | (9, 4) |
(3, 10) | (10, 3) |
(4, 9) | (10, 2) |
(5, 9) | (10, 1) |
(6, 8) | (10, 0) |
Thus, we can find all the coordinates of the circle for all quadrants.
Quadrant 1 (p, q) | Quadrant 2 (-p, q) | Quadrant 3 (-p, -q) | Quadrant 4 (p, -q) |
(0, 10) | (0, 10) | (0, -10) | (0, -10) |
(1, 10) | (-1, 10) | (-1, -10) | (1, -10) |
(2, 10) | (-2, 10) | (-2, -10) | (2, -10) |
(3, 10) | (-3, 10) | (-3, -10) | (3, -10) |
(4, 9) | (-4, 9) | (-4, -9) | (4, -9) |
(5, 9) | (-5, 9) | (-5, -9) | (5, -9) |
(6, 8) | (-6, 8) | (-6, -8) | (6, -8) |
(8, 6) | (-8, 6) | (-8, -6) | (8, -6) |
(9, 5) | (-9, 5) | (-9, -5) | (9, -5) |
(9, 4) | (-9, 4) | (-9, -4) | (9, -4) |
(10, 3) | (-10, 3) | (-10, -3) | (10, -3) |
(10, 2) | (-10, 2) | (-10, -2) | (10, -2) |
(10, 1) | (-10, 1) | (-10, -1) | (10, -1) |
(10, 0) | (-10, 0) | (-10, 0) | (10, 0) |
Advantages of Midpoint circle drawing algorithm
- It is a powerful and efficient algorithm.
- The midpoint circle drawing algorithm is easy to implement.
- It is also an algorithm based on a simple circle equation (x^{2 }+ y^{2 }= r^{2}).
- This algorithm helps to create curves on a raster display.
Disadvantages of Midpoint circle drawing algorithm
- It is a time-consuming algorithm.
- Sometimes the points of the circle are not accurate.
Related Post:
- Scan Conversion of an Ellipse Computer Graphics
- Scan Conversion of a Circle Computer Graphics
- Bresenham’s Circle Drawing Algorithm in Computer Graphics
- Line Drawing Algorithm in Computer Graphics
- DDA line Drawing Algorithm in Computer Graphics
- 3D Rotation in Computer Graphics
- 2D Rotation in Computer Graphics
- Computer Graphics Tutorial
- Projection in Computer Graphics
- Animation in Computer Graphics