2D packing in fixed dimensions rectangle

Question

Input:

• 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)$

Output:

• 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.

Thank you!

Answer 1

This is equivalent to finding the enclosing square of minimum area for rectangles of size $(w_i/W, h_i/H)$.

You seem to have found algorithms for this problem already. There are many heuristics (here or here) and exact models (here), available when searching for "2D packing algorithm". The ones linked handle the case with variable W and H as well.

Answer 2

-In bin packing u have fixed size/weight trucks say K & want to find the min no. of them n to hold all the given goods.

-I take it u think of solving ur problem as it is bin packing to get n, then make all the rectangles scaled down to 1/n.

-Since rectangles can't be reshaped or even rotated, u see it as 2D bin packing.

-As start, u may solve 2 bin packing instances (1D each) one in width and one in height, then take the maximum of the 2 n's as a solution. However, this may not be the optimal solution (ur rectangle may have unnecessary empty space), but bin parking is NP-COMPLETE with no easy upperbounded heuristic anyway.

don't know why do I see it in my first thought as an optimization problem

WH = S0*W0*H0 + S1*W1*H1 +.... + Si* WiHi +..... +SnWn*Hn

If u accept to solve this in any approx. method, solve it twice

W = S0*W0 + S1*W1 +.... + Si* Wi +..... +Sn*Wn

H = S'0*H0 + S'1*H1 +.... + S'iHi +..... +S'nHn

You may check also geometric set problems, maybe you can find something interesting/helpful

https://www.sciencedirect.com/science/article/pii/S0925772112000740