CODEWITHSUNDEEP
algorithm
ohho
ohho

Reputation: 51951

What's the algorithm to pack squares and rectangles?

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

Assumptions:

For example:

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

Upvotes: 4

Views: 3113

Answers (2)

Michael Nett
Michael Nett

Reputation: 375

It might help you to look into some tools in computer graphics which are called 'texture atlas generators'. These programs try to pack rectangular textures into a larger one, so basically the same as your problem.

I think there is also some working code available from some guy named Redcliff...

Upvotes: 0

Merlyn Morgan-Graham
Merlyn Morgan-Graham

Reputation: 59151

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.

Upvotes: 3

Related Questions