Mid Point Circle Drawing Algorithm

Circle Drawing Algorithms-

 

In computer graphics, popular algorithms used to generate circle are-

 

 

1. Mid Point Circle Drawing Algorithm
2. Bresenham’s Circle Drawing Algorithm

 

In this article, we will discuss about Mid Point Circle Drawing Algorithm.

 

Mid Point Circle Drawing Algorithm-

 

Given the centre point and radius of circle, Mid Point Circle Drawing Algorithm attempts to generate the points of one octant.

 

The points for other octacts are generated using the eight symmetry property.

 

Procedure-

 

Given-

• Centre point of Circle = (X₀, Y₀)
• Radius of Circle = R

 

The points generation using Mid Point Circle Drawing Algorithm involves the following steps-

 

Step-01:

 

Assign the starting point coordinates (X₀, Y₀) as-

• X₀ = 0
• Y₀ = R

 

Step-02:

 

Calculate the value of initial decision parameter P₀ as-

P₀ = 1 – R

 

Step-03:

 

Suppose the current point is (X_k, Y_k) and the next point is (X_k+1, Y_k+1).

Find the next point of the first octant depending on the value of decision parameter P_k.

Follow the below two cases-

 

 

Step-04:

 

If the given centre point (X₀, Y₀) is not (0, 0), then do the following and plot the point-

• X_plot = X_c + X₀
• Y_plot = Y_c + Y₀

 

Here, (X_c, Y_c) denotes the current value of X and Y coordinates.

 

Step-05:

 

Keep repeating Step-03 and Step-04 until X_plot >= Y_plot.

 

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-

 

 

Also Read- Line Drawing Algorithms

 

PRACTICE PROBLEMS BASED ON MID POINT CIRCLE DRAWING ALGORITHM-

 

Problem-01:

 

Given the centre point coordinates (0, 0) and radius as 10, generate all the points to form a circle.

 

Solution-

 

Given-

• Centre Coordinates of Circle (X₀, Y₀) = (0, 0)
• Radius of Circle = 10

 

Step-01:

 

Assign the starting point coordinates (X₀, Y₀) as-

• X₀ = 0
• Y₀ = R = 10

 

Step-02:

 

Calculate the value of initial decision parameter P₀ as-

P₀ = 1 – R

P₀ = 1 – 10

P₀ = -9

 

Step-03:

 

As P_initial < 0, so case-01 is satisfied.

 

Thus,

• X_k+1 = X_k + 1 = 0 + 1 = 1
• Y_k+1 = Y_k = 10
• P_k+1 = P_k + 2 x X_k+1 + 1 = -9 + (2 x 1) + 1 = -6

 

Step-04:

 

This step is not applicable here as the given centre point coordinates is (0, 0).

 

Step-05:

 

Step-03 is executed similarly until X_k+1 >= Y_k+1 as follows-

 

Pk	Pk+1	(Xk+1, Yk+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)
Algorithm Terminates These are all points for Octant-1.

 

Algorithm calculates all the points of octant-1 and terminates.

Now, the points of octant-2 are obtained using the mirror effect by swapping X and Y coordinates.

 

Octant-1 Points	Octant-2 Points
(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)
These are all points for Quadrant-1.

 

Now, the points for rest of the part are generated by following the signs of other quadrants.

The other points can also be generated by calculating each octant separately.

 

Here, all the points have been generated with respect to quadrant-1-

 

Quadrant-1 (X,Y)	Quadrant-2 (-X,Y)	Quadrant-3 (-X,-Y)	Quadrant-4 (X,-Y)
(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)
These are all points of the Circle.

 

Problem-02:

 

Given the centre point coordinates (4, -4) and radius as 10, generate all the points to form a circle.

 

Solution-

 

Given-

• Centre Coordinates of Circle (X₀, Y₀) = (4, -4)
• Radius of Circle = 10

 

As stated in the algorithm,

• 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.

Now, we find the values of X_plot and Y_plot using the formula given in Step-04 of the main algorithm.

 

The following table shows the generation of points for Quadrant-1-

• X_plot = X_c + X₀ = 4 + X₀
• Y_plot = Y_c + Y₀ = 4 + Y₀

 

(Xk+1, Yk+1)	(Xplot, Yplot)
(0, 10)	(4, 14)
(1, 10)	(5, 14)
(2, 10)	(6, 14)
(3, 10)	(7, 14)
(4, 9)	(8, 13)
(5, 9)	(9, 13)
(6, 8)	(10, 12)
(8, 6)	(12, 10)
(9, 5)	(13, 9)
(9, 4)	(13, 8)
(10, 3)	(14, 7)
(10, 2)	(14, 6)
(10, 1)	(14, 5)
(10, 0)	(14, 4)
These are all points for Quadrant-1.

 

The following table shows the points for all the quadrants-

 

Quadrant-1 (X,Y)	Quadrant-2 (-X,Y)	Quadrant-3 (-X,-Y)	Quadrant-4 (X,-Y)
(4, 14)	(4, 14)	(4, -6)	(4, -6)
(5, 14)	(3, 14)	(3, -6)	(5, -6)
(6, 14)	(2, 14)	(2, -6)	(6, -6)
(7, 14)	(1, 14)	(1, -6)	(7, -6)
(8, 13)	(0, 13)	(0, -5)	(8, -5)
(9, 13)	(-1, 13)	(-1, -5)	(9, -5)
(10, 12)	(-2, 12)	(-2, -4)	(10, -4)
(12, 10)	(-4, 10)	(-4, -2)	(12, -2)
(13, 9)	(-5, 9)	(-5, -1)	(13, -1)
(13, 8)	(-5, 8)	(-5, 0)	(13, 0)
(14, 7)	(-6, 7)	(-6, 1)	(14, 1)
(14, 6)	(-6, 6)	(-6, 2)	(14, 2)
(14, 5)	(-6, 5)	(-6, 3)	(14, 3)
(14, 4)	(-6, 4)	(-6, 4)	(14, 4)
These are all points of the Circle.

 

Advantages of Mid Point Circle Drawing Algorithm-

 

The advantages of Mid Point Circle Drawing Algorithm are-

• It is a powerful and efficient algorithm.
• The entire algorithm is based on the simple equation of circle X² + Y² = R².
• It is easy to implement from the programmer’s perspective.
• This algorithm is used to generate curves on raster displays.

 

Disadvantages of Mid Point Circle Drawing Algorithm-

 

The disadvantages of Mid Point Circle Drawing Algorithm are-

• 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.

 

Important Points   Circle drawing algorithms take the advantage of 8 symmetry property of circle. Every circle has 8 octants and the circle drawing algorithm generates all the points for one octant. The points for other 7 octants are generated by changing the sign towards X and Y coordinates. To take the advantage of 8 symmetry property, the circle must be formed assuming that the centre point coordinates is (0, 0). If the centre coordinates are other than (0, 0), then we add the X and Y coordinate values with each point of circle with the coordinate values generated by assuming (0, 0) as centre point.

 

To gain better understanding about Mid Point Circle Drawing Algorithm,

Watch this Video Lecture

 

Next Article- Bresenham Circle Drawing Algorithm

 

Get more notes and other study material of Computer Graphics.

Watch video lectures by visiting our YouTube channel LearnVidFun.