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

Question

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.

Alabama

Answer 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

Avellaneda

Thanks. That works, except you have a typo in equation two. The minus sign should be a plus. – Alabama

Fixed, seems I followed through for the solution for tan(t) on [2] also, so I fixed that too. Hopefully you spotted all my errors - it's all scribbled on the back of an envelope here .. ;) – Avellaneda

I think there's another error, in the example: the first t value for x is -0.4636, shouldn't the second be -3.6052 (equals -0.4636 - pi)? – Eudora

@sh1ftst0rm You are correct. Bizarre mistake, since I wrote down the right result. The calculation as written gives -0.9487, which is pretty wrong. Will correct. – Avellaneda

One thing isn't quite clear to me about this answer: why are we only interested in t = -0.4636 and t = -3.6052? I see that these results come from substituting 0 and -1 for the variable 'n' in the equation t = -0.4636 + n*PI, but don't know the significance of those particular values. Is it because the other t-values will yield duplicate Cartesian coordinates when plugged in to our original equations? – Humberto

@Caleb: Exactly correct. There are only two unique solutions that will fit in a single whole 2*PI rotation (since we have the ...+n*PI term). By choosing any 2 consecutive values of t, we ensure that both of the unique answers will result from plugging those values for t into the equations. You can confirm this by trying other values for t. – Avellaneda

Obviously, your solution doesn't work for phi=90° and phi=270° – Inexcusable

Why not? Can you explain? It seems to work in the example I tried. – Avellaneda

Can you please explain what parameter t is for? And why we are finding extrema points? – Verisimilitude

Here is python implementation gist.github.com/smidm/b398312a13f60c24449a2c7533877dc0. – Nugent

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

Vibraharp

JavaScript implementation gist.github.com/kolosovsky/b56d90ad3a507876ae2da96e5bb8ff71 – Pangenesis

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

Prolix

There is a typo in your code in the thrid line. I the second = should be a *. I think this is obvious for everybody. I can't edit it because edits have to have at least 6 characters and this is only one character to edit. – Leporide

Answer 4

Brilian Johan Nilsson. I have transcribed your code to c# - ellipseAngle are now in degrees:

private static RectangleF EllipseBoundingBox(int ellipseCenterX, int ellipseCenterY, int ellipseRadiusX, int ellipseRadiusY, double ellipseAngle)
{
    double angle = ellipseAngle * Math.PI / 180;
    double a = ellipseRadiusX * Math.Cos(angle);
    double b = ellipseRadiusY * Math.Sin(angle);
    double c = ellipseRadiusX * Math.Sin(angle);
    double d = ellipseRadiusY * Math.Cos(angle);
    double width = Math.Sqrt(Math.Pow(a, 2) + Math.Pow(b, 2)) * 2;
    double height = Math.Sqrt(Math.Pow(c, 2) + Math.Pow(d, 2)) * 2;
    var x= ellipseCenterX - width * 0.5;
    var y= ellipseCenterY + height * 0.5;
    return new Rectangle((int)x, (int)y, (int)width, (int)height);
}

Danutadanya

I believe that should be ellipseCenterY - height * 0.5 (minus, not plus). Otherwise works flawlessly. – Disfranchise

Answer 5

I think the most useful formula is this one. An ellipsis rotated from an angle phi from the origin has as equation:

where (h,k) is the center, a and b the size of the major and minor axis and t varies from -pi to pi.

From that, you should be able to derive for which t dx/dt or dy/dt goes to 0.

Perdomo

I feel so slow now, took me ages to write my answer up T.T – Avellaneda

Answer 6

Here is the formula for the case if the ellipse is given by its foci and eccentricity (for the case where it is given by axis lengths, center and angle, see e. g. the answer by user1789690).

Namely, if the foci are (x0, y0) and (x1, y1) and the eccentricity is e, then

bbox_halfwidth  = sqrt(k2*dx2 + (k2-1)*dy2)/2
bbox_halfheight = sqrt((k2-1)*dx2 + k2*dy2)/2

where

dx = x1-x0
dy = y1-y0
dx2 = dx*dx
dy2 = dy*dy
k2 = 1.0/(e*e)

I derived the formulas from the answer by user1789690 and Johan Nilsson.

