README

RectanglePacker 是一个JavaScript/PHP类，旨在高效地将具有相同宽高比的矩形放入定义的空间中，使用启发式算法解决NP难的箱装问题。有关此问题的更多信息，请参阅维基百科。此启发式算法解决了文章中列出的第二种变体，即 在矩形多边形中装箱相同的正方形。

定义问题

我设计了此算法，目的是最大限度地 填充 不同屏幕区域内的水平和垂直空间，使用只有宽高比已知且视频数量可变的瓦片网格。在我的用例中，宽高比是4/5。

CSS布局算法

我无法通过浏览器布局算法如css flexbox 或 grid 实现所需的效果。我也无法同时垂直和水平填充容器，而不需要为flex/grid-item显式设置高度/宽度值或使用javascript来纠正布局（虽然我很乐意看到有人证明我是错的！）。无论如何，我需要一个可以在服务器端工作的实现，而不是客户端。

在线尝试算法可视化器

如果您想尝试此算法，您可以在网上找到一个测试应用程序，该应用程序可视化了包装器的工作过程：https://aslamhus.github.io/RectanglePacker/example

尝试不同的屏幕区域、瓦片数量、间距大小、瓦片宽高比等。

用法

此类可在 JavaScript 和 PHP 中使用，适用于客户端和服务器端实现。

JavaScript

克隆仓库并从src目录导入。如果需要，我将将其作为npm包提供。

克隆仓库

git clone https://github.com/aslamhus/RectanglePacker.git

导入和使用

import RectanglePacker from '../RectanglePacker/src/RectanglePacker.js';

const packer = new RectanglePacker({
  screenArea: [480, 480],
  tiles: [1, 2, 3, 4, 5],
  tileAspectRatio: 4 / 5,
});
const result = packer.pack();

PHP

使用composer安装

composer require aslamhus/rectpacker

使用

$rectPacker = new Aslamhus\RectPacker\RectPacker([
  'screenArea' => [480,480],
  'tiles' => [1,2,3,4,5],
  'tileAspectRatio' => 4/5
])
$result = $rectPacker->pack();

结果

启发式算法输出网格中每个瓦片的(x,y) 位置，您可以根据其中的坐标排列您的网格。如果成功，启发式算法的结果将是一个对象（在PHP类中是一个关联数组），包含以下键

const {
  tileWidth : 0, // the width of each tile (excluding gutter)
  tileHeight: 0, // the height of each tile (excluding the gutter)
  columns: 0, // the grid columns
  rows: 0, // the grid rows
  realWidth: 0 // the width of the grid (including gutter)
   realHeight: 0, // the height of the grid  (including gutter)
  positions: [], // an array of positions corresponding to the tiles array you gave in the constructor. Each tile has an (x,y) coordinate according to its position in the grid
  tiles: [], // the original tiles array you supplied in the constructor
  tries : [], // an array with data for each iteration of the packer providing granular analysis of the heuristic
} = result;

如果失败，RectanglePacker 将引发错误。

选项

可以通过以下选项配置 RectanglePacker 算法的行为，这些选项可以在初始化 RectanglePacker 实例时设置，或者可以通过调用 setOptions 方法重新初始化算法。以下是每个可配置选项的详细说明

必需参数

screenArea

• 描述：指定需要装箱的矩形屏幕区域的尺寸。
• 类型：表示宽度和高度的数字数组。

tiles

• 描述：表示每个瓦片源的字符串数组。
• 类型：字符串数组。

tileAspectRatio

• 描述：瓦片的固定宽高比。
• 类型：数字。

约束（可选）

gutter

• 描述：瓦片之间的间距。
• 类型：数字。
• 默认值 0.

minTileWidth

• 描述：每个瓦片的最小宽度。
• 类型：数字。
• 默认值 0.

minTileHeight

• 描述：每个瓦片的最小高度。
• 类型：数字。
• 默认值 0.

maxTileHeight

• 描述：每个瓦片的最大高度。
• 类型：数字。
• 默认值 0.

columns

• 描述: 列数固定。如果设置了，则基于列数计算瓦片高度的最好猜测。
• 类型：数字。
• 默认值 0.

allowIncompleteRow

• 描述: 如果设置为true，则启发式算法将允许在不满足列数约束的情况下存在不完整的行。例如，如果您指定瓦片应按8列排列以适应屏幕区域，但实际上只有3个瓦片，则allowIncompleteRow将按水平方向排列瓦片，就好像有足够的瓦片来遵守列数约束一样。如果没有allowIncompleteRow，则算法将抛出无法满足列数约束或屏幕宽度下溢错误/异常。
• 类型: 布尔型。
• 默认值: false。

completeRectangle

• 描述: 如果设置为true，则启发式算法将尝试使矩形完整，即所有行都将填满。
• 类型: 布尔型。
• 默认值: false。

canRemoveTiles

• 描述: 如果设置为true，则当解决方案不可行时将删除瓦片。
• 类型: 布尔型。
• 默认值: false。

tryLimit

• 描述: 启发式算法放弃前的最大尝试次数。
• 类型：数字。
• 默认值 800.

errorMargin

• 描述: 瓦片尺寸的错误范围。
• 类型：数字。
• 默认值 0.01.

performanceLimit

• 描述: 性能的毫秒限制。
• 类型：数字。
• 默认值 1000.

debug

• 描述: 如果设置为true，则将调试信息记录到控制台。
• 类型: 布尔型。
• 默认值: false。

回调选项

onError

• 描述: 处理错误的回调函数。它接收一个错误消息作为参数。
• 类型: 函数。
• 默认值: null。

示例

const options = {
  screenArea: [800, 600],
  tiles: ['tile1.jpg', 'tile2.jpg', 'tile3.jpg'],
  tileAspectRatio: 0.75,
  gutter: 5,
  columns: 0, // 0 means no fixed columns
  allowIncompleteRow: false,
  completeRectangle: false,
  canRemoveTiles: false,
  tryLimit: 800,
  errorMargin: 0.01,
  performanceLimit: 1000,
  debug: false,
  onError: (error) => console.error(error),
};

const packer = new RectanglePacker(options);
const result = packer.pack();
console.log(result);

效率

尽管我没有广泛测量算法的时间复杂度，但大多数情况都在1-4毫秒和1-10次迭代内解决。随着您添加更多约束，时间复杂度会增加。当我有时间时（哈哈！），我很乐意更精确地测量这一点。欢迎提供反馈/观察！

潜在改进

元启发式

多次运行启发式算法，每次使用不同的初始最佳猜测，如果需要，可以利用Web Workers提高效率。开发一种方法来衡量解决方案的可行性，其中剩余空间是主要标准。

单元测试

RectanglePacker存储库包含一个包含测试值的json文件，每个测试值都有一个预期的输出。您可以使用这些测试值测试算法的PHP和JavaScript实现。

PHPUnit测试

composer run test-rect-packer

JavaScript测试

npm run test

关于接缝精度和浏览器子像素舍入的说明

在测试应用程序中，接缝可能偏移一个或两个像素。这是因为浏览器舍入像素值。如果接缝很小，并且每个瓦片宽度都向上或向下舍入（取决于您的浏览器），则每行末尾的接缝将看起来被截断。这是一个已知问题，不是算法的bug。您可以在打包器的结果中检查瓦片位置，以确认接缝值是正确的。将来，我将尝试在算法的JavaScript实现中考虑这个问题。

许可

此矩形打包类根据MIT许可许可。请随意根据您的需求使用和修改它。

祝打包愉快！！