Back to October Calendar            ←Previous Entry                             Next Entry→

October 24, 2005

Ellipse Pixels Algorithms

My goal today is to generalize the circle algorithm of the last few days to drawing ellipses. My subgoal is to just ignore all this WebEQ/MathML/MathPlayer crap.  It’s just worn me down to where I just can’t stand it that it still doesn’t work.

 

A geometric definition of an ellipse is:

 

the set of all points the sum of whose distances from two fixed points is a constant.” 

That is,

                                                             

 

Assuming the foci are at (x1,y1) and (x2,y2) the rectangular form of this equation is

                              

By equating squares, isolating the radical and again equating squares, you’ll arrive at and equation equivalent to the basic conic form

                                                

where the parameters A, B, C, D, E and F depend on where the ellipse is centered and the lengths of its major and minor axes.

 

For an ellipse centered at (h,k) with , the standard rectangular form is often written as

                                                         

or in polar coordinates,

                                                                

An ellipse has somewhat less symmetry than a circle, so we may need to do more computations to find its pixel coordinates.  To avoid computations where the slope (rate of change of one variable with respect to change in the other) is too large, we’ll split the first quadrant into a region where  and a region where . 

 

The analogous decision function will involve

                                                     

which has the nice property that

                            

As with the circle algorithm, we can start at the top point (0,b) and take unit steps in the x direction until we reach the point where the slope is -1 where we switch to unit steps in the (negative) y direction.   At each step we compute the slope of the tangent line:

                                                           

At the point where dy/dx = −1, b2x = a2y. and we can use the sign of   a2y − b2x to determine where to switch from delta x to delta y zones. 

 

Starting at (0,b), the midpoint algorithm, as applied to the ellipse, entails evaluating the decision parameter

         

 

  

Again, the decision parameter is negative if only if the midpoint between adjacent candidate pixels is inside the ellipse boundary, as shown in the picture at right, where you see the midpoints in red and the resulting pixel array.  As before, the coordinates of the next pixel to color will be either

      (xk+1, yk) or (xk+1, yk−1)

depending on whether the decision parameter is negative or not.

 

Following the process for the circle midpoint algorithm of yesterday, we seek a recurrence relation for the decision parameter:

      

Grouping the terms of pxk and observing that, in the second case,       

           

So that we again a nice tidy recurrence relation:

                                    

and since the values of 2b2xk+1 and 2a2yk+1 can easily be obtained by recursion, the formula requires only addition and subtraction!  Initially, at (0,b), these terms are

                                                                 

and then updated by adding 2b2 to the x term and subtracting 2a2 from the y term:

 

Updated increments are computed until we reach the point where b2x>a2y (the tangent line has slope of -1) and then we switch to other region. 

 

In the first region we have the initial decision parameter value

                            

In the second region, we switch from steadily incrementing x by 1 to steadily decrementing y by 1.  Thus the decision parameter is the f function evaluated at the midpoint of the boundary between the pixel directly below the current pixel and the the pixel immediately to its right:

                                             

If pyk > 0 then the midpoint sample is outside the boundary so we don’t move over, only down. Otherwise, we increase the x coordinate by 1. 

 

where yk+1 = yk−1. and xk+1 = xk+ .

 

Hearn and Baker observe that you can express this function this way

                            

The last position from crossing the border into the second region can then be the first position for walking through the second region, and for simplicity we can rename it so that

                                             

 

If you start at (a,0) rather than at (0,b) and then move counterclockwise.  In this case you’ll increment y coordinates steadily until entering the other region, where you’ll steadily decrement x values.  Or you can mix to start on the axis and move towards the interior of the first quadrant.

 

You can adapt this midpoint algorithm to plot ellipses with rotated axes by using   to work the test parameter for the entire perimeter, or you could plot it without rotation and then rotate it using some efficient rotation routine or other.

 

So here’s pseudo code for an ellipse midpoint algorithm:

 

  1. Get parameters a, b, h, k for center coordinate h and k and major&minor axis lengths 2a and 2b.
  2. Calculate the initial decision parameter value in the first region: .
  3. Use the formulas above to iterate pxk+1 until b2x>a2y.

  4. Rename the current (xk,yk) as (x0,y0) and calculate the initial decision parameter value in the 2nd region: .
  5. Use the formulas above to iterate pyk+1 until y <= 0.

  6. For both regions plot the other three symmetry points.

 

  1. Shift to center at h, k.

 

Tomorrow maybe investigate implementating.