Using rotating calipers to find the minimum bounding box of points in 2D space is a common approach:
- Generate a convex hull from many points.
- Iterate over each edge of the convex hull.
- Measure the area of the bounding box rotated by the edge vector.
- Store rotation of the edge which yields the bounding box with the smallest area.
See this question: Minimum bounding rectangle of polygon
When looking into implementations of this it seems most implementations follow the steps above, however it seems to me that there are relatively straightforward optimizations that could improve performance for large convex hulls.
Are there common optimizations for this implementation which can improve performance?
I'll note some in my own answer, but I'm surprised not to find optimizations in code I've found linked online.
Listing some potential optimizations:
Track the 2..4 points that meet the bounds, check if the bounds of these points exceeds the known best rotation, before calculating bounds of all other points.
When a bounding-box is larger than the smallest known bounding-box, before checking the next edges rotation.
It's possible to calculate the potential gains form the new rotation without having to calculate the bounds of all points. Making it possible to skip checking some rotations entirely. I'd this should be able to give significant gains when checking many similar rotations which are all worse than the current minimum bounding box.
Use a KD-tree for optimized min/max lookups along 2 axes to calculate bounds.
Modulo the edge angle from 0-90 degrees and sort them, since there is no difference between 45, 135 & 225 degrees.
This means there is a greater likelihood of a reduced between each angle tested which could speed up calculation using the first two optimizations noted here.
De-duplicate edge rotations.
Perform a "coarse" iteration over edge directions first (begin with the best of 4 for example).
Most of the optimizations listed above rely on detecting if the next angle is worse than the known best. This wont work well if the first rotation tested happens to be one of the worst, where the next edge is always providing a better fit. To prevent this from happening an initial check on fewer edges could be used before iterating over every edge of the convex hull.
There are other potential improvements, although I'm less convinced they're of value:
Adjust the order edges are checked, early exist if the bounding box exceeds the best known option. Use a binary search strategy to find the best rotation.
Change the order points are checked when computing a bounding box and early exit if it's worst than the known best option.