获取图像的明确高度并将它们布置在最佳紧凑的“砖石”式布局中的算法？

Question

我正在使用 react-masonry-css 以类似砖石的布局布置一些图像，但它只是在每一列中基本上放置相同数量的图像，并且最终在剩余空间量上存在很大差异在每列的底部，如此处所示（这是所有列的底部）：

（请注意，此演示中缺少一些图像，但即使它们都存在，底部剩余空间也会有很大差异）。

看起来图书馆所做的就是在每列中放置相同数量的项目，而不管图像高度如何。

我希望它能更优化地分布图像，因为我还在 JSON 数据中包含了每个图像的宽度和高度。我如何使用高度来确定如何以最佳方式将图像放置在已知数量的列中？乍一看似乎非常复杂，就像它需要一个复杂的类似研究论文的算法。真的吗？如果是这样，用于解决这个问题的一般算法是什么，所以我可以着手用 JavaScript 编写一个快速实现？如果它很简单，它是如何完成的？

到目前为止，在我的脑海中，我可能会用图像的数量除以列的数量来粗略估计每列的数量。然后我会在每一列中放一张图片，所以 7 列中的每一列都有 1 张图片。然后我会像砖一样铺在下一张图片的柱子上。我会尽力保持列高相同，搜索并选择适合适当高度的图像。

这只是头脑风暴，但我已经可以看到这种不可行的方法中的几个漏洞和陷阱。这似乎很难，想知道这是否是一个已解决的问题，因为图像的高度可能有很大差异。

最终目标是让所有列的高度大致相同，仅此而已。尽可能接近。

Answer 1

如果我们将“最紧凑”操作化为最短的边界框， 那么这是一个相同的机器 调度 问题。每个图像对应一个作业，每一列对应 机器。作业的处理时间是作业的高/宽比 相应的图像（加上填充）。

虽然调度是 NP-hard，但有一个简单且可证明有效的方法 称为最长处理时间的近似值 首先。 就您的问题而言，对于每个图像按降序排列 高度/宽度，您将其分配给当前的列 最短的。 （您可以在末尾打乱每列中图像的顺序 以避免偏向更高的图像。）边界框永远不会 比需要的时间长 34% 以上（好吧，也许多一点 因为插页式广告）。

// Set up some test data.
const imageCount = 50;
let images = [];
for (let i = 0; i < imageCount; ++i) {
  // Allow the images to vary in aspect ratio between 5:1 and 1:5.
  images.push({
    id: i,
    width: Math.random() + 0.25,
    height: Math.random() + 0.25,
  });
}

// Parameters.
const columnCount = 10;
const thumbnailWidth = 100;
const interstitialHeight = 10;

// Algorithm begins. Initialize empty columns.
let columns = [];
let columnHeights = [];
for (let j = 0; j < columnCount; ++j) {
  // This height will be correct once the column is nonempty.
  columnHeights.push(-interstitialHeight);
  columns.push([]);
}

// Sort the images by aspect ratio descending.
function aspectRatioDescending(a, b) {
  return b.height / b.width - a.height / a.width;
}
images.sort(aspectRatioDescending);

// Assign each image to a column.
for (const image of images) {
  // Find the shortest column.
  let shortest = 0;
  for (let j = 1; j < columnCount; ++j) {
    if (columnHeights[j] < columnHeights[shortest]) {
      shortest = j;
    }
  }
  // Put the image there.
  columnHeights[shortest] +=
    interstitialHeight + thumbnailWidth * (image.height / image.width);
  columns[shortest].push(image);
}

// Shuffle the columns for aesthetic reasons.
for (const column of columns) {
  for (let k = 1; k < column.length; ++k) {
    const i = Math.floor((k + 1) * Math.random());
    let temp = column[i];
    column[i] = column[k];
    column[k] = temp;
  }
}

const maxHeight = Math.max.apply(null, columnHeights);
const minHeight = Math.min.apply(null, columnHeights);
// Analyze the layout.
console.log(
  "// The tallest column is %f%% taller than the shortest.",
  (100 * (maxHeight - minHeight)) / minHeight
);
// The tallest column is 3.030982959129835% taller than the shortest.