7

I am looking for some pointers to algorithms that should allow to tile with no overlap different size rectangles.

Given a set of different sized rectangles, tile them on an area of size H x W with no overlap. The objective would be to maximize the space used or conversely - minimize area of gaps. If there is not enough space, proceed on the second area of the same size and so on.

It is assumed that each rectangle's width and height are smaller than respective dimensions of the tiling area. Rectangles are not rotated or otherwise transformed - i.e. their sides are either horizontal or vertical.

I am not looking for finished code, just curious what approaches/algorithms are the best to use to solve this problem.

Vladislavs Dovgalecs
  • 1,525
  • 2
  • 16
  • 26
  • 1
    Sounds like a textbook [packing problem](http://en.wikipedia.org/wiki/Packing_problem#Different_rectangles_in_a_rectangle) to me. Wikipedia links [this page](http://www.codeproject.com/Articles/210979/Fast-optimizing-rectangle-packing-algorithm-for-bu), which looks useful. – Kevin Jul 30 '12 at 15:24
  • Excellent! This is a keyword which finds the right algorithms at once! I knew this problem should have a special name! Thanks! – Vladislavs Dovgalecs Jul 30 '12 at 15:41

2 Answers2

2

Most simple is to use a kd-tree to subdivide the tree into vertical and horizontal euklidian 2d space. Then you can pack a rectangle into one of the created space and recursively subdivide the tree. There is a Jquery treemap plugin example available online. The jquery plugin masonry can do the same but it's more like a 1d bin-packing solver. 2d bin-packing is much more complicated and can also mean to rotate rectangles. Here is an example for packing lightmaps: http://www.blackpawn.com/texts/lightmaps/default.html.

Micromega
  • 12,486
  • 7
  • 35
  • 72
  • Hmm, could you detail your approach bit more? What happens with the Eucliedean space if there are many hundreds or thousands of rectangles? There is no risk to have a huge tree? – Vladislavs Dovgalecs Jul 30 '12 at 15:44
  • Xeon: You cannot compare apples with orange? Euklidian space is a mathematical law. That's a fact. – Micromega Jul 30 '12 at 15:50
  • Sorry, but I cannot get how you build such a tree and what means splitting the euclidean space. That is, how you pass from your input rectangles to tree, then how you use this tree to obtain the final tiling. – Vladislavs Dovgalecs Jul 30 '12 at 16:00
  • 1
    @xeon: I added a link to an c++ example. – Micromega Jul 30 '12 at 16:02
  • Thanks!As I feared, I asked an already existing question: http://stackoverflow.com/questions/8880975/is-there-a-c-source-lib-to-solve-2d-bin-packing-with-a-rectangular-bin-not-sq – Vladislavs Dovgalecs Jul 30 '12 at 16:05
0

I have one idea that could go in the right direction. The idea is to track ratio of tile area vs white area in a bounding box.

input: unordered set of input rectangles output: filled area

  1. Define empty bounding box
  2. Select such two rectangles A_i and B_j from the input set whose bounding box B contains minimal blank area ratio
  3. Update the bounding box with the two optimal boxes
  4. Put the bounding box in a corner, say (1,1)
  5. Repeat until no boxes
    1. Take a new box from the set such as the updated bounding box has minimum blank
    2. Constrain growing in horizontal or vertical direction if the bounding box width or height exceeds that of output area
    3. If it is impossible to add a new box, proceed with a new area H x W and restart the algorithm, else update the bounding box

There are still some points to define - how to best decide the place of bounding box? How to impose the bounding box growing restrictions? How to efficiently find the best bounding box?

Vladislavs Dovgalecs
  • 1,525
  • 2
  • 16
  • 26
  • No, this is an algorithm that I should find a rapid use in my application. I don't have time to code it from scratch if nice software packages exist already (rapid search with the keywords "2d binning problem", "packaging problem" etc revealed its very well known problem in many areas) – Vladislavs Dovgalecs Jul 30 '12 at 15:57