Packing rectangles for compact representation

Question

I am looking for pointers to the solution of the following problem: I have a set of rectangles, whose height is known and x-positions also and I want to pack them in the more compact form. With a little drawing (where all rectangles are of the same width, but the width may vary in real life), i would like, instead of.

-r1-
  -r2--
     -r3--
       -r4-
        -r5--

something like.

-r1-  -r3-- 
  -r2-- -r4-
         -r5--

All hints will be appreciated. I am not necessarily looking for "the" best solution.

Answer 1

Your problem is a simpler variant, but you might get some tips reading about heuristics developed for the "binpacking" problem. There has been a lot written about this, but this page is a good start.

Answer 2

Topcoder had a competition to solve the 3D version of this problem. The winner discussed his approach here, it might be an interesting read for you.

Answer 3

Are the rectangles all of the same height? If they are, and the problem is just which row to put each rectangle in, then the problem boils down to a series of constraints over all pairs of rectangles (X,Y) of the form "rectangle X cannot be in the same row as rectangle Y" when rectangle X overlaps in the x-direction with rectangle Y.

A 'greedy' algorithm for this sorts the rectangles from left to right, then assigns each rectangle in turn to the lowest-numbered row in which it fits. Because the rectangles are being processed from left to right, one only needs to worry about whether the left hand edge of the current rectangle will overlap any other rectangles, which simplifies the overlap detection algorithm somewhat.

I can't prove that this is gives the optimal solution, but on the other hand can't think of any counterexamples offhand either. Anyone?

Answer 4

Something like this?

• Sort your collection of rectangles by x-position

• write a method that checks which rectangles are present on a certain interval of the x-axis

  Collection<Rectangle> overlaps (int startx, int endx, Collection<Rectangle> rects){
  ...
  }
  

• loop over the collection of rectangles

  Collection<Rectangle> toDraw;
  Collection<Rectangle> drawn;
  foreach (Rectangle r in toDraw){
  Collection<Rectangle> overlapping = overlaps (r.x, r.x+r.width, drawn);
  int y = 0;
  foreach(Rectangle overlapRect in overlapping){
  y += overlapRect.height;
  }
  drawRectangle(y, Rectangle);
  drawn.add(r);
  }