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

Submitted by Monika Sharma, on April 24, 2020

## 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:

r_{y}^{2 }x^{2}+ r_{x}^{2 }y^{2 }- r_{x}^{2 }r_{y}^{2 }= 0 ...(1) where, r_{y }: semi-minor axis r_{x }: 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 r_{y}^{2 }x /2 r_{x}^{2 }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, r _{y})** 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; ( x_{k}+1, y_{k })

For B; ( x_{k}+1, y_{k}-1 )

Value for their mid-point will be:

M_{p}= [ ( (x_{k}+1 + x_{k}+1) / 2 ) ,( (y_{k }+ y_{k}-1) / 2) ]

= ( x_{k}+1 , y_{k}-1 / 2 )

Putting M_{p }in eqn (1):

r_{y}^{2 }(x_{k}+1)^{2} + r_{x}^{2 }( y_{k}-1 / 2 )^{2 }- r_{x}^{2 }r_{y}^{2}

Let us define this statement as our decision variable:

P_{k}= r_{y}^{2 }( x_{k}+1 )^{2} + r_{x}^{2 }( y_{k}-1 / 2 )^{2 }- r_{x}^{2 }r_{y}^{2} -----(2)

Successive parameter can be defined as:

P_{k+1 }= r_{y}^{2 }( x_{k+1}+1 )^{2} + r_{x}^{2 }( y_{k+1}-1 / 2 )^{2}- r_{x}^{2 }r_{y}^{2 } -----(3)

Now, subtract eqn (2) from eqn (3);

P_{k+1 }- P_{k} = [ r_{y}^{2 }( x_{k+1 }+ 1 )^{2} + r_{x}^{2 }( y_{k+1}-1 / 2 )^{2}- r_{x}^{2 }r_{y}^{2 }] - [ r_{y}^{2 }(x_{k}+1)^{2}+ r_{x}^{2}( y_{k}-1 / 2 )^{2}- r_{x}^{2 }r_{y}^{2 }] ^{ }

= r_{y}^{2 }[ (x_{k+1}+1)^{2 }- (x_{k}+1)^{2 }] + r_{x}^{2 }[ ( y_{k+1}-1 / 2 )^{2 }- ( y_{k}-1 / 2 )^{2 }]

As the x-coordinate remains same in both the pixels, put x_{k+1 }= x_{k}+1

P_{k+1}- P_{k} = r_{y}^{2 }[ (x_{k}+1+1)^{2 }- (x_{k}+1)^{2 }] + r_{x}^{2 }[ ( y_{k+1}-1 / 2 )^{2 }- ( y_{k}-1 / 2)^{2 }]

= r_{y}^{2 }[ 2x_{k }+ 3 ] + r_{x}^{2 }[ (y_{k+1})^{2 }- y_{k+1 }- (y_{k})^{2 }+ y_{k }]

P_{k+1 }=_{ }P_{k }+ r_{y}^{2 }[ 2x_{k }+ 3 ] + r_{x}^{2 }[ (y_{k+1})^{2 }- y_{k+1 }- (y_{k})^{2 }+ y_{k }]

If P_{k }< 0 : use y_{k+1 }= y_{k }(Choose point A)

P_{k+1 }=_{ }P_{k}+ r_{y}^{2 }[ 2x_{k }+ 3 ]

If P_{k }≥ 0: use y_{k+1 }= y_{k }-1_{ }(Choose point B)

P_{k+1 }=_{ }P_{k }+ r_{y}^{2 }[ 2x_{k }+ 3 ] + 2 [ 1 - y_{k }]

**Initial Decision Parameter**

Put initial point(0,r_{y}) in eq.(2)

P_{0}= r_{y}^{2 }(0+1)^{2} + r_{x}^{2}( r_{y}-1 /2)^{2 }- r_{x}^{2 }r_{y}^{2}P_{0} = r_{y}^{2 }+ r_{x}^{2}/4 - r_{y} r_{x}^{2}

**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; (x_{k}+1, y_{k}-1)

For Q; (x_{k}, y_{k}-1)

Value for their mid-point will be:

M_{p}= [ ( (x_{k}+1+ x_{k}) / 2 ), ( (y_{k}-1 y_{k}-1) / 2 ) ]

