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

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

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);