- a enclosing rectangle of size $(W, H)$
- a family of rectangles $R= (R_1;R_2;\dots;R_n);R_i=(w_i;h_i)$
- a scaling factor $s$
- a 2D bin packing of $R$ in a rectangle of size $(sW, sH)$
I have a set of rectangles of various dimensions that I’d like to fit in an enclosing rectangle. This is a classic instance of the 2D-packing problem.
However, in my instance, the enclosing rectangle has fixed dimensions. All the rectangles should fit in it, but they possibly would have to be scaled and must keep their respective aspect ratios. They must not be rotated.
Most examples of 2D-packing algorithms find the enclosing square of least area, or assume that one of the dimensions isn't constrained.
I think that a good solution would be to find an enclosing rectangle R of aspect ratio (roughly) equal to that of the target fixed-dimensions enclosing rectangle T, then scale all the enclosed rectangles down with the ratio of R over T. It seems better to have a global ratio, so that rectangles keep their relative proportions.
I did not find any convincing algorithms, and cannot think of one except enumerating enclosing rectangles until one with a suitable aspect ratio is found.
Could you point me towards a working algorithm that I missed, or a better solution?
Related question, but the answer isn’t satisfying.
Imagine you want to display a bunch of pictures in a screen, however the screen's too small. So you display the picture in a virtual screen keeping the aspect ratio of the original screen, the scale the whole thing down.