Oriented Bounding-Box Heuristic

The 2-dimensional minimum-area oriented bounding box problem is as follows: Given a set of coplanar points, how can we efficiently find the smallest rectangle which encloses these points? Additionally, that rectangle can be oriented at any angle with respect to the coordinate system.

One interesting estimate for the solution, which guarantees “pretty good” results in O(n) time is a natural extension of orthogonal linear regression. Specifically, we assume that the minimum rectangle is aligned to the orthogonal “line of best fit” of the point set. The parameters for this fit can be found in O(n) time.

This method appears to work when points who are not members of the convex-set do not have much of an effect on the result. Specifically, when the non-convex-set points are evenly distributed, the method generates acceptable boxes.