Calculating the Bounding Rectangle at an Angle of a Polygon

Question

I have the need to determine the bounding rectangle for a polygon at an arbitrary angle. This picture illustrates what I need to do:

alt text http://kevlar.net/RotatedBoundingRectangle.png

The pink rectangle is what I need to determine at various angles for simple 2d polygons.

Any solutions are much appreciated!

Edit:

Thanks for the answers, I got it working once I got the center points correct. You guys are awesome!

Answer 1

To get a bounding box with a certain angle, rotate the polygon the other way round by that angle. Then you can use the min/max x/y coordinates to get a simple bounding box and rotate that by the angle to get your final result.

From your comment it seems you have problems with getting the center point of the polygon. The center of a polygon should be the average of the coordinate sums of each point. So for points P1,...,PN, calculate:

xsum = p1.x + ... + pn.x;
ysum = p1.y + ... + pn.y;
xcenter = xsum / n;
ycenter = ysum / n;

To make this complete, I also add some formulas for the rotation involved. To rotate a point (x,y) around a center point (cx, cy), do the following:

// Translate center to (0,0)
xt = x - cx;
yt = y - cy;
// Rotate by angle alpha (make sure to convert alpha to radians if needed)
xr = xt * cos(alpha) - yt * sin(alpha);
yr = xt * sin(alpha) + yt * cos(alpha);
// Translate back to (cx, cy)
result.x = xr + cx;
result.y = yr + cx;

Answer 2

To get the smallest rectangle you should get the right angle. This can acomplished by an algorithm used in collision detection: oriented bounding boxes. The basic steps:

Get all vertices cordinates
Build a covariance matrix
Find the eigenvalues
Project all the vertices in the eigenvalue space
Find max and min in every eigenvalue space.

For more information just google OBB "colision detection"

Ps: If you just project all vertices and find maximum and minimum you're making AABB (axis aligned bounding box). Its easier and requires less computational effort, but doesn't guarantee the minimum box.