How to find an arbitrarily oriented minimum boundi

Question

So let's say I have a list of N pairs of positive long coordinates (points).
How do I find the smallest rectangle containing all of them?
The rectangle can also have floating coordinates and be rotated in any angle and further shrunk... Not just X, Y, Width and Height!

I already know how to find the smallest polygon or not rotated rectangle, but it's not what I need...I wish to know how to find the arbitrarily oriented minimum bounding box.

Answer 1

This wikipedia page notes that you can solve this problem by using the fact that the minimum rectangle must have an edge collinear with one of the edges of the convex hull.

Answer 2

See http://www.geometrictools.com/Source/ComputationalGeometry.html

The section "Minimum-area box" has various examples.

Answer 3

Maybe this paper can help: Smallest k point enclosing rectangle of arbitrary orientation

Answer 4

I don't know if this would be of help to you, but here's my thoughts on how I'd approach the problem.

You'll need functions to find your "corner-most" points (in your example, the left 2 and right 2 points). Given those 4 points, connect them with lines.

(Note in your example image, the top point would not be contained by the generated rectangle, so...) You'll then need a function to determine if the rectangle generated contains all given points; if not, extend the endpoints (in this case, the top 2 points of the generated rectangle) by N (which is either a single measure ... say a pixel, or if you're smart, the distance to the point that's out of bounds plus/minus one dependant on the direction) and re-evaluate.

Answer 5

Maybe this works for you:

• find the center point of all your points (sum of all x / number of x's, same for y)
• take the farthest point from the center as a corner point
• project line through the 2nd farthest point in a 90° angle of the corner point
• iterate over the points of the other side of the center point and find minimum