Scan Conversion of an Ellipse Computer Graphics

Facebooktwitterredditpinterestlinkedinmailby feather

Scan Conversion of an Ellipse: An ellipse can be defined as a closed plane curve, which is a collection of points. It is the cause of the intersection of a plane over a cone. The ellipse is a symmetric shape figure. It is similar to a circle, but it contains four-way symmetry. We can also define an ellipse as a closed curve created by the points moving in such an order that the total of its distance from two points is constant. These two points are also called “foci.” 

Properties of Ellipse

  • The circle and ellipse are examples of the conic section.
  • We can create an ellipse by performing stretching on a circle in x and y-direction.  
  • Every ellipse has two focal points, called “foci.” In the standard form, we can write the ellipse equation as follow-

                     (x – h)2/ a2 + (y – h)2/ b2 = 1

        (h, k) are the center coordinates of the circle.

There should be two axes of an ellipse.

  • Major axis
  • Minor axis

Major axis: The major axis is the longest width. For a horizontal ellipse, the major axis and x-axis are parallel to each other. 2a is the length of the major axis. The endpoints of the major axis are vertices with (h ±a, k).

Minor axis: The minor axis is the shortest width of it. For a horizontal ellipse, the minor axis is parallel to the y-axis. 2b is the length of the minor axis. The endpoints of the minor axis are vertices with (h, k ±a). 

There are following two methods to define an ellipse-

  • An ellipse with the polynomial method
  • An ellipse with the trigonometric method

An Ellipse with Polynomial method

When we use polynomial method to define an ellipse, we will use the following equation-

                               (x – h)2/ a2 + (y – k)2/ b2 = 1 

Here, (h, k) = The center points of ellipse

                 a = Length of the major axis

                 b = Length of the minor axis

We will use (p, q) for major and minor axes. Now the equation will be-

                             (x – h)2/ p2 + (y – k)2/ q2 = 1

In the polynomial method, the value of the x-axis is increased from the center point (h) to major axis length (p). We will find the value of y-axis by following formula/equation-

                     y = q √1- (x – h)2 + k / p2 

An Ellipse with Trigonometric method

When we use the trigonometric method to define an ellipse, we will use the following equation-

                       x = a cos (θ) +h 

                       y = b sin (θ) +h 

Here, (x, y) = The current coordinates

(h, k) = The center points of ellipse

                 p = Length of the major axis

                 q = Length of the minor axis

                 θ Current angle

Now, the equation will be-

                     x = p cos (θ) +h 

                     y = q sin (θ) +h           

In the trigonometric method, the value of the angle (θ) tends from 0 to π/2 radians. We will find the value of all points by symmetry.

Midpoint Ellipse Drawing Algorithm

We can understand ellipse as an elongated circle. In the midpoint ellipse drawing algorithm, we will determine the plotting point (p, q). Let us suppose that the center point of the ellipse is (0, 0).

Scan Conversion of an Ellipse Computer Graphics

The equation of ellipse = p2 / rp2 + q2 / rq2 = 1

We will simplify the equation as follows-

                                 p2 rq2 + q2 rp2 = rp2 rq2      

We can represent the ellipse by following equation-

                   f (p, q) = rq2 p2 + rp2 q2 – rp2 rq2 …………………………. (1)

Now, there are three following conditions-

If 

         f (p, q) < 0

then 

             (p, q) is inside the ellipse boundary.

 If 

         f (p, q) = 0

then 

             (p, q) is on the ellipse boundary.

 If 

         f (p, q) > 0

then 

             (p, q) is outside the ellipse boundary.

Now,we partially differentiate the equation (1), and we get-

dp /dq = -2rq2p / 2rp2q  

2rq2p >= 2rp2q                                      {when we switch from region 1 to region 2}

Now, we will calculate the decision parameter (dk1) for region 1

dk1 = (pk+1, qk – 1/2)

Now, we put the value in equation (1)

f (p, q) = rq2 (pk+1)2 + rp2 (qk – 1/2)2 – rp2 rq2 ………………………… (2)

Now, we calculate the next decision parameter (dk1+1) 

dk1+1 = (pk+1+1, qk+1 – 1/2)

Now, we put the value of dk1+1 in equation (2) 

 dk1+1 = rq2 ((pk+1) +1)2 + rp2 (qk+1 – 1/2)2 – rp2 rq2

