Home » Computer Graphics

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₁ and d₂ then the general equation of the ellipse can be stated as- d₁+d₂=constant.

For expressing the distances d₁ and d₂ in terms of focal coordinates F₁ and F₂ we have:- Ax²+By²+Cxy+Dx+Ey+F=0 where 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²x²+r_x²y²-r_x²r_y²

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

1. f_ellipse(x,y)<0 which means (x,y) is inside the ellipse boundary.
2. f_ellipse(x,y)>0 which means (x,y) is outside the ellipse boundary.
3. f_ellipse(x,y)=0 which means (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₀=r_y²+1/4r_x²-r_x²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₀=r_y²(x₀+1/2)²+r_x²(y₀-1)²-r_x²r_y²

ALGORITHM

1. Take the input and ellipse centre and obtain the first point on an ellipse centered on the origin as a (x,y₀)= (0,r_y).
2. Now calculate the initial decision parameter in region 1 as:
   p1₀=r_y²+1/4r_x²-r_x²r_y
3. At each x_k position in region 1 perform the following task. If p1_k<0 then the next point along the ellipse centered on (0,0) is (x_k+1,y_k).
   i.e. p1_k+1=p1_k+²r_y²x_k+1+r_y²
   Otherwise the next point along the circle is (x_k+1,y_k -1)
   i.e. p1_k+1=p1_k+2r_y²x_k+1 – 2r_x²y_k+1+r_y²
4. Now, again calculate the initial value in region 2 using the last point (x₀,y₀) calculated in a region 1 as : p2₀=r_y²(x₀+1/2)²+r_x²(y₀-1)²-r_x²r_y²
5. At each y_k position in region 2 starting at k =0 perform the following task. If p2_k<0 the next point along the ellipse centered on (0,0) is (x_k , y_k-1)
   i.e. p2_k+1=p2_k-2r_x²y_k+1+r_x²
   Otherwise the next point along the circle will be (x_k+1,y_k -1)
   i.e. p2_k+1 =p2_k+2r_y²x_k+1 -2r_x²y_k+1+r_x²
6. Now determine the symmetric points in another three quadrants.
7. Plot the coordinate value as: x=x+x_c , y=y+y_c
8. Repeat the steps for region 1 until 2r_y²x>=2r_x²y.