Justified Packing of Rectangles in Javascript

Question

I have an algorithm that packs a set of rectangles. My problem is that all of the rectangles end up perfectly aligned on the let side of the canvas (outlined in red), but not on the right side of the canvas:

I'd like each row to be justified in a fashion similar to what you get with a flex box with justify-content: space-between, which look something like this:

LINK TO CODESANDBOX

Some givens for my particular use case:

• All items are the same height
• There will never be more rectangles than can be packed inside of the canvas
• All rectangles widths are multiples of some constant column width value (2x, 3x, 4x)

---

Now I have some ideas about how I could brute force this, for example:

• Do the initial packing
• Sort the packed rects into rows
• Given the widths of the rectangles in a row and the width of the canvas, calculate the necessary amount of padding needed to spread them over the width of the row, then update the coordinates of each rectangle

Is there a more elegant solution that doesn't involve reiterating over the rectangles after the initial packing occurs?

Here's the Packer class:

export interface Block {
  w: number;
  h: number;
  fit?: Node;
}

export interface Node {
  x: number;
  y: number;
  w: number;
  h: number;
  used?: boolean;
  down?: Node;
  right?: Node;
}

export class Packer {
  readonly w: number;
  readonly h: number;
  readonly root: Node;
  readonly gutter: number;

  constructor(w: number, h: number, gutter?: number) {
    this.w = w;
    this.h = h;
    this.gutter = gutter ?? 5;
    this.root = { x: 0, y: 0, w: w, h: h, used: false };
  }
  fit(blocks: Block[]): void {
    let n, node, block;
    for (n = 0; n < blocks.length; n++) {
      block = blocks[n];
      block.w += this.gutter;
      block.h += this.gutter;
      if ((node = this.findNode(this.root, block.w, block.h)))
        block.fit = this.splitNode(node, block.w, block.h);
    }
  }
  findNode(root: Node, w: number, h: number): Node | null {
    if (root.used && root.right && root.down)
      return this.findNode(root.right, w, h) || this.findNode(root.down, w, h);
    else if (w <= root.w && h <= root.h) return root;
    else return null;
  }
  splitNode(node: Node, w: number, h: number): Node {
    node.used = true;
    node.down = { x: node.x, y: node.y + h, w: node.w, h: node.h - h };
    node.right = { x: node.x + w, y: node.y, w: node.w - w, h: h };
    return node;
  }
}

export default Packer;

Answer 1

Is there a more elegant solution that doesn't involve reiterating over the rectangles after the initial packing occurs?

If you want the spacing to be perfectly even, the answer is no.

You're positioning the blocks dynamically, so a block doesn't know if it's the last one in a row or not until all the blocks have been placed. I'm not sure if I'd call it "brute force" since it's still O(n), but no, there's no magical way for rectangles to know how much spacing they need to add until you're certain there won't be any more rectangles in that row.