Given a set of rectangles, find 3 bounding rectangles with the smallest area

Question

I am trying to implement redraw regions with up to 3 regions but can't think of an efficient way to find the best set of regions given a set of rectangles.

So there would be a set of rectangles and I would need to calculate up to 3 bounding rectangles that produce the smallest area.

The black rectangles are the set of rectangles whereas the red rectangles are the bounding boxes (up to 3) that produce the smallest possible area. Need to work out the best possible combination of bounding boxes.

Answer 1

As most 3 rectangles, everything is always going to be oriented and aligned on the x-y axis, and there is no overlap? You are in luck, there are O(n2) sets of 3 such rectangles, and it is pretty easy to enumerate them with O(n3) work. Given that you're dealing with a small enough number of black rectangles for visual display, enumerating them all and picking the best one should be more than fast enough.

First let us think about the 2 bounding rectangle case because it is simpler. It is easy to project the picture to the x-axis, and it is also easy to project the picture to the y-axis. At least one of those two projections will have a visible gap with no overlap. Therefore we can enumerate the possible ways of dividing into two rectangles by first projecting all of the black ones to line segments on the x-axis, look for the gaps, and for each gap reconstruct which pair of bounding boxes we got. Then repeat the procedure with the y-axis. And we will get them all.

Now the 3 bounding rectangle case is similar. It turns out that given 3 non-overlapping rectangles that are oriented along the x-y axis, that either the x projection or the y projection must have a visible gap. So we can do the same procedure as before, but instead of just constructing a pair of bounding boxes, we try ways to construct one bounding box, and divide the other into 2 more using the same algorithm.

(By the way you are lucky that you just wanted 3. This approach breaks down in the 4 bounding rectangle case. Because then it is possible to have 4 bounding rectangles such that neither the x-projection nor the y-projection have any visible gaps.)

So how do we take n black rectangles, project them to one axis (let's say the x-axis), and look for the sets of bounding rectangles? You just sort them, construct the maximum overlapping intervals, and find the gaps. Like this:

function find_right_boundaries_of_x_gaps (rectangles) {
  var ordered_rect = rectangles.sort(function (r1, r2) { return r1.x1 <=> r2.x2 });
  var gaps = [];
  var max_right = ordered_rect[0].x2;
  for (var i = 0; i < ordered_rect.length; i++) {
    if (max_right < ordered_rect[i].x1) {
      gaps.push(max_right);
    }
    if (max_right < ordered_rect[i].x2) {
      max_right = ordered_rect[i].x2;
    }
  }
  return gaps;
}

Given a gap it is straightforward to figure out the 2-rectangle bounding box for what lies on each side. (It is even more straightforward if you have the ordered rectangles to do it with.)

With these pieces you should now be able to write your code. Unfortunately naive approaches give you a choice between building up a lot of repetitive code, or else having to construct a lot of large data structures. However if you're comfortable with closures, you can address both problems in two very different ways.

The first is to construct closures that will, when called, iterate through the various data structures that you want. See http://perl.plover.com/Stream/stream.html for inspiration. The idea here being that you write a function which takes a set of rectangles and returns a stream of pairs of bounding boxes, then another function which takes a set of rectangles, gets the stream of pairs of bounding boxes, and returns a stream of triplets of bounding boxes. Then have a filter that takes that stream and finds the best one.

The other is inside out from that. Rather than return a function that can iterate through possibilities, pass in a function, iterate through possibilities, and call the function on each possibility. (Said function may do further iteration as well.) If you have any exposure to blocks in Ruby, this approach may make a lot of sense to you.

If you're not familiar with closures, you may wish to ignore the last few paragraphs.