54

I'm trying to fit a rectangle around a set of 8 2D-Points, while trying to minimize the covered area.

Example:

enter image description here

The rectangle may be scaled and rotated. However it needs to stay a rectangle.

My first approach was to brute force each possible rotation, fit the rectangle as close as possible, and calculate the covered area. The best fit would be then the rotation with the lowest area.

However this does not really sound like the best solution.

Is there any better way for doing this?

24
  • So, what's the complexity of your brute force solution? There are O(n) edges on the convex hull. Even if you use a brute force rectangle shrink wrap, you end up O(n^2), with th(n^1.5) in practice. Dec 27, 2015 at 10:15
  • 1
    I was hoping to find a better solution, instead of a brute force approach
    – tobspr
    Dec 27, 2015 at 10:17
  • 4
    @MrSmith42 - My gut tells me the converse; that one edge of the convex hull will be part of the minimal rectangle. Can't prove it yet, though... Dec 27, 2015 at 10:21
  • 1
    @MrSmith42 I'd try aligning the bounding box with the top two points. Dec 27, 2015 at 10:25
  • 5
    So... compute the convex hull; for each range of angles between the convex hull directions mod 90 degrees, the rectangle is bounded by the same four points. Find the minimum of the corresponding area function (whose form is known in advance). Take the lowest minimum. Dec 27, 2015 at 10:28

3 Answers 3

37

I don't know what you mean by "try every possible rotation", as there are infinitely many of them, but this basic idea actually yields a very efficient solution:

The first step is to compute the convex hull. How much this actually saves depends on the distribution of your data, but for points picked uniformly from a unit disk, the number of points on the hull is expected to be O(n^1/3). There are a number of ways to do that:

  • If the points are already sorted by one of their coordinates, the Graham scan algorithm does that in O(n). For every point in the given order, connect it to the previous two in the hull and then remove every concave point (the only candidate are those neighboring the new point) on the new hull.
  • If the points are not sorted, the gift-wrapping algorithm is a simple algorithm that runs at O(n*h). For each point on the hull starting from the leftmost point of the input, check every point to see if it's the next point on the hull. h is the number of points on the hull.
  • Chen's algorithm promises O(n log h) performance, but I haven't quite explored how it works.
  • another simle idea would be to sort the points by their azimuth and then remove the concave ones. However, this only seems like O(n+sort) at first, but I'm afraid it actually isn't.

At this point, checking every angle collected thus far should suffice (as conjenctured by both me and Oliver Charlesworth, and for which Evgeny Kluev offered a gist of a proof). Finally, let me refer to the relevant reference in Lior Kogan's answer.

For each direction, the bounding box is defined by the same four (not necessarily distinct) points for every angle in that interval. For the candidate directions, you will have at least one arbitrary choice to make. Finding these points might seem like an O(h^2) task until you realise that the extremes for the axis-aligned bounding box are the same extremes that you start the merge from, and that consecutive intervals have their extreme points either identical or consecutive. Let us call the extreme points A,B,C,D in the clockwise order, and let the corresponding lines delimiting the bounding box be a,b,c,d.

So, let's do the math. The bounding box area is given by |a,c| * |b,d|. But |a,c| is just the vector (AC) projected onto the rectangle's direction. Let u be a vector parallel to a and c and let v be the perpendicular vector. Let them vary smoothly across the range. In the vector parlance, the area becomes ((AC).v) / |v| * ((BD).u) / |u| = {((AC).v) ((BD).u)} / {|u| |v|}. Let us also choose that u = (1,y). Then v = (y, -1). If u is vertical, this poses a slight problem involving limits and infinities, so let's just choose u to be horizontal in that case instead. For numerical stability, let's just rotate 90° every u that is outside (1,-1)..(1,1). Translating the area to the cartesian form, if desired, is left as an exercise for the reader.

0
32

It has been shown that the minimum area rectangle of a set of points is collinear with one of the edges of the collection's convex hull polygon ["Determining the Minimum-Area Encasing Rectangle for an Arbitrary Closed Curve" [Freeman, Shapira 1975]

An O(nlogn) solution for this problem was published in "On the computation of minimum encasing rectangles and set diameters" [Allison, Noga, 1981]

A simple and elegant O(n) solution was published in "A Linear time algorithm for the minimum area rectangle enclosing a convex polygon" [Arnon, Gieselmann 1983] when the input is the convex hull (The complexity of constructing a convex hull is equal to the complexity of sorting the input points). The solution is based on the Rotating calipers method described in Shamos, 1978. An online demonstration is available here.

-1

They first thing that came to mind when I saw this problem was to use principal component analysis. I conjecture that the smallest rectangle is the one that satisfies two conditions: that the edges are parallel with the principal axes and that at least four points lie on the edges (bounded points). There should be an extension to n dimensions.

4
  • Huh? Edges parallel with the principal axes? Then why is the fitted rectangle tilted? Is my monitor crooked? Dec 30, 2015 at 12:36
  • The principal axes are not parallel to the edges of your monitor. They are determined by the points.
    – polarise
    Dec 30, 2015 at 12:37
  • Ah, so you define the direction of the edges ... not at all. :P Dec 30, 2015 at 12:45
  • See Mathematics for 3D Game Programming and Computer Graphics, Section 8.1.1 (pp212 onwards)
    – polarise
    Jan 6, 2016 at 13:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.