= ( x_{k}+1 / 2 , y_{k}-1 )

Putting M_{p }in eq.(1):

r_{y}^{2 }(x_{k}+1 / 2)^{2} + r_{x}^{2 }(y_{k}-1)^{2}- r_{x}^{2 }r_{y}^{2}

Let us define this statement as our decision variable:

P2_{k }= r_{y}^{2 }( x_{k}+1 /2)^{2} + r_{x}^{2 }(y_{k}-1)^{2 }- r_{x}^{2 }r_{y}^{2} ----(4)

Successive parameter can be defined as:

P2_{k+1}= r_{y}^{2 }( x_{k+1 }+ 1 / 2 )^{2} + r_{x}^{2 }( y_{k+1}-1 )^{2 }- r_{x}^{2 }r_{y}^{2 } ----(5)

Now, subtract eq.(4) from eq.(5);

P2_{k+1}- P2_{k} = [ r_{y}^{2 }(x_{k+1}+1/2)^{2} + r_{x}^{2 }(y_{k+1}-1)^{2}- r_{x}^{2}r_{y}^{2 }] - [ r_{y}^{2 }(x_{k}+1/2)^{2}+ r_{x}^{2 }(y_{k}-1)^{2 }- r_{x}^{2 }r_{y}^{2}] ^{ }

= r_{y}^{2 }[ (x_{k+1}+1 / 2 )^{2 }- ( x_{k}+1 / 2 )^{2 }] + r_{x}^{2 }[ (y_{k+1}-1)^{2 }- (y_{k}-1)^{2}]

As the y-coordinate remains same in both the pixels, put y_{k+1 }= y_{k}-1

P2_{k+1}- P2_{k} = r_{y}^{2 }[ (x_{k+1})^{2 }+ x_{k+1 }- (x_{k})^{2 }- x_{k }]+ r_{x}^{2 }[ 3 - 2y_{k }]

P2_{k+1 }=_{ }P2_{k }+ r_{y}^{2 }[ (x_{k+1})^{2 }+ x_{k+1 }- (x_{k})^{2 }- x_{k }]+ r_{x}^{2 }[ 3 - 2y_{k }]

If P2_{k }> 0: use x_{k+1}= x_{k }(Choose point Q)

P2_{k+1 }=_{ }P2_{k }- 2 y_{k+1 }r_{x}^{2} + r_{x}^{2}

If P2_{k }≤ 0: use x_{k+1 }= x_{k }+1_{ }(Choose point P)

P2_{k+1 }=_{ }P 2_{k}+ 2r_{y}^{2 }[2 x_{k+1}] - 2 y_{k+1 }r_{x}^{2} + r_{x}^{2}

**Initial Decision Parameter:**

Putting the ending point of region **R1**

Where, m > -1 i.e. (x, y) in eq.(4)

P2_{0 }= r_{y}^{2 }( x+1 / 2 )^{2} + r_{x}^{2 }(y-1)^{2 }- r_{x}^{2 }r_{y}^{2}

### Algorithm

Step 1: Start

Step 2: Declare r_{x} , r_{y }, x , y , m , dx , dy , P , P2.

Step 3: Initialize initial point of region1 as

x=0 , y = r_{y}

Step 4: Calculate P= r_{y}^{2 }+ r_{x}^{2 }/ 4 - r_{y} r_{x}^{2}

dx = 2 r_{y}^{2 }x

dy = 2 r_{x}^{2 }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 += _{ }r_{y}^{2 }[2x + 3 ]

Else

Update x = x + 1

y= y - 1

Step 7: When dx ≥ dy, plot region 2:

Step 8: Calculate P2 = r_{y}^{2 }( x+1 / 2)^{2} + r_{x}^{2 }(y -1)^{2}- r_{x}^{2}r_{y}^{2}

Step 9: Repeat till (y > 0)

If (P2 > 0)

Update y = y-1 (x will remain same)

P2 =_{ }P2 -2 y r_{x}^{2} + r_{x}^{2}

else

x = x+1

y = y-1

P2=_{ }P2+ 2 r_{y}^{2 }[2x] -2 y r_{x}^{2} + r_{x}^{2}

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.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions