How do you calculate the axis-aligned bounding box of an ellipse?

If the major axis of the ellipse is vertical or horizontal, it's easy to calculate the bounding box, but what about when the ellipse is rotated?

The only way I can think of so far is to calculate all the points around the perimeter and find the max/min x and y values. It seems like there should be a simpler way.

If there's a function (in the mathematical sense) that describes an ellipse at an arbitrary angle, then I could use its derivative to find points where the slope is zero or undefined, but I can't seem to find one.

Edit: to clarify, I need the axis-aligned bounding box, i.e. it should not be rotated with the ellipse, but stay aligned with the x axis so transforming the bounding box won't work.

Solution 1:

You could try using the parametrized equations for an ellipse rotated at an arbitrary angle:

x = h + a*cos(t)*cos(phi) - b*sin(t)*sin(phi)  [1]
y = k + b*sin(t)*cos(phi) + a*cos(t)*sin(phi)  [2]

...where ellipse has centre (h,k) semimajor axis a and semiminor axis b, and is rotated through angle phi.

You can then differentiate and solve for gradient = 0:

0 = dx/dt = -a*sin(t)*cos(phi) - b*cos(t)*sin(phi)

=>

tan(t) = -b*tan(phi)/a   [3]

Which should give you many solutions for t (two of which you are interested in), plug that back into [1] to get your max and min x.

Repeat for [2]:

0 = dy/dt = b*cos(t)*cos(phi) - a*sin(t)*sin(phi)

=>

tan(t) = b*cot(phi)/a  [4]

Lets try an example:

Consider an ellipse at (0,0) with a=2, b=1, rotated by PI/4:

[1] =>

x = 2*cos(t)*cos(PI/4) - sin(t)*sin(PI/4)

[3] =>

tan(t) = -tan(PI/4)/2 = -1/2

=>

t = -0.4636 + n*PI

We are interested in t = -0.4636 and t = -3.6052

So we get:

x = 2*cos(-0.4636)*cos(PI/4) - sin(-0.4636)*sin(PI/4) = 1.5811

and

x = 2*cos(-3.6052)*cos(PI/4) - sin(-3.6052)*sin(PI/4) = -1.5811

Solution 2:

I found a simple formula at http://www.iquilezles.org/www/articles/ellipses/ellipses.htm (and ignored the z axis).

I implemented it roughly like this:

num ux = ellipse.r1 * cos(ellipse.phi);
num uy = ellipse.r1 * sin(ellipse.phi);
num vx = ellipse.r2 * cos(ellipse.phi+PI/2);
num vy = ellipse.r2 * sin(ellipse.phi+PI/2);

num bbox_halfwidth = sqrt(ux*ux + vx*vx);
num bbox_halfheight = sqrt(uy*uy + vy*vy); 

Point bbox_ul_corner = new Point(ellipse.center.x - bbox_halfwidth, 
                                 ellipse.center.y - bbox_halfheight);

Point bbox_br_corner = new Point(ellipse.center.x + bbox_halfwidth, 
                                 ellipse.center.y + bbox_halfheight);

Solution 3:

This is relative simple but a bit hard to explain since you haven't given us the way you represent your ellipse. There are so many ways to do it..

Anyway, the general principle goes like this: You can't calculate the axis aligned boundary box directly. You can however calculate the extrema of the ellipse in x and y as points in 2D space.

For this it's sufficient to take the equation x(t) = ellipse_equation(t) and y(t) = ellipse_equation(t). Get the first order derivate of it and solve it for it's root. Since we're dealing with ellipses that are based on trigonometry that's straight forward. You should end up with an equation that either gets the roots via atan, acos or asin.

Hint: To check your code try it with an unrotated ellipse: You should get roots at 0, Pi/2, Pi and 3*Pi/2.

Do that for each axis (x and y). You will get at most four roots (less if your ellipse is degenerated, e.g. one of the radii is zero). Evalulate the positions at the roots and you get all extreme points of the ellipse.

Now you're almost there. Getting the boundary box of the ellipse is as simple as scanning these four points for xmin, xmax, ymin and ymax.

Btw - if you have problems finding the equation of your ellipse: try to reduce it to the case that you have an axis aligned ellipse with a center, two radii and a rotation angle around the center.

If you do so the equations become:

  // the ellipse unrotated:
  temp_x(t) = radius.x * cos(t);
  temp_y(t) = radius.y * sin(t);

  // the ellipse with rotation applied:
  x(t) = temp_x(t) * cos(angle) - temp_y(t) * sin(angle) + center.x;
  y(t) = temp_x(t) * sin(angle) + temp_y(t) * cos(angle) + center.y;