Treemapping with a given aspect ratio

Question

I would like to create a TreeMap, using pictures to fill out the treemap rectangles. I can assume that all the pictures have the same width and height (i.e. the aspect ratio). Thus, I need a treemapping algorithm to create the rectangles with a given ratio, do I will be able to put the pictures there (and perhaps scale the pictures if I need).

Could you recommend one ?

Answer 1

In general, a solution is not possible - Albin Sunnanbo has provided a proof by counterexample. Assuming your bounding rectangle has the same aspect ratio as your target rectangles, you might be able to get a good-enough solution by scaling the bounding rectangle to be a square, running the squarified treemap[pdf] algorithm over it, and then scaling back to a rectangle. Since the squarified treemap doesn't guarantee perfect squares, your final rectangles will not have a perfect aspect ratio, but in practice it might not distort your pictures too much.

A nice refinement would be to run a seam carving pass over your pictures to fit them properly into the slightly-off aspect-ratio rectangles; if you're using this to assemble a collage, for instance, you should get visually pleasing results out of this.