# Ellipse Algorithm | Computer Graphics

In this article, we are going to learn about **Ellipse generating algorithms in computer graphics** i.e. **Midpoint ellipse algorithm**. **Properties of ellipse** are also prescribed in this article.

Submitted by Abhishek Kataria, on August 25, 2018

## Properties of ellipse

Ellipse is defined as the locus of a point in a plane which moves in a plane in such a manner that the ratio of its distance from a fixed point called focus in the same plane to its distance from a fixed straight line called directrix is always constant, which should always be less than unity.

If the distance to the two foci from any point **P=(x,y)** on the ellipse are labeled **d _{1}** and

**d**then the general equation of the ellipse can be stated as-

_{2}**d**.

_{1}+d_{2}=constantFor expressing the distances **d _{1}** and

**d**in terms of focal coordinates

_{2}**F**and

_{1}**F**we have:-

_{2}**Ax**where

^{2}+By^{2}+Cxy+Dx+Ey+F=0**A, B, C, D,E, and F**are evaluated in terms of focal coordinates and dimensions of the major and minor axes of the ellipse.

## Midpoint ellipse algorithm

**The midpoint ellipse method** is applied throughout the first quadrant in two parts. Now let us take the start position at **(0,r _{y})** and step along the ellipse path in clockwise order throughout the first quadrant.

Ellipse function can be defined as:

**f _{ellipse}(x,y)=r_{y}^{2}x^{2}+r_{x}^{2}y^{2}-r_{x}^{2}r_{y}^{2}**

According to this there are some properties which have been generated that are:

**f**which means_{ellipse}(x,y)<0**(x,y)**is inside the ellipse boundary.**f**which means_{ellipse}(x,y)>0**(x,y)**is outside the ellipse boundary.**f**which means_{ellipse}(x,y)=0**(x,y)**is on the ellipse boundary.

### Initial decision parameter

In region **1** the initial value of a decision parameter is obtained by giving starting position = **(0,r _{y})**.

**i.e. p1 _{0}=r_{y}^{2}+1/4r_{x}^{2}-r_{x}^{2}r_{y}**

When we enter into a region **2** the initial position is taken as the last position selected in region **1** and the initial decision parameter in region 2 is then:

**p2 _{0}=r_{y}^{2}(x_{0}+1/2)^{2}+r_{x}^{2}(y_{0}-1)^{2}-r_{x}^{2}r_{y}^{2}**

### ALGORITHM

- Take the input and ellipse centre and obtain the first point on an ellipse centered on the origin as a (x,y
_{0})= (0,r_{y}). - Now calculate the initial decision parameter in region 1 as:
**p1**_{0}=r_{y}^{2}+1/4r_{x}^{2}-r_{x}^{2}r_{y} - At each
**x**position in region_{k}**1**perform the following task. If**p1**then the next point along the ellipse centered on_{k}<0**(0,0)**is**(x**._{k}+1,y_{k})**i.e. p1**_{k+1}=p1_{k}+^{2}r_{y}^{2}x_{k+1}+r_{y}^{2}

Otherwise the next point along the circle is (x_{k+1},y_{k}-1)**i.e. p1**_{k+1}=p1_{k}+2r_{y}^{2}x_{k+1}– 2r_{x}^{2}y_{k+1}+r_{y}^{2} - Now, again calculate the initial value in region 2 using the last point
**(x**calculated in a region 1 as :_{0},y_{0})**p2**_{0}=r_{y}^{2}(x_{0}+1/2)^{2}+r_{x}^{2}(y_{0}-1)^{2}-r_{x}^{2}r_{y}^{2} - At each
**y**position in region 2 starting at_{k}**k =0**perform the following task. If**p2**the next point along the ellipse centered on_{k}<0**(0,0)**is**(x**_{k}, y_{k-1})**i.e. p2**_{k+1}=p2_{k}-2r_{x}^{2}y_{k+1}+r_{x}^{2}

Otherwise the next point along the circle will be**(x**_{k+1},y_{k}-1)**i.e. p2**_{k+1}=p2_{k}+2r_{y}^{2}x_{k+1}-2r_{x}^{2}y_{k+1}+r_{x}^{2} - Now determine the symmetric points in another three quadrants.
- Plot the coordinate value as:
**x=x+x**_{c}, y=y+y_{c} - Repeat the steps for region 1 until
**2r**._{y}^{2}x>=2r_{x}^{2}y

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