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.

Russ

so basically you want to determine the first available y-position to draw a rectangle? – Ding

Are you looking to pack them, or optimally pack them? – Biosphere

looks like the x position is unchangeable but the y position is? – Bonnard

I am having difficulty understanding the question. Perhaps better graphics will help. – Inboard

I think what the whole idea is to minimize the number of rows, and efficiently use the space on each row. Assuming all rectangles are of same height. X position of all the rectangles are given and is fixed. However, Y coordinates can be changed. – Sparge

Imagine these rectangles as tasks of given start-time and time-length, solve them using few number of processors. – Sparge

Are the heights of the rectangles the same? – Centigrade

Did you ever solve this problem? I'm running into the exact same issue. – Megdal

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.

Shorten

I first voted you up but reading the question again, if his x-coordinates are set he doesn't have an NP-hard problem. Depending on whether the height of the rectangles is all the same, it can be solved by something like Jasper's algorithm. – Centigrade

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.

Selfexcited

Answer 3

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);
  }
  

Ding

Aside from that, yeah I think this is a correct algorithm. I think it's the optimum, if the rectangles are all the same height and the x-coordinates (which I think are start times in a scheduling algorithm?) are fixed. – Centigrade

My rectangles are not all of the same height, and x-coordinates are really spatial, no temporal coordinates, but you're right that it changes nothing to the problem. – Russ

the four spaces didn't work, but pre and code tags did. As for the problem of height that is determined in the inner for loop. If the height is fixed you could also multiply the height times the number of overlapping elements to calculate the y-position. – Ding

It's important to distinguish whether you sort rectangles by their left or right edge. Sorting by their right edge is optimal for the corresponding scheduling problem. – Thebaine

Answer 4

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?

Pedo

Specifically, when sorting rectangles "from left to right" you should sort by their rightmost endpoints. I'm also not sure if this gives an optimal solution for the same-height problem, but it gives an optimal solution for the closely related scheduling problem of maximising the number of tasks that can be completed. – Thebaine

Answer 5

Put a tetris-like game into you website. Generate the blocks that fall and the size of the play area based on your paramters. Award points to players based on the compactness (less free space = more points) of their design. Get your website visitors to perform the work for you.

Broadloom

Distributed computing at its best :) Let's call it the 'human brain cloud' :) – Centigrade

It may be a good solution, but i doubt i will find enough workers, with enough time. Thanks. – Russ

Answer 6

I had worked on a problem like this before. The most intuitive picture is probably one where the large rectangles are on the bottom, and the smaller ones are on top, kinda like putting them all in a container and shaking it so the heavy ones fall to the bottom. So to accomplish this, first sort your array in order of decreasing area (or width) -- we will process the large items first and build the picture ground up.

Now the problem is to assign y-coordinates to a set of rectangles whose x-coordinates are given, if I understand you correctly.

Iterate over your array of rectangles. For each rectangle, initialize the rectangle's y-coordinate to 0. Then loop by increasing this rectangle's y-coordinate until it does not intersect with any of the previously placed rectangles (you need to keep track of which rectangles have been previously placed). Commit to the y-coordinate you just found, and continue on to process the next rectangle.

Aedile