The Infinite Loop

Tales from a lean programmer.

Computing oriented minimum bounding boxes in 2D

14 Comments

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 x– and y– coordinates of its vertices. Such an axis aligned bounding box (AABB) can be computed trivially but it’s in most cases significantly bigger than the polygon’s OMBB. Finding the OMBB requires some more work as the bounding box’ area must be minimized, constrained by the location of the polygon’s vertices. Look at the following figure for an illustration (AABB in blue, OMBB in red).

AABB vs OMBB

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 n points can be described as the closed polygonal chain of all outer points of the set, which entirely encloses all set elements. You can picture it as the shape of a rubber band stretched around all set elements. The convex hull of a set of two-dimensional points can be efficiently computed in O(n\log n). In the figure below the convex hull of the vertices of a concave polygon is depicted.

Convex hull of vertices of concave polygon

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 n is small or the polygon’s convex hull contains only a few vertices. The runtime complexity is O(nh), where h is the number of vertices in the convex hull. In the general case Gift Wrapping is outperformed by other algorithms. Especially, when all points are part of the convex hull. In that case the complexity degrades to O(n^2).

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.

OMBB candidates

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.

  1. Compute the convex hull of the input polygon.
  2. Find the the extreme points p_\text{min}=(x_\text{min},y_\text{min})^T and p_\text{max}=(x_\text{max},y_\text{max})^T of the convex hull.
  3. Construct two vertical supporting lines at x_\text{min} and x_\text{max} and two horizontal ones at y_\text{min} and y_\text{max}.
  4. Initialize the current minimum rectangle area A_\text{min}=\infty.
  5. Rotate the supporting lines until one coincides with an edge of the convex hull.
    1. Compute the area A of the current rectangle.
    2. Update the minimum area and store the current rectangle if A<A_\text{min}.
  6. Repeat step 5 until all edges of the convex hull coincided once with one of the supporting lines.
  7. Output the minimum area rectangle stored in step 5.2.

In practice, in every iteration the smallest angle \phi_\text{min} between each caliper line and its associated, following convex hull edge is determined. Then, all caliper lines are rotated at once by \phi_\text{min} and the associated convex hull edge of the caliper line enclosing the smallest angle is advanced to the next convex hull edge.

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.


  1. 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 

14 thoughts on “Computing oriented minimum bounding boxes in 2D

  1. 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.

  2. 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.

  3. For the function of intersectLines…I am a bit confused what computation is going on there!

    • This is the derivation of the formula used in the IntersectLines() function. Let’s say we have to lines L1 and L2:

      L0(t) = start0 + t*dir0
      L1(u) = start1 + u*dir1
      

      L0 and L1 are 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 if L0(t) = L1(u) for some u and t.

          L1(u) = L0(t)
      <=> start1 + u*dir1 = start0 + t*dir0
      <=> u = (start0-start1 + t*dir0)/dir1
      

      The equation above is a vector equation, so it’s actually two equations (in x and y).

      u = (start0_x-start1_x+t*dir0_x)/dir1_x
      u = (start0_y-start1_y+t*dir0_y)/dir1_y
      

      These two equations must equal each other. We arrive at a single equation with a single unknown t. Solving for t gives us the value we can insert into start0 + t*dir0 to 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 dy in IntersectLines() is negated. This is compensated for in the following line by subtracting the relevant part instead of adding it.

      • Thank you! I ended up figuring it out that day, but your response definitely helped reinforce what I realized!

  4. 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?

    • ** 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.

      • 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

      • ps: pivot refers to the center of the plane in which lhs and rhs were 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)”

      • 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 that leftDir, rightDir, topDir, bottomDir and all edgeDirs are 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 the arccos() 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)),
        ];
        
  5. @David Actually, I was not normalizing correctly! It has been fixed. Thank you!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s