Halftrack

Answer 7

If you work with OpenCV/C++ and use cv::fitEllipse(..) function, you may need bounding rect of ellipse. Here I made a solution using Mike's answer:

// tau = 2 * pi, see tau manifest
const double TAU = 2 * std::acos(-1);

cv::Rect calcEllipseBoundingBox(const cv::RotatedRect &anEllipse)
{
    if (std::fmod(std::abs(anEllipse.angle), 90.0) <= 0.01) {
        return anEllipse.boundingRect();
    }

    double phi   = anEllipse.angle * TAU / 360;
    double major = anEllipse.size.width  / 2.0;
    double minor = anEllipse.size.height / 2.0;

    if (minor > major) {
        std::swap(minor, major);
        phi += TAU / 4;
    }

    double cosPhi = std::cos(phi), sinPhi = std::sin(phi);
    double tanPhi = sinPhi / cosPhi;

    double tx = std::atan(-minor * tanPhi / major);
    cv::Vec2d eqx{ major * cosPhi, - minor * sinPhi };
    double x1 = eqx.dot({ std::cos(tx),           std::sin(tx)           });
    double x2 = eqx.dot({ std::cos(tx + TAU / 2), std::sin(tx + TAU / 2) });

    double ty = std::atan(minor / (major * tanPhi));
    cv::Vec2d eqy{ major * sinPhi, minor * cosPhi };
    double y1 = eqy.dot({ std::cos(ty),           std::sin(ty)           });
    double y2 = eqy.dot({ std::cos(ty + TAU / 2), std::sin(ty + TAU / 2) });

    cv::Rect_<float> bb{
        cv::Point2f(std::min(x1, x2), std::min(y1, y2)),
        cv::Point2f(std::max(x1, x2), std::max(y1, y2))
    };

    return bb + anEllipse.center;
}

Inexcusable

Answer 8

Here's a typescript function based on the above answers.

export function getRotatedEllipseBounds(
  x: number,
  y: number,
  rx: number,
  ry: number,
  rotation: number
) {
  const c = Math.cos(rotation)
  const s = Math.sin(rotation)
  const w = Math.hypot(rx * c, ry * s)
  const h = Math.hypot(rx * s, ry * c)

  return {
    minX: x + rx - w,
    minY: y + ry - h,
    maxX: x + rx + w,
    maxY: y + ry + h,
    width: w * 2,
    height: h * 2,
  }
}

Blocky

Answer 9

Here is another version of Pranay Soni's code, implemented in js codepen I hope someone will find it useful

/**
* @param {Number} rotation
* @param {Number} majorAxis
* @param {Nmber} minorAxis
* @pivot {Point} pivot {x: number, y: number}
* @returns {Object}
*/
export function getElipseBoundingLines(ratation, majorAxis, minorAxis, pivot) {
   const {cos, sin, tan, atan, round, min, max, PI} = Math;

   let phi = rotation / 180 * PI;

   if(phi === 0) phi = 0.00001;
   // major axis
   let a = majorAxis;
   //minor axis
   let b = minorAxis;

   const getX = (pivot, phi, t)  => {
      return round(pivot.x + a * cos(t) * cos(phi) - b * sin(t) * sin(phi))
   }
   const getY = (pivot, phi, t)  => {
      return round(pivot.y + b * sin(t) * cos(phi) + a * cos(t) * sin(phi))
   }

   const X = [], Y = [];

   let t = atan(-b * tan(phi) / a);
   X.push(getX(pivot, phi, t));
   Y.push(getY(pivot, phi, t));

   t = atan(b * (1 / tan(phi) / a));
   X.push(getX(pivot, phi, t));
   Y.push(getY(pivot, phi, t));

   phi += PI;

   t = atan(-b * tan(phi) / a);
   X.push(getX(pivot, phi, t));
   Y.push(getY(pivot, phi, t));

   t = atan(b * (1 / tan(phi)) / a);
   X.push(getX(pivot, phi, t));
   Y.push(getY(pivot, phi, t));

   const left    = min(...X);
   const right   = max(...X);
   const top     = min(...Y);
   const bottom  = max(...Y);

   return {left, top, right, bottom};
}

Incoordinate

Answer 10

