Tile (scalable) stacking algorithm

Question

Here is the problem. I have rectangular canvas that have size of 1. So it have coordinate sistem of (0.0 ... 1.0 - x and 0.0 ... 1.0 - y).

I also have some tiles. Tiles are also rectangles. They have diffrent size and amount of tiles is a variable.

I want to stack tiles in rectangular canvas, from 0.0 to 1.0 (from left to right, from top to bottom):

1) tiles have to fit in canvas (but fill as much space as they could)

2) tiles have to be scaled (if they don't fit), each tile should be scaled by the same amount (they have to remain same proportions).

3) imagine that you have this 'tiles' in your hand, and you placing them into this canvas one after another

4) it almost like "TreeMap algorithm" but - shape of tiles have to be the same (rectangles) and i don't need to fill all space of canvas

Is there anybody who can show me an algoritm in any C alike language (C, C++, Java, C#)?

*I tried this.

1) i calculated area of tile, then i calculate a sum of tile's areas (for example: i have two tiles, one have area of 2, other area of 1, them it's mean i have total sum of 3)

2) then i calculate what "proportion" each tile have in "total sum of areas" (for example: 2/3 and 1/3)

3) then calculate size of rectangle tile by Math.sqrt(x) (for example: Math.sqrt(2/3))

4) then draw tile one by one...

But this dosen't work always. Sometimes i get tiles to be out of canvas..*

Answer 1

It may appear that this is a packing problem, however if we try to solve this problem exactly as it described it is not. In other words there is no solution because, again, there is no problem in a question as it is described. If we have ONLY ONE box and fixed set of tiles and requirement that they ALL must fit into box there is no room for optimization. I can see several related optimization problems:

1. Given fixed set of tiles that must be packed into boxes of same or different sizes find optimal packing order so that minimal number of boxes is used.

2. Given single box of an arbitrary size and set of tiles find optimal (maximum) set of tiles that can be fit into a box.

3. Given a box and set of tiles - answer the question if it is possible to fit them into a box or not.

Which one of these are you trying to solve?

The way problem is set right now is meaningless, because no matter which order you place the tiles in the box they will always use same amount of space no matter how they are arranged, as soon as they all fit in of course.

Answer 2

Try a monte-carlo algorithm:

Repeat until result is good enough or until you aren't seeing any improvement
  Select (with removal) a random first tile
  Place the first tile at a random position
  Repeat until no remaining tiles
    Select (with removal) a random tile
    Place it adjoining to the existing "tile blob" 
      (you might have to do a search here to find the best place to plug it in)
  Check to see if you have a new best filled-area percentage

All random tile selections should be weighted by the tile's area so that you tend to place the larger ones first.

Answer 3

I don't think this is a (bin)-packing problem because I wrote one for the 1D bin-packing problem. I think the problem here is solved by the 2D-cutting-stock problem, maybe there is also a 2D-bin-packing. What you want is to try the knappsack-problem too. This problem is hard to solve (NP) and there is no solution. It's a bit like the Travelsalesman problem where the number of solution is exponential to the number of cities. If you can reduce the ccomplexity to a 1D problem you may try my bin-packing algorithm at phpclasses.org.