Mid Point Circle Drawing Derivation
(Algorithm)
The mid point circle algorithm is used to determine the pixels needed
for rasterizing a circle while drawing a circle on a pixel screen.
In this technique algorithm determines the mid point between the
next 2 possible consecutive pixels and then checks whether the mid
point in inside or outside the circle and illuminates the pixel
accordingly.
This is how a pixel screen is represented:
A circle is highly symmetrical and can be divided into 8 Octets on
graph. Lets take center of circle at Origin i.e (0,0) :
We need only to conclude the pixels of any one of the octet rest we
can conclude because of symmetrical properties of circle.
Let us Take Quadrant 1:
Radius = OR = r
Radius = x intercept = y intercept
At point R
coordinate of x = coordinate of y or we can say x=y
let us take Octet 2 of quadrant 1
here first pixel would be (0,y)
here value of y intercept = radius (r)
as circle’s center is at origin
DERIVATION
let us assume we have plotted Pixel P whose coordinates are
Now we need to determine the next pixel.
We have chosen octet 2 where circle is moving forward and
downwards so y can never be increased, either it can be same or
decremented. Similarly x will always be increasing as circle is moving
forward too.
So y is needed to be decided.
Now we need to decide whether we should go with point N or S.
For that decision Mid Point circle drawing technique will us decide our
next pixel whether it will be N or S.
As is the next most pixel of therefore we can write,
And similarly in this case.
Let M is the midpoint between and .
And coordinates of point (M) are
Equation of Circle with Radius r
(x– h)2 + (y – k)2 = r2
When coordinates of centre are at Origin i.e., (h=0, k=0)
x2 + y2 = r2 (Pythagoras theorem)
Function of Circle Equation
F(C) = x2 + y2 - r2
Function of Midpoint M (xk+1 , yk -1/2) in circle equation
F(M)= xk+12 + (yk -1/2)2 - r2
= (xk+1)2 + (yk -1/2)2 - r2
The above equation is too our decision parameter pk
Pk = (xk+1)2 + (yk -1/2)2 - r2 …….(i)
To find out the next decition parameter we need to get Pk+1
Pk+1 = (xk+1+1)2 + (yk+1 -1/2)2 - r2
Now,
Pk+1- Pk = (xk+1+1)2 + (yk+1 -1/2)2 - r2
-[(xk+1)2 + (yk -1/2)2 - r2]
= ((xk+1)+1)2 + (yk+1 -1/2)2
- (xk+1)2 - (yk -1/2)2
= (xk+1)2 + 1 +2(xk+1) + yk+12 +(1/4) - yk+1
- (xk+1)2 - yk2 – (1/4) + yk+1
= 2(xk+1) + yk+12 - yk2 - yk+1 + yk +1
= 2(xk+1) +( yk+12 - yk2 ) - (yk+1 - yk) +1
Pk+1 = Pk + 2(xk+1)+( yk+12 - yk2 ) - (yk+1 - yk) +1 …..(ii)
Now let us conclude the initial decision parameter
For that we have to choose coordinates of starting point
i.e. (0,r)
Put this in (i) i.e. Pk
Pk = (xk+1)2 + (yk -1/2)2 - r2
P0 = (0+1)2 + (r -1/2)2 - r2
= 1 + r2 + ¼ - r – r2
=1+¼-r
…..(initial decision parameter)
Now If Pk ≥ 0 that means midpoint is outside the circle and S is
closest pixel so we will choose S (xk+1,yk-1)
That means yk+1 = yk-1
Putting coordinates of S in (ii) then,
Pk+1 = Pk + 2(xk+1)+( yk-12 - yk2 ) - (yk-1 - yk) +1
= Pk + 2(xk+1)+( yk -1)2 - yk2 ) - ((yk-1) - yk) +1
= Pk + 2(xk+1)+yk 2+1-2yk - yk2 - yk+1 + yk +1
= Pk + 2(xk+1)-2yk +2 + 1
= Pk + 2(xk+1)-2(yk -1) + 1
As we know (xk+1 = xk+1) and (yk-1 = yk-1)
Therefore,
Pk+1 = Pk + 2xk+1 - 2yk-1 + 1
And if Pk < 0 that means midpoint is inside the circle and N is
closest pixel so we will choose N (xk+1 , yk)
i.e. yk+1 = yk
Now put coordinates of N in (ii)
Pk+1 = Pk + 2(xk+1)+( yk2 - yk2 ) - (yk - yk) +1
= Pk + 2(xk+1)+( yk2 - yk2 ) - (yk - yk) +1
= Pk + 2(xk+1) +1
as xk+1 = xk+1 , therefore,
Pk+1 = Pk + 2xk+1 +1
Hence we have derived the mid point circle drawing algorithm.
Credit: www.getsetcg.com
Mid Point Circle Drawing Algorithm
Given the center point and radius of circle,
Mid-Point Circle Drawing Algorithm attempts to generate the points of one
octant.
The points for other octets are generated using the eight-symmetry property.
Procedure-
Given-
• Centre point of Circle = (X0, Y0)
• Radius of Circle = R
The points generation using Mid-Point Circle Drawing Algorithm involves the following
steps-
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 P k.
Follow the below two cases-
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-
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 (X0, Y0) = (0, 0)
• Radius of Circle = 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
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 x Xk+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 Xk+1 >= Yk+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 (X0, Y0) = (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 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
(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 X2 + Y2 = R2.
• 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 center point coordinates is (0,
0).
If the center 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 center
point.