The general method is to find the zeroes of the derivative of the parametric form of the ellipse along X and Y axes. The position of those zeroes give the edge points along vertical and horizontal directions (derivative is zero).

// compute point on ellipse from angle around ellipse (theta)
function arc(theta, cx, cy, rx, ry, alpha)
{
    // theta is angle in radians around arc
    // alpha is angle of rotation of ellipse in radians
    var cos = Math.cos(alpha), sin = Math.sin(alpha),
      x = rx*Math.cos(theta), y = ry*Math.sin(theta);
    return {
        x: cx + cos*x - sin*y,
        y: cy + sin*x + cos*y
    };
}

function bb_ellipse(cx, cy, rx, ry, alpha)
{
    var tan = Math.tan(alpha),
        p1, p2, p3, p4, theta,
        xmin, ymin, xmax, ymax
    ;
    // find min/max from zeroes of directional derivative along x and y
    // along x axis
    theta = Math.atan2(-ry*tan, rx);
    // get point for this theta
    p1 = arc(theta, cx, cy, rx, ry, alpha);
    // get anti-symmetric point
    p2 = arc(theta + Math.PI, cx, cy, rx, ry, alpha);
    // along y axis
    theta = Math.atan2(ry, rx*tan);
    // get point for this theta
    p3 = arc(theta, cx, cy, rx, ry, alpha);
    // get anti-symmetric point
    p4 = arc(theta + Math.PI, cx, cy, rx, ry, alpha);
    // compute min/max values
    ymin = Math.min(p3.y, p4.y)
    xmin = Math.min(p1.x, p2.x);
    ymax = Math.max(p3.y, p4.y);
    xmax = Math.max(p1.x, p2.x);
    // return bounding box vertices
    return [
    {x: xmin, y: ymin},
    {x: xmax, y: ymin},
    {x: xmax, y: ymax},
    {x: xmin, y: ymax}
    ];
}
var cx = 120, cy = 120, rx = 100, ry = 40, alpha = -45;
function ellipse(cx, cy, rx, ry, alpha)
{
   // create an ellipse
   const ellipse = document.createElementNS('http://www.w3.org/2000/svg', 'ellipse');
   ellipse.setAttribute('stroke', 'black');
   ellipse.setAttribute('fill', 'none');
   ellipse.setAttribute('cx', cx);
   ellipse.setAttribute('cy', cy);
   ellipse.setAttribute('rx', rx);
   ellipse.setAttribute('ry', ry);
   ellipse.setAttribute('transform', 'rotate('+alpha+' '+cx+' '+cy+')');
   document.getElementById('svg').appendChild(ellipse);
   
   // create the bounding box
   const bb = bb_ellipse(cx, cy, rx, ry, /*angle in radians*/ alpha*Math.PI/180);
   const polygon = document.createElementNS('http://www.w3.org/2000/svg', 'polygon');
   polygon.setAttribute('stroke', 'red');
   polygon.setAttribute('fill', 'none');
   polygon.setAttribute('points', bb.map(p => String(p.x) + ' ' + String(p.y)).join(' '));
   document.getElementById('svg').appendChild(polygon);
}

ellipse(cx, cy, rx, ry, alpha);

<svg xmlns="http://www.w3.org/2000/svg" id="svg" style="position:relative;width:240px;height:240px" viewBox="0 0 240 240"></svg>

You may be interested in my computational geometry library Geometrize (in JavaScript) which constructs and renders many 2D curves and shapes, along with bounding boxes, convex hulls and intersection points.

Hedger

Answer 11

This code is based on the code user1789690 contributed above, but implemented in Delphi. I have tested this and as far as I can tell it works perfectly. I spent an entire day searching for an algorithm or some code, tested some that didn't work, and I was very happy to finally find the code above. I hope someone finds this useful. This code will calculate the bounding box of a rotated ellipse. The bounding box is axis aligned and NOT rotated with the ellipse. The radiuses are for the ellipse before it was rotated.

type

  TSingleRect = record
    X:      Single;
    Y:      Single;
    Width:  Single;
    Height: Single;
  end;

function GetBoundingBoxForRotatedEllipse(EllipseCenterX, EllipseCenterY, EllipseRadiusX,  EllipseRadiusY, EllipseAngle: Single): TSingleRect;
var
  a: Single;
  b: Single;
  c: Single;
  d: Single;
