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

algorithmscomputational geometrypacking-problem

I am working on tool for merging smaller textures into one larger for use on Android app.

I have $n$ rectangles of given size $(w_k, h_k)$, where $k=1,\ldots,n$ and I need to position them within master rectangle of size $2^l \times 2^m$, where $l, m \leq 9$ so none overlapping occur and $2^l \times 2^m$ has minimal possible value. The result should be $(x_k, y_k)$, a position of each of the $n$ base rectangles or information that such positioning is impossible.

Best Answer

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.

Related Solutions

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

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.

[Math] Is packing rectangles exactly into a larger rectangle NP-complete

Partition can be reduced to this problem. Set $S$ can be partitioned iff set of rectangles $\{1 \times (4\cdot x)| x \in S\}$ can be packed into rectangle $2 \times (\sum_{x \in S} 2x)$: rectangles from upper row corresponds to one subset, from bottom to other, and multiplication by $4$ ensures all rectangles are placed horizontally.

Best Answer

Related Solutions

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

[Math] Is packing rectangles exactly into a larger rectangle NP-complete

Related Question