I have a problem that, discovered today, may be called "rectangle packing". I found extremely interesting references to papers in this question.
But the rectangles I want to pack have dimensions that are based on grid cells and must fit an evenly spaced grid. That means, rectangle widths and heights are multiples of an evenly spaced grid cell.
So, let's say that we have a 5x5 grid:
+----+----+----+----+----+
| | | | | |
| | | | | |
+----+----+----+----+----+
| | | | | |
| | | | | |
+----+----+----+----+----+
| | | | | |
| | | | | |
+----+----+----+----+----+
| | | | | |
| | | | | |
+----+----+----+----+----+
| | | | | |
| | | | | |
+----+----+----+----+----+
Packing it with the following rectangles:
- 3x3 (1)
- 2x2 (3)
- 1x1 (3)
...can possibly result in:
+----+----+----+----+----+
| 3x3| 2x2|
| | |
+ + +
| | |
| | |
+ +----+----+
| | 1x1| 1x1|
| | | |
+----+----+----+----+----+
| 2x2| 2x2| 1x1|
| | | |
+ + +----+
| | | |
| | | |
+----+----+----+----+----+
...leaving one empty grid cell. Other solutions exist and some invalid ones too.
Which algorithm should I use to accomplish this? I am wondering if, given the rectangle dimensions and grid constraints, this would be much simpler than packing an arbitrarily-sized rectangle with others of equally arbitrary dimensions.