Calculating the Bounding Rectangle at an Angle of a Polygon

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

I'm interpreting your question to mean "For a given 2D polygon, how do you calculate the position of a bounding rectangle for which the angle of orientation is predetermined?"

And I would do it by rotating the polygon against the angle of orientation, then use a simple search for its maximum and minimum points in the two cardinal directions using whatever search algorithm is appropriate for the structure the points of the polygon are stored in. (Simply put, you need to find the highest and lowest X values, and highest and lowest Y values.)

Then the minima and maxima define your rectangle.

You can do the same thing without rotating the polygon first, but your search for minimum and maximum points has to be more sophisticated.

Answer 3

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.

Answer 4

To get a rectangle with minimal area enclosing a polygon, you can use a rotating calipers algorithm.

The key insight is that (unlike in your sample image, so I assume you don't actually require minimal area?), any such minimal rectangle is collinear with at least one edge of (the convex hull of) the polygon.