[Math] Algorithm to get the maximum size of n rectangles that fit into a rectangle with a given width and height

algorithms

I have the same problem like this guy here, except that I need to change the algorithm posted there to calculate rectangles instead of squares, because I use this to calculate a grid of icons (square images) but with text underneath them.

Is this possible?

I tried to implement his algorithm and just substract the height of the text, but that didn't worked.

PS: My implementation in JavaScript

// Used to subtract margin and border
var squareExtraWidth = $(this).outerWidth(true) - $(this).find('a > img').width();
// Used also to subtract the text height
var squareExtraHeight = $(this).outerHeight(true) - $(this).find('a > img').height();

var hw = containerHeight / containerWidth;
var wh = containerWidth / containerHeight;

var rows = Math.ceil(Math.sqrt(squareCount * hw));
var columns = Math.ceil(Math.sqrt(squareCount * wh));

var sx;
if (Math.floor(rows * wh) * rows < squareCount) {
  sx = containerWidth / Math.ceil(rows * wh);
}
else {
  sx = containerHeight / rows;
}
sx -= squareExtraHeight;

var sy;
if (Math.floor(columns * hw) * columns < squareCount) {
  sy = containerHeight / Math.ceil(columns * hw);
}
else {
  sy = containerWidth / columns;
}
sy -= squareExtraWidth;

var squareDimension = Math.floor(Math.max(sx, sy));

Best Answer

Here's a somewhat inelegant but correct solution to this. It works by trying all combinations of rows and columns

function getBestFit(containerWidth, containerHeight, numRects, aspectRatio) {
  let best = { area: 0, cols: 0, rows: 0, width: 0, height: 0 };

  // For each combination of rows + cols that can fit
  // the number of rectangles, place them and see the area.
  for (let cols = numRects; cols > 0; cols--) {
    const rows = Math.ceil(numRects / cols);
    const hScale = containerWidth / (cols * aspectRatio);
    const vScale = containerHeight / rows;
    let width;
    let height;

    // Determine which axis is the constraint.
    if (hScale <= vScale) {
      width = containerWidth / cols;
      height = width / aspectRatio;
    } else {
      height = containerHeight / rows;
      width = height * aspectRatio;
    }
    const area = width * height;
    if (area > best.area) {
      best = {area, width, height, rows, cols};
    }
  }
  return best;
}

```

If you're using npm, you can find it under rect-scaler.

Related Solutions

[Math] Algorithm for positioning rectangles of various size into a larger rectangle

I guess this should be exactly what you need. Basically it is an implementation of the approach presented in this paper by Richard E. Korf. To quote the introduction:

Given a set of rectangles with fixed orientations, we want to find an enclosing rectangle of minimum area that contains them all with no overlap. Many simple scheduling tasks can be modelled by this NP-complete problem. We use an anytime branch-and-bound algorithm to solve the problem optimally.

Algorithm for Maximum Size of Squares in a Rectangle

Let's analyze a single case:

If we want to cover a $6x5$ rectangle with $7$ squares, we first note that each square at most has an area of $30/7$. We also know that for our filling to be optimal, we need to fill at least an axis.

So now we know that we will fill either the $6$ or the $5$ completely. We will first try with the 5. Since the maximal side of our squares is $\sqrt{30/7}$, we now need the smallest integer more than $5/\sqrt{30/7}$, that is equal to $\lceil5/\sqrt{30/7}\rceil=3$

So we would divide the $5$ in $3$ parts $p_x$, so each side will have $5/3$ . If so, I would cover $(5/3)^2*7=19\frac49$ of the thirty squares. If they don't fit vertically, we try with more parts $p_x$, until the squares fit in the other axis. $$\lfloor6/(5/p_x)\rfloor*\lfloor5/(5/p_x)\rfloor=\lfloor6/(5/p_x)\rfloor*p_x\ge7 \,\,\,\,\,\,\,\,\,\, (5/p_x=\text{the actual size of our squares)}$$ Also, since $p_x$ is integer $\lfloor p_x \rfloor =p_x$

If we do the same with the $6$, we get $\lceil6/\sqrt{30/7}\rceil$ again covering $19\frac49$ of the surface. We then do the same as with the $5$ and save it as $p_y$

Let's now recall the formulas we had.

We had an $x∗y$ rectangle and filled it with $N$ squares. We started with $p_x=⌈x/\sqrt{xy/N}⌉$=$⌈\sqrt{Nx/y}⌉$ or $p_y=⌈y/\sqrt{xy/N}⌉=⌈\sqrt{Ny/x}⌉$ and then we made them fit by shrinking them until they fit in the other axis. But we know we want the area maximised, so $Side=max(x/p_x,y/p_y)$.

A better method:

Once we have the start value $p_x=⌈x/\sqrt{xy/N}⌉=⌈\sqrt{Nx/y}⌉$,if it does not fit in the $y$ axis, we need to make it fit in the $y$ axis. For that, we use that $$a=x/p_x$$ where $a$ is the value of the actual side of our squares. Then we know that for our side to fit we need to reduce it: $$S_x=y/(\lceil y/a \rceil)$$ We do the same with $S_y$ and calculate $max(S_x,S_y)$ The advantage of this is that it needs a constant number of operations, the most expensive one being the square root.

Plain, unoptimized C Code

Some multiplications may be reused but for code readability and practical uses this is enough. Input: values of $x$,$y$, and $n$. Handcoded.

Output: The optimal side of our squares

#include <math.h>
#include <stdio.h>
#define MAX(x,y)    (x)>(y)?(x):(y) 
int main(){
    double x=5, y=6, n=7;//values here
    double px=ceil(sqrt(n*x/y));
    double sx,sy;
    if(floor(px*y/x)*px<n)  //does not fit, y/(x/px)=px*y/x
            sx=y/ceil(px*y/x);
    else
            sx= x/px;
    double py=ceil(sqrt(n*y/x));
    if(floor(py*x/y)*py<n)  //does not fit
            sy=x/ceil(x*py/y);
    else
            sy=y/py;
    printf("%f",MAX(sx,sy));
    return 0;
}

Best Answer

Related Solutions

[Math] Algorithm for positioning rectangles of various size into a larger rectangle

Algorithm for Maximum Size of Squares in a Rectangle

Related Question