Home »
Computer Graphics
Mid-Point Ellipse Algorithm in Computer Graphics
Computer Graphics | Mid-Point Ellipse Algorithm: In this tutorial, we are going to learn about the mid-point ellipse drawing algorithm. This article is all about how to draw an ellipse on a computer window and how it is implemented in the drawing of an ellipse is also mentioned.
By Monika Sharma Last updated : April 05, 2024
What is an ellipse?
Ellipse is defined as the geometric figure which is the set of all points on a plane whose distance from two fixed points known as the foci remains a constant.
It consists of two axes: major and minor axes where the major axis is the longest diameter and minor axis is the shortest diameter.
Unlike circle, the ellipse has four-way symmetry property which means that only the quadrants are symmetric while the octants are not.
Here, we will calculate the points for one quadrant while the points for the remaining three can be calculated using the former points.
Introduction to the Mid-Point Ellipse Drawing Algorithm
In computer graphics, the mid-point ellipse algorithm is an incremental method of drawing an ellipse. It is very similar to the mid-point algorithm used in the generation of a circle.
The mid-point ellipse drawing algorithm is used to calculate all the perimeter points of an ellipse. 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 determines whether the mid-point lies inside, outside, or on the ellipse boundary and the then position of the mid-point helps in drawing the ellipse.
Working of the Mid-Point Ellipse Drawing Algorithm
Now, for understanding the proper working of the algorithm, let us consider the elliptical curve in the first quadrant.
Also, consider the equation of ellipse:
ry2 x2 + rx2 y2 - rx2 ry2 = 0 ...(1)
where, ry : semi-minor axis
rx : semi-major axis
In the ellipse each quadrant is divided into two regions: R1 and R2 respectively.
We know that the slope of an ellipse is given by:
m =dx / dy = - (2 ry2 x /2 rx2 y ) = -1
The region R1 has the value of slope as m<-1 while R2 has the value of slope as m > -1.
The starting point for R1 will be (0, ry) and for R2, the initial points will become the ending points of R1, where the slope becomes greater than -1. Thats why we need to keep in check the value of slope while plotting the points for R1 to know whether we have reached R2 or not.
We will do the derivation for each region:
Derivation for Region 1:
Let us consider two pixels: one which is outside(A) and the other which is inside(B) respectively.
Let their coordinates be:
For A; ( xk+1, yk )
For B; ( xk+1, yk-1 )
Value for their mid-point will be:
Mp= [ ( (xk+1 + xk+1) / 2 ) ,( (yk + yk-1) / 2) ]
= ( xk+1 , yk-1 / 2 )
Putting Mp in eqn (1):
ry2 (xk+1)2 + rx2 ( yk-1 / 2 )2 - rx2 ry2
Let us define this statement as our decision variable:
Pk= ry2 ( xk+1 )2 + rx2 ( yk-1 / 2 )2 - rx2 ry2 -----(2)
Successive parameter can be defined as:
Pk+1 = ry2 ( xk+1+1 )2 + rx2 ( yk+1-1 / 2 )2- rx2 ry2 -----(3)
Now, subtract eqn (2) from eqn (3);
Pk+1 - Pk = [ ry2 ( xk+1 + 1 )2 + rx2 ( yk+1-1 / 2 )2- rx2 ry2 ] - [ ry2 (xk+1)2+ rx2( yk-1 / 2 )2- rx2 ry2 ]
= ry2 [ (xk+1+1)2 - (xk+1)2 ] + rx2 [ ( yk+1-1 / 2 )2 - ( yk-1 / 2 )2 ]
As the x-coordinate remains same in both the pixels, put xk+1 = xk+1
Pk+1- Pk = ry2 [ (xk+1+1)2 - (xk+1)2 ] + rx2 [ ( yk+1-1 / 2 )2 - ( yk-1 / 2)2 ]
= ry2 [ 2xk + 3 ] + rx2 [ (yk+1)2 - yk+1 - (yk)2 + yk ]
Pk+1 = Pk + ry2 [ 2xk + 3 ] + rx2 [ (yk+1)2 - yk+1 - (yk)2 + yk ]
If Pk < 0 : use yk+1 = yk (Choose point A)
Pk+1 = Pk+ ry2 [ 2xk + 3 ]
If Pk ≥ 0: use yk+1 = yk -1 (Choose point B)
Pk+1 = Pk + ry2 [ 2xk + 3 ] + 2 [ 1 - yk ]
Initial Decision Parameter
Put initial point(0,ry) in eq.(2)
P0= ry2 (0+1)2 + rx2( ry-1 /2)2 - rx2 ry2
P0 = ry2 + rx2/4 - ry rx2
Derivation for Region 2:
Let us consider two pixels: one which is outside(P) and the other which is inside(Q) respectively.
Let their coordinates be:
For P; (xk+1, yk-1)
For Q; (xk, yk-1)
Value for their mid-point will be:
Mp= [ ( (xk+1+ xk) / 2 ), ( (yk-1 yk-1) / 2 ) ]
= ( xk+1 / 2 , yk-1 )
Putting Mp in eq.(1):
ry2 (xk+1 / 2)2 + rx2 (yk-1)2- rx2 ry2
Let us define this statement as our decision variable:
P2k = ry2 ( xk+1 /2)2 + rx2 (yk-1)2 - rx2 ry2 ----(4)
Successive parameter can be defined as:
P2k+1= ry2 ( xk+1 + 1 / 2 )2 + rx2 ( yk+1-1 )2 - rx2 ry2 ----(5)
Now, subtract eq.(4) from eq.(5);
P2k+1- P2k = [ ry2 (xk+1+1/2)2 + rx2 (yk+1-1)2- rx2ry2 ] - [ ry2 (xk+1/2)2+ rx2 (yk-1)2 - rx2 ry2]
= ry2 [ (xk+1+1 / 2 )2 - ( xk+1 / 2 )2 ] + rx2 [ (yk+1-1)2 - (yk-1)2]
As the y-coordinate remains same in both the pixels, put yk+1 = yk-1
P2k+1- P2k = ry2 [ (xk+1)2 + xk+1 - (xk)2 - xk ]+ rx2 [ 3 - 2yk ]
P2k+1 = P2k + ry2 [ (xk+1)2 + xk+1 - (xk)2 - xk ]+ rx2 [ 3 - 2yk ]
If P2k > 0: use xk+1= xk (Choose point Q)
P2k+1 = P2k - 2 yk+1 rx2 + rx2
If P2k ≤ 0: use xk+1 = xk +1 (Choose point P)
P2k+1 = P 2k+ 2ry2 [2 xk+1] - 2 yk+1 rx2 + rx2
Initial Decision Parameter:
Putting the ending point of region R1
Where, m > -1 i.e. (x, y) in eq.(4)
P20 = ry2 ( x+1 / 2 )2 + rx2 (y-1)2 - rx2 ry2
Mid-Point Ellipse Algorithm
Step 1: Start
Step 2: Declare rx , ry , x , y , m , dx , dy , P , P2.
Step 3: Initialize initial point of region1 as
x=0 , y = ry
Step 4: Calculate P= ry2 + rx2 / 4 - ry rx2
dx = 2 ry2 x
dy = 2 rx2 y
Step 5: Update values of dx and dy after each iteration.
Step 6: Repeat steps while (dx < dy):
Plot (x,y)
if(P < 0)
Update x = x+1 ;
P += ry2 [2x + 3 ]
Else
Update x = x + 1
y= y - 1
Step 7: When dx ≥ dy, plot region 2:
Step 8: Calculate P2 = ry2 ( x+1 / 2)2 + rx2 (y -1)2- rx2ry2
Step 9: Repeat till (y > 0)
If (P2 > 0)
Update y = y-1 (x will remain same)
P2 = P2 -2 y rx2 + rx2
else
x = x+1
y = y-1
P2= P2+ 2 ry2 [2x] -2 y rx2 + rx2
Step 10: End
Advantages
- The mid-point ellipse algorithm has simple and easy implementation as it only includes addition operations.
Disadvantages
- This algorithm is time consuming.