What's the algorithm to pack squares and rectangles?

Question

Similar to the Windows 8 Slate interface, how to nicely fill a screen with squares and rectangles without leaving holes?

Assumptions:

• a rectangle is basically two connected squares
• the rectangles can be horizontal or vertical
• the screen width is 3 times of the width of a square
• the screen is filled from top to bottom
• such that the lowest part of the screen may not be aligned fully
• the order of rectangles and squares come in randomly (but can be re-ordered in a small cache before put onto screen, the cache size is limited, say 12)

For example:

  +---++---++---+
  |   ||   ||   |
  +---++---+|   |
  +---++---+|   |
  |   ||   ||   |
  +---+|   |+---+
  +---+|   |+---+
  |   ||   ||   |
  +---++---++---+
  +--------++---+
  |        ||   |
  +--------+|   |
  +---++---+|   |
  |   ||   ||   |
  |   |+---++---+
  |   |
  |   |
  +---+

Answer 1

I believe this is a subset of Packing Problems.

One algorithm to solve this is to use Linear Programming.

Define constraints that ensure rectangles don't overlap, then solve for that. Then weight the algorithm to favor the upper/left corner of the screen, and the narrowest width/height. Also weight the algorithm to favor spacing out larger rectangles.

Since you have a target screen resolution, you can add constraints for width and height, and relax the height constraint if the algorithm fails to find a solution.

This is pretty heavy-weight, though. You could probably use a much less robust algorithm to simplify the problem and still get okay results. E.g.:

Take items in order of display preference
Start at the top-left
For each item:
    Try to stack horizontally, going right ("favoring" left)
    if it won't fit on the screen:
        try to stack on the next row
        when trying to stack on the next row:
            if any "gaps" exist in the current row:
                see if you have a less "regular" rectangle that will fit in the gap
            else
                "favor" placing it farther left

Edit:

I read your existing constraints after posting this answer.

The fact that rectangles have the same dimensions probably will allow you to optimize the problem - e.g. using a bit array and indexing rather than some tree-based spatial container.

It will probably let you short-cut and special case certain decisions - e.g. place all 1x1 squares, then fit double-tall, displacing squares, then fit double-wide, displacing squares and rectangles. Or the reverse, since fitting smaller rectangles is always easier than fitting larger ones. Just make sure you space out the large rectangles in a likely eye-pleasing/somewhat random way, and take a volume count first so you don't force scrolling that doesn't have to happen.