First, let me preface by saying I've done a few searches both on here and on Google, and have not been able to find anything that suits my purposes, at least as far as I am aware. My maths have gotten a bit rusty over the years.

Now then, I would like to find the minimum bounding box/rectangle given a set of points on a 2-dimensional plane, one that is properly rotated to be the smallest. At the moment, the only thought process that has come to mind is to compute 180 different bounding boxes and find the one with the lowest area, but this seems to be the opposite of ideal.

Any help is greatly appreciated and please excuse if it is something obvious/simple/etc.

Thanks!

Looking for the minimal box with unconstrained rotation is a fairly hard problem. I don't know a solution off hand, but I can suggest a few potential avenues:

• Perform a linear regression of the points to determine a primary axis for the bounding box -- this isn't a minimal solution, but probably a reasonable approximation for relatively low cost. Once you have the axis, project the points into that frame of reference, compute the box as you would an AABB, then unproject the box back to the original space.
• Compute the convex hull of the set of points to reduce the number of points you need to consider. Once you have the hull, compute the minimal bounding box using an edge as one of the edges of the box, repeat for all edges, and choose the smallest box that results. To make calculating the boxes easier, for each box calculation project the hull into a frame of reference defined by the edge and compute as an AABB, store the edge index and area of the result somewhere, use the area to compare against other boxes, choose the winner, and only unproject the winner. This is most like your idea, but optimizes away degrees of rotation that aren't useful and also is truly minimal, choosing an arbitrary 180 rotations is not necessarily the absolute minimum (though the error is probably pretty small). Anyways, the hull-optimized version is almost certainly faster.
• If perfect or consistent results aren't required, consider early-outing if a potential match is below some threshold -- say by comparing the area of a potential bounding box to the area of the space enclosed by the convex hull using some heuristic, and just choosing it if it seems close enough for your purposes.

These techniques could be combined in various ways -- the second ought to give true minimum, but is costlier than the others.

I don't know the result would be optimal, but I would:

* Compute the principle axis of the data (google Principle Component Analysis)

* Align your box to be 45 degrees offset from this (so the principle component is describing your diagonal)

* Compute distance from the center along that axes for all points (actually, distance squared; only root the farthest one)

My first attempt to search the web for a solution of the problem lead me here: http://en.wikipedia.org/wiki/Minimum_bounding_box_algorithms