在 Javascript 中合理排列矩形

Question

我有一个算法可以打包一组矩形。我的问题是所有矩形最终都在 canvas 的 let 侧完美对齐（以红色标出），但在 canvas:

的右侧没有对齐

我希望每一行都以类似于 justify-content: space-between 的弹性框所获得的方式对齐，看起来像这样：

LINK TO CODESANDBOX

我的特定用例的一些给定：

所有项目高度相同
永远不会有超过 canvas
所有矩形宽度都是某个恒定列宽值（2x、3x、4x）的倍数

现在我对如何暴力破解这个有了一些想法，例如：

进行初始包装
将打包的矩形排序成行
给定一行中矩形的宽度和 canvas 的宽度，计算将它们分布在行的宽度上所需的必要填充量，然后更新每个矩形的坐标

是否有更优雅的解决方案，不涉及在初始打包发生后重复矩形？

这是打包机 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?

如果你想让间距完全均匀，答案是否定的。

您正在动态定位方块，因此在所有方块都已放置之前，方块不知道它是否是一行中的最后一个方块。我不确定我是否会称它为“蛮力”，因为它仍然是 O(n)，但是不，没有神奇的方法让矩形知道它们需要添加多少间距，直到你确定它们不会'该行中不再有矩形。

在 Javascript 中合理排列矩形

Justified Packing of Rectangles in Javascript

javascript

layout

packing

LINK TO CODESANDBOX