begin
  a := EllipseRadiusX * Cos(EllipseAngle);
  b := EllipseRadiusY * Sin(EllipseAngle);
  c := EllipseRadiusX * Sin(EllipseAngle);
  d := EllipseRadiusY * Cos(EllipseAngle);
  Result.Width  := Hypot(a, b) * 2;
  Result.Height := Hypot(c, d) * 2;
  Result.X      := EllipseCenterX - Result.Width * 0.5;
  Result.Y      := EllipseCenterY - Result.Height * 0.5;
end;

Tryck

Answer 12

This is my function for finding tight fit rectangle to ellipse with arbitrary orientation

I have opencv rect and point for implementation:

cg - center of the ellipse

size - major, minor axis of ellipse

angle - orientation of ellipse

cv::Rect ellipse_bounding_box(const cv::Point2f &cg, const cv::Size2f &size, const float angle) {

    float a = size.width / 2;
    float b = size.height / 2;
    cv::Point pts[4];

    float phi = angle * (CV_PI / 180);
    float tan_angle = tan(phi);
    float t = atan((-b*tan_angle) / a);
    float x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi);
    float y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi);
    pts[0] = cv::Point(cvRound(x), cvRound(y));

    t = atan((b*(1 / tan(phi))) / a);
    x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi);
    y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi);
    pts[1] = cv::Point(cvRound(x), cvRound(y));

    phi += CV_PI;
    tan_angle = tan(phi);
    t = atan((-b*tan_angle) / a);
    x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi);
    y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi);
    pts[2] = cv::Point(cvRound(x), cvRound(y));

    t = atan((b*(1 / tan(phi))) / a);
    x = cg.x + a*cos(t)*cos(phi) - b*sin(t)*sin(phi);
    y = cg.y + b*sin(t)*cos(phi) + a*cos(t)*sin(phi);
    pts[3] = cv::Point(cvRound(x), cvRound(y));

    long left = 0xfffffff, top = 0xfffffff, right = 0, bottom = 0;
    for (int i = 0; i < 4; i++) {
        left = left < pts[i].x ? left : pts[i].x;
        top = top < pts[i].y ? top : pts[i].y;
        right = right > pts[i].x ? right : pts[i].x;
        bottom = bottom > pts[i].y ? bottom : pts[i].y;
    }
    cv::Rect fit_rect(left, top, (right - left) + 1, (bottom - top) + 1);
    return fit_rect;
}

Favors

Answer 13

Here's a simple example of bounding box around rotated ellipse in javascript: https://jsfiddle.net/rkn61mjL/1/

The idea is pretty simple and doesn't require complex calculations and solving gradients:

1. calculate a simple bounding box of non-rotated ellipse:

   let p1 = [centerX - radiusX, centerY - radiusY];
   let p2 = [centerX + radiusX, centerY - radiusY];
   let p3 = [centerX + radiusX, centerY + radiusY];
   let p4 = [centerX - radiusX, centerY + radiusY];
   

2. rotate all of the four points around the center of the ellipse:

   p1 = [(p1[0]-centerX) * Math.cos(radians) - (p1[1]-centerY) *  Math.sin(radians) + centerX,
       (p1[0]-centerX) * Math.sin(radians) + (p1[1]-centerY) * Math.cos(radians) + centerY];        
   p2 = [(p2[0]-centerX) * Math.cos(radians) - (p2[1]-centerY) *  Math.sin(radians) + centerX,
       (p2[0]-centerX) * Math.sin(radians) + (p2[1]-centerY) * Math.cos(radians) + centerY];        
   p3 = [(p3[0]-centerX) * Math.cos(radians) - (p3[1]-centerY) *  Math.sin(radians) + centerX,
       (p3[0]-centerX) * Math.sin(radians) + (p3[1]-centerY) * Math.cos(radians) + centerY];        
   p4 = [(p4[0]-centerX) * Math.cos(radians) - (p4[1]-centerY) *  Math.sin(radians) + centerX,
       (p4[0]-centerX) * Math.sin(radians) + (p4[1]-centerY) * Math.cos(radians) + centerY];
   

Phototube