From: dseal@armltd.co.uk (David Seal)
Newsgroups: comp.programming
Subject: Re: Ellipses?
Date: 16 Oct 92 12:34:12 GMT
Distribution: comp
Organization: A.R.M. Ltd, Swaffham Bulbeck, Cambs, UK

In article <1992Oct15.144816.9814@geovision.gvc.com> pt@geovision.gvc.com
(Paul Tomblin) writes:

>I need an algorithm for generating points along an ellipse.  I assume I
>would have to specify three input points (centre, semi-major axis end,
>and another?)  These ellipses cannot be contrainted to have the semi-major
>axis along the x-axis.
>
>Thanks...
>-- 
>Paul Tomblin, pt@geovision.gvc.com
>(This is not an official opinion of GeoVision Systems Inc.)
>"I don't have time to think it through: I've got to get this code written!"

The main problem with specifying non-axis-aligned ellipses in terms of
points is that they have 5 degrees of freedom. You can specify them in many
different ways - e.g.:

  (A) Centre X co-ordinate;
      Centre Y co-ordinate;
      Length of semi-major axis;
      Length of semi-minor axis;
      Angle of semi-major axis.

  (B) First focus X co-ordinate;
      First focus Y co-ordinate;
      Second focus X co-ordinate;
      Second focus Y co-ordinate;
      The sum of the distances of an arbitrary point on the boundary from
        the two foci.

  (C) Centre X co-ordinate;
      Centre Y co-ordinate;
      X co-ordinate at which the ellipse crosses the horizontal line through
        the centre;
      Maximum Y co-ordinate of a point on its boundary (i.e. Y co-ordinate
        of the "highest" point on the ellipse);
      X co-ordinate at which this maximum Y co-ordinate is achieved (i.e. X
        co-ordinate of the "highest" point).

When you specify a curve in terms of points, you always get an even number
of degrees of freedom. When an odd number are needed (as in this case), you
need to throw one away in some way. The classic example of this is the
circle, which has three degrees of freedom (centre X, centre Y and radius).
It is normally specified by 2 points, namely the centre and a point on its
boundary: we throw away the surplus degree of freedom by ignoring the full
position of the boundary point and only paying attention to how far it lies
from the centre.

The corresponding technique for ellipses is to use (B) above: you specify
the two foci and a point on the boundary of the ellipse. The surplus degree
of freedom is thrown away by ignoring the full position of the boundary
point and only paying attention to the sum of its distances from the two
foci.

Unfortunately, specifying an ellipse this way has some unpleasant
properties. One is that I don't know of any good low-level algorithm to plot
the ellipse directly from these three points. Another one is that it has
some numerical problems for long thin ellipses: small errors in the
positions of the three points can lead to comparatively large errors in the
ellipse that is actually plotted in some circumstances.

Method (A) above is obviously the easiest for the programmer to think in
terms of. However, as you've discovered, once you've specified the centre
and the end of the semi-major axis, it's not too clear how to throw away the
"spare" degree of freedom from the third point so that you just get the
length of the semi-minor axis. Probably the best technique would be to make
the length of the semi-minor axis be the distance of the third point from
the centre: if the third point actually is the end of the semi-minor axis,
the expected results will be obtained, and small errors in the calculation
of the semi-minor axis end won't lead to major changes in the ellipse
plotted. However, I still don't know of a low-level routine that will plot
the ellipse directly from these three points.

Method (C) above may seem somewhat strange. The reason I mention it is that
I *do* know of a reasonable low-level algorithm to plot the ellipse based on
them. The idea is as follows:

We're given three points (Xcentre,Ycentre), (Xhoriz,Yhoriz) and (Xtop,Ytop),
which are supposed to be the centre, the intercept of the horizontal line
through the centre with the ellipse and the "highest" point of the ellipse
respectively. Obviously, Yhoriz is supposed to be equal to Ycentre: rather
than checking this, we will simply ignore the specified value of Yhoriz and
assume that it is equal to Ycentre (this is where we lose the degree of
freedom).

So what we've got is something like the following:

                                               (Xtop,Ytop)
                                  ______------*-----____
                           ___----         _-           --_
                      __---              _-                -
                  __--                 _-                   |
              __--                   _-                     |
           __-                     _-                      |
         _-                      _-                      _-
  -----_-----------------------_*----------------------_*------------------
      -                      _-  (Xcentre,Ycentre)  __-  (Xhoriz,Ycentre)
     |                     _-                    __-
    |                    _-                  __--
    |                  _-                __--
     -_              _-            ___---
       --____      _-    ______----
             ------------

The crucial point is that if we shear this ellipse to make the line drawn
above connecting (Xcentre,Ycentre) to (Xtop,Ytop) vertical, we will get an
axis-aligned ellipse with centre (Xcentre,Ycentre), end of X-axis at
(Xhoriz,Ycentre) and end of Y-axis at (Xcentre,Ytop):

                                 (Xcentre,Ytop)
                      _____-----*-----_____
                 __---          |          ---__
             __--               |               --__
           _-                   |                   -_
          -                     |                     -
         |                      |                      |
        |                       |                       |
  ------|-----------------------*-----------------------*------------------
        |                       |(Xcentre,Ycentre)      |(Xhoriz,Ycentre)
         |                      |                      |
          -_                    |                    _-
            -__                 |                 __-
               --__             |             __--
                   ---_____     |     _____---
                           -----------

Bresenham's algorithm for drawing circles can easily be adapted to drawing
this axis-aligned ellipse, and Bresenham's algorithm for line-drawing can be
used to track the (Xcentre,Ycentre) to (Xtop,Ytop) line. The idea is now to
combine these two to find the points of the original ellipse, by "undoing"
the shear we did above.

So for any particular Y value, we can use the first algorithm to find out
what the two points of the axis-aligned ellipse are for that Y value - they
will be (Xcentre+Xwidth,Y) and (Xcentre-Xwidth,Y) for some value of Xwidth.
The second algorithm will tell us where the (Xcentre,Ycentre) to (Xtop,Ytop)
line intersects that Y value - it will be at a point (Xcentre+Xdisp,Y) for
some value of Xdisp. Undoing the shear then tells us that the two points of
the original ellipse for that Y value are (Xcentre+Xdisp+Xwidth,Y) and
(Xcentre+Xdisp-Xwidth,Y).

Probably the best solution overall if you want to use this technique is to
write a high-level ellipse routine which takes the ellipse specification in
a form suitable for the programmer - e.g. (A) above. It then transforms this
into form (C) - the mathematics isn't especially difficult - and calls a
low-level ellipse routine written to use that form.

I've left a lot of details out of the above - e.g. that to reduce the size
of the errors that occur, it's a good idea to run both of the Bresenham's
algorithms to rather higher than pixel accuracy in the X-direction, then
round to pixel boundaries after doing the (Xcentre+Xdisp+Xwidth) and
(Xcentre+Xdisp-Xwidth) calculations. It's also a good idea to look at Y in
half-scanline increments and combine the results suitably to decide which
pixels you will plot - otherwise long thin ellipses that are nearly parallel
to the X-axis can look strange.

I should also say that this is a somewhat rough-and-ready solution - for
instance, it isn't easy to make it obey any good mathematical rules about
which pixels are plotted (e.g. "pixels whose centres lie inside the
mathematical ellipse are plotted, and those that don't are not"). But it is
reasonably accurate and reasonably fast: even an 8-bit processor can perform
it at an acceptable speed.

David Seal
dseal@armltd.co.uk

All opinions are mine only...