We simplify the equation (2) by {(A+B)2} and {(A-B)2 }

dk1+1 = rq2 [(pk+1)2 +12+2 (pk+1)]2 + rp2 [(qk+1)2 +1/4 –2(1/2) qk+1] – rp2 rq2 

Now, we find the difference between dk1+1 and dk1

dk1+1 – dk1= rq2 [(pk+1)2+12+2(pk+1)]2+rp2 [(qk+1)2+1/4–qk+1]–rp2rq2  rq2((pk+1) +1)2 + rp2 (qk+1 – 1/2)2 – rp2 rq2

 dk1+1 = dk1+rq2 + 2 rq2(pk+1) +rp2 [(qk-1/2)- (qk-1/2)2] ……………. (3)

If 

      Decision parameter (dk1) < 0

Then

        dk1+1 dk1 + rq2 + 2 rq2 (pk+1)    

If 

      Decision parameter (dk1) > 0

Then

        dk1+1 dk1 + rq2 + 2 rq2 (pk+1) – 2 rp2 k+1

 Now, we calculate the initial decision parameter dk1(0)   

dk1(0) rq2 + ¼ rp2 – rp2rq             {For region 1}

Thus, we calculate the decision parameter (dk2) for region 2

dk2 = (pk+1/2, qk – 1)

Now, we put the value of dkin equation (1)

 dkrq2 (pk +1/2)2 + rp2 (qk -1)2 – rp2 rq2 

Now, we calculate the next decision parameter (dk2+1)

(dk2+1) = (pk+1 +1/2, qk+1 – 1)

Now, we put the value of dk2+2 in previous equation 

 dk2+1 = rq2 ((pk+1) +1/2)2 + rp2 (qk-1) – 1)2 – rp2 rq2

 We simplify the equation and calculate the difference between dk2+1 and dk2. We get- 

dk2+1 = dk2-2rp2 (qk -1) +rp2 +rq2 2 [(pk+1+1/2)2– (pk+1/2)2] ……………… (4)

Now, we check two conditions-

If 

      Decision parameter (dk2) < 0

Then

        dk2+1 dk2 -2 rp2qk+1 + rp2     

If 

      Decision parameter (dk2) > 0

Then

        dk2+1 dk2 +2rq2 pk+1 2 rp2 qk+1 +rp2 

Now, we calculate the initial decision parameter dk2(0)

dk1(0) rq2(pk +1/2)2 + rp2(qk 1) – rp2rq           {For region 2}

Algorithm of Midpoint Ellipse Drawing    

Step 1: First, we read rp and rq.

Step 2: Now we initialize starting coordinates as follow-

              p = 0 and q =rq

Step 3: Wecalculate the initial value and decision parameter for region 1 as follow-

                dkr2– r2p r2q + ¼ r2p

Step 4: Now, we initialize dp and dq as follows-

     dp = 2r2qp

    dq = 2r2pq

Step: 5 Now, we apply Do-while loop

 Do

{plot (p, q)

If (dk1 < 0)

     (p= p+1 and q = q)

dp = dp + 2r2q

dk1 = dk dp r2q

[dk1 = dk1 + 2r2qp +2r2q + r2q]

Else

              (p= p+1 and q = q -1)

dp = dp + 2r2q

dq = dq  2r2p

dk1 = dk+ dp – dp + r2q

         [dk1 = dk1 + 2r2qp +2r2q – (2r2pq – 2r2p) + r2q]

while (dp < dq)

Step 6: Now,wecalculate the initial value and decision parameter for region 2 as follow-

dk2 = r2q (p + 1/2)2 + r2p (q-1)2 – r2p r2q

Step 7: Now, we again apply Do-while loop

Do

{plot (p, q)

If (dk2 < 0)

     (p= p and q = q – 1)

dq = dp – 2r2p

dk2 = dk dq r2p

[dk2 = dk2 – (2r2pq – 2r2p) + r2p]

Else

              (p= p+1 and q = q -1)

   dq = dq – 2r2p

   dp = dp + 2r2q

dk2 = dk+ dp – dq + r2p

         [dk2 = dk2 + 2r2qp +2r2q – (2r2pq – 2r2p) + r2q]

while (q < 0)

Step 8: Thus, we calculate all the points of other quadrants.

Step 9: Stop.

Facebooktwitterredditpinterestlinkedinmailby feather