Introduction
Oriented bounding boxes are an important tool for visibility testing and collision detection in computer graphics. In this post I want to talk about how to compute the oriented minimum bounding box (OMBB) of an arbitrary polygon in two dimensions. As a polygon just enforces an ordering on a set of points (vertices), everything described in the following equally applies to simple point sets. Minimum in this context refers to the area of the bounding box. A minimum oriented bounding box is also known as smallest-area enclosing rectangle. However, I will stick to the former term throughout this article as it is more frequently used in the computer graphics world.
The easiest way of computing a bounding box for a polygon is to determine the minimum and maximum 
The technique for computing OMBBs presented in the following consists of two detached steps. In the first step the convex hull of the input polygon is computed. If the polygon is convex this step can be omitted because a convex polygon is equal to its convex hull. In the second step the Rotating Calipers method is employed on the convex hull to compute the resulting OMBB. I will focus on the Rotating Calipers method because it’s not very widely known in comparison to the numerous ways of computing convex hulls.
Convex hulls
In less mathematical but more illustrative terms the convex hull of a set of 
There are numerous algorithms for computing convex hulls: Quick Hull, Gift Wrapping (also known as Jarvis March), Graham’s Algorithm and some more. I’ve chosen the Gift Wrapping algorithm for my implementation because it’s easy to implement and provides good performance in case 
As there are many good articles on the Gift Wrapping algorithm available online, I won’t describe it another time here. Instead I want to focus on the lesser-known Rotating Calipers method for computing OMBBs. However, take care that your convex hull algorithm correctly handles collinear points. If multiple points lie on a convex hull edge, only the spanning points should end up in the convex hull.
Rotating Calipers
Rotating Calipers is a versatile method for solving a number of problems from the field of computational geometry. It resembles the idea of rotating a dynamically adjustable caliper around the outside of a polygon’s convex hull. Originally, this method was invented to compute the diameter of convex polygons. Beyond that, it can be used to compute OMBBs, the minimum and maximum distance between two convex polygons, the intersection of convex polygons and many things more.
The idea of using the Rotating Calipers method for computing OMBBs is based on the following theorem, establishing a connection between the input polygon’s convex hull and the orientation of the resulting OMBB. The theorem was proven in 1975 by Freeman and Shapira1:
The smallest-area enclosing rectangle of a polygon has a side collinear with one of the edges of its convex hull.
Thanks to this theorem the number of OMBB candidates is dramatically reduced to the number of convex hull edges. Thus, the complexity of the Rotating Calipers method is linear if the convex hull is already available. If it isn’t available the overall complexity is bound by the cost of computing the convex hull. An example of a set of OMBB candidates (red) for a convex hull (green) is depicted in the figure below. Note, that there are as many OMBB candidates as convex hull edges and each OMBB candidate has one side flush with one edge of the convex hull.
To determine the OMBB of a polygon, first, two orthogonally aligned pairs of parallel supporting lines through the convex hull’s extreme points are created. The intersection of the four lines forms a rectangle. Next, the lines are simultaneously rotated about their supporting points until one line coincides with an edge of the convex hull. Each time an edge coincides, the four lines form another rectangle / OMBB candidate. This process is repeated until each convex hull edge once coincided with one of the four caliper lines. The resulting OMBB is the OMBB candidate with the smallest area. The entire algorithm is outlined step by step below.
- Compute the convex hull of the input polygon.
- Find the the extreme points
and
of the convex hull.
- Construct two vertical supporting lines at
and
and two horizontal ones at
and
.
- Initialize the current minimum rectangle area
.
- Rotate the supporting lines until one coincides with an edge of the convex hull.
- Compute the area
of the current rectangle.
- Update the minimum area and store the current rectangle if
.
- Compute the area
- Repeat step 5 until all edges of the convex hull coincided once with one of the supporting lines.
- Output the minimum area rectangle stored in step 5.2.
In practice, in every iteration the smallest angle 
Wrap up
Rotating Calipers is a very elegant method for computing OMBBs in two dimensions. O’Rourke generalized it to three dimensions, yielding an algorithm of cubic runtime complexity. However, in practice approximation algorithms are used for three dimensional data because they’re usually faster. Beyond that, it's worth knowing the Rotating Calipers technique as it can be employed with minor changes to numerous other geometric problems. Depending on the programming language the implementation of the entire algorithm, including the convex hull computation, requires merely 150-200 lines of code. My sample implementation in Javascript can be found in my github repository.
- H. Freeman, R. Shapira. Determining the minimum-area encasing rectangle for an arbitrary closed curve. Communications of the ACM, 18 Issue 7, July 1975, Pages 409-413 ↩
May 7, 2014 at 1:17 pm
You can initialize the minimum area of the rectangle according to the AABB you found when computing the Ymin , Ymax, Xmin, Xmax. It’s not much, but keeps you from having to think what is “infinite” in your implementation.
May 7, 2014 at 2:47 pm
Good point. In general, it’s a good idea to set the current minimum/maximum to the first set element when computing the minimum/maximum of a set of values.
June 10, 2014 at 12:10 pm
I’ts been a while since I’ve commented here, but, if you’re interested, I’ve made an implementation for the minimum bounding box that doesn’t rely on floating point arithmetic, so it’s not so prone to rounding errors.
I thought should share it with you, since your post was my best resource on implementing this problem. Take a look at https://github.com/alvarob/ref_maratonas/blob/master/cpp/geometria/rotating_calipers/min_enclosing_rect.cpp
The geometry functions used were taken from the book Competitive Programming 3, from Steven Halim and Felix Halim.
April 27, 2015 at 9:28 am
The algorithm proposed by Freeman and Shapira referenced above is inefficient and runs in quadratic time as a function of the size of the input polygon.
The efficient linear time algorithm described above was originally proposed by Godfried Toussaint and published here:
G. T. Toussaint, “Solving geometric problems with the rotating calipers, ” Proceedings of IEEE MELECON’ 83, Athens, Greece, May 1983.
Many additional problems that can be solved in two and three dimensions are given here:
G. T. Toussaint, “Applications of the rotating calipers to geometric problems in two and three dimensions,” International Journal of Digital Information and Wireless Communications, Vol. 4, No. 3, 2014, pp. 108-122.
July 8, 2016 at 10:24 pm
For the function of intersectLines…I am a bit confused what computation is going on there!
July 11, 2016 at 10:26 am
This is the derivation of the formula used in the
IntersectLines()function. Let’s say we have to linesL1andL2:L0andL1are parallel if the cross product of their direction vectors is 0, but this case we don’t need to consider because we know that our lines are never parallel. The two lines intersect in a point ifL0(t) = L1(u)for someuandt.L1(u) = L0(t) <=> start1 + u*dir1 = start0 + t*dir0 <=> u = (start0-start1 + t*dir0)/dir1The equation above is a vector equation, so it’s actually two equations (in x and y).
These two equations must equal each other. We arrive at a single equation with a single unknown
t. Solving fortgives us the value we can insert intostart0 + t*dir0to get the intersection point.(start0_x-start1_x + t*dir0_x)/dir1_x = u = (start0_y-start1_y + t*dir0_y)/dir1_y <=> (start0_x-start1_x + t*dir0_x)*dir1_y = (start0_y-start1_y + t*dir0_y)*dir1_x <=> start0_x*dir1_y - start1_x*dir1_y + t*dir0_x*dir1_y = start0_y*dir1_x - start1_y*dir1_x + t*dir0_y*dir1_x <=> t*dir0_x*dir1_y - t*dir0_y*dir1_x = start0_y*dir1_x - start1_y*dir1_x - start0_x*dir1_y + start1_x*dir1_y <=> t*(dir0_x*dir1_y - dir0_y*dir1_x) = start0_y*dir1_x - start1_y*dir1_x - start0_x*dir1_y + start1_x*dir1_y <=> t = (start0_y*dir1_x - start1_y*dir1_x - start0_x*dir1_y + start1_x*dir1_y) / (dir0_x*dir1_y - dir0_y*dir1_x) <=> t = ((start0_y-start1_y)*dir1_x + (start1_x-start0_x)*dir1_y) / (dir0_x*dir1_y - dir0_y*dir1_x)Note, that
dyinIntersectLines()is negated. This is compensated for in the following line by subtracting the relevant part instead of adding it.July 11, 2016 at 7:03 pm
Thank you! I ended up figuring it out that day, but your response definitely helped reinforce what I realized!
July 11, 2016 at 7:09 pm
I am running into bugs where I am finding the arccosines. I keep getting NaN. The dot product for two of my vectors ends up being 11 point something. Hence, when I find the arccosine, it ends up being undefined. Is this suppose to happen?
July 11, 2016 at 7:18 pm
** actually just realized why its problematic. Wolfram Alpha actually approximates it to pi/2. But the javascript function only takes in numbers that range from -1 to 1.
July 11, 2016 at 8:06 pm
try using this angle comparison function: https://github.com/alvarob/ref_maratonas/blob/master/cpp/geometria/aleatorio/angle_sort.cpp
it doesn’t rely on actually calculating the arcs, so it’s safer
July 11, 2016 at 8:10 pm
ps:
pivotrefers to the center of the plane in whichlhsandrhswere calculated. so, if you have two vectors, pivot should be(0, 0).the comments, translated from portuguese, are: “comparing quadrants first guarantees transitivity property needed for sorting (if a>b and b>c, then a > c)”
July 12, 2016 at 6:20 am
For normalized vectors
angle = arccos(dot(v1, v2))is defined. The range of the dot product of any two unit vectors is [-1, 1]. Looking at the code again, it seems to me thatleftDir,rightDir,topDir,bottomDirand alledgeDirsare all correctly normalized. So it’s a little funny that you’re observing the dot product becoming something around 11. Could post the data-set you tested with?A solution that seems to work is using
atan2()instead of thearccos()function. The following code works for me, though I don’t have a failing case to test with. Could you either send me your failing test-case, or let me know if that piece of code fixes it for you?var phis = // 0=left, 1=right, 2=top, 3=bottom [ Math.abs(Math.atan2(leftDir.x, leftDir.y)-Math.atan2(edgeDirs[leftIdx].x, edgeDirs[leftIdx].y)), Math.abs(Math.atan2(rightDir.x, rightDir.y)-Math.atan2(edgeDirs[rightIdx].x, edgeDirs[rightIdx].y)), Math.abs(Math.atan2(topDir.x, topDir.y)-Math.atan2(edgeDirs[topIdx].x, edgeDirs[topIdx].y)), Math.abs(Math.atan2(bottomDir.x, bottomDir.y)-Math.atan2(edgeDirs[bottomIdx].x, edgeDirs[bottomIdx].y)), ];July 12, 2016 at 6:46 pm
@David Actually, I was not normalizing correctly! It has been fixed. Thank you!
July 12, 2016 at 6:48 pm
Cool! Your welcome!