0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Can you add to the start of your post a precise statement of the problem (input and desired output?) $\endgroup$ – 6005 May 8 at 14:11
  • $\begingroup$ What is the measure you are trying to optimize? Do you want to minimize $s$? $\endgroup$ – Steven May 8 at 16:11
  • $\begingroup$ Yes, so that most of the space is filled in the end. $\endgroup$ – Antonin Décimo May 8 at 16:13
  • $\begingroup$ I think I’m going to find a 2D bin packing for $(W, H)$. If rectangles doesn’t fit, multiply dimensions by a smart factor until rectangles fit. Then, reduce the factor by dichotomy between the last fit and did-not-fit factor values. $\endgroup$ – Antonin Décimo May 8 at 16:15
  • $\begingroup$ Please edit the question to incorporate that information. I don't see anything in the question about what is the objective function you are minimizing, or indeed that there is a minimization. $\endgroup$ – D.W. May 8 at 23:54
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

-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

enter image description here

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.