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

    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

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.





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.