希望在更大的矩形中生成一些矩形的随机网格。
这看起来是一个相当容易的问题，但事实并非如此，在这里寻求建议。
这不是打包问题，因为内部矩形可以具有任何宽度和高度。
但是矩形的数量并不总是相同的。
我已经有一些不同类型的循环的结果，但没有一个是真正有效的。
例如，对于15 个矩形，表示它们的可能方法是：
O 10 50 60
+----------+---------------------------------------------+----------+-------+
| | | | |
| | | | |
| | | | |
5 +----------+---------------------------------------------+----------+-------+
| | | |
| | | |
| | | |
| | | |
| | | |
| | | |
15+----------+---------------------------------------------+----------+-------+
| | | | |
| | | | |
| | | | |
+----------+---------------------------------------------+----------+-------+
| | | | |
| | | | |
| | ↓ | | |
+----------+---------------------------------------------+----------+-------+
然后，坐标将类似于每个内部方块的左上角(+(的[x，y]点数组：
[[0,0],[10,0],[50,0],[60,0],[5,0],[5,10],[5,50], ...]
甚至更好的是[x，y，w，h]值数组(左上角 x、左上角 y、宽度、高度(
[[0,0,10,5],[10,0,40,5],[50,0,10,5],[60,0,10,5],[5,0,10,10],[5,10,40,10],[5,50,20,10], ...]
但目标是创建一个函数，为任意数量的内平方生成坐标：
例如，对于14 个矩形，表示它们的可能方法是：
+----------+----------------------------------+---------------------+-------+
| | | | |
| | | | |
| | | | |
| | | | |
| | | | |
+----------+----------------------------------+----------+----------+-------+
| | | | |
| | | | |
+----------+--------+------------------------------------+----------+-------+
| | | | |
| | | | |
+-------------------+-----------+------------------------+----------+-------+
| | |
| | |
| | |
| | |
+-------------------------------+-----------------------------------+-------+
相关链接：
将矩形图像数据打包为方形纹理
可以使用什么算法以相当优化的方式将不同大小的矩形打包成最小的矩形？
如何排列 N 个矩形以覆盖最小面积
您的问题有两个方面：您希望创建一个具有n个可能跨越多个单元格的矩形的常规网格，并且您希望随机分布单元格边框的坐标。
所以我提出了愚弄算法：
- 确定网格中的行数和列数，以便每个单元格或多或少是方形的。
- 创建一个包含 1×1 个单元格的矩形网格。单元格数将大于n。
- 合并两个相邻的单元格，直到有n个单元格。
- 现在为单元格边界创建随机轴。如果有m列，请创建一个递减值数组，以便第一个坐标为 0，最后一个坐标为原始角的宽度。为此，您可以创建一个递增随机数的列表，然后使用总宽度进行规范化。
- 最后，使用单元格(位置、单元格跨度(和随机轴的信息创建实际矩形。
此算法使用矩形的两种表示形式：首先，它创建"单元格"，其中包含有关其行和列索引以及跨度的信息。实际输出是带有左侧、顶部、宽度和高度信息的矩形。
我不熟悉PHP，所以这里有一个Javascript的实现。我想你可以看到它是如何工作的：
function tile(big, n) {
// big: outer rectangle
// n: number of subrectangles to create
// determine number of rows and cols
let l = Math.sqrt(big.height * big.width / n);
let ncol = (big.width / l + 1) | 0;
let nrow = (big.height / l + 1) | 0;
let cells = [];
// create grid of m*m cells
for (let j = 0; j < nrow; j++) {
for (let i = 0; i < ncol; i++) {
cells.push(new Cell(i, j, 1, 1));
}
}
// conflate rectangles until target number is reached
while (cells.length > n) {
let k = (cells.length * Math.random()) | 0;
let c = cells[k];
if (c.col + c.colspan < ncol) {
let cc = cells[k + 1];
c.colspan += cc.colspan;
cells.splice(k + 1, 1);
}
}
// generate increasing lists of random numbers
let xx = [0];
let yy = [0];
for (let i = 0; i < ncol; i++) {
xx.push(xx[xx.length - 1] + 0.5 + Math.random());
}
for (let i = 0; i < nrow; i++) {
yy.push(yy[yy.length - 1] + 0.5 + Math.random());
}
// fit numbers to outer rectangle
for (let i = 0; i < ncol; i++) {
xx[i + 1] = (big.width * xx[i + 1] / xx[ncol]) | 0;
}
for (let i = 0; i < nrow; i++) {
yy[i + 1] = (big.height * yy[i + 1] / yy[nrow]) | 0;
}
// create actual rectangles
let res = [];
for (let cell of cells) {
let x = xx[cell.col];
let w = xx[cell.col + cell.colspan] - x;
let y = yy[cell.row];
let h = yy[cell.row + cell.rowspan] - y;
res.push(new Rect(x, y, w, h));
}
return res;
}
笔记：
- 上面的代码仅水平合并单元格。您可以将其更改为垂直合并单元格或两者兼而有之，但根据目前的算法，如果不进行重大修改，您将无法创建多个单元格宽且高的单元格。
x | 0是将浮点数转换为整数的廉价方法。我已经使用它来将最终坐标捕捉为整数值，但您也可以将它们捕捉到任何网格大小，s在 PHP 中使用s * ((x / s) | 0)或s * intval(x / s)。
代码不太关心美学。它随机选择单元格大小和单元格进行合并，这样您可能会得到交叉关节，这看起来不太好。不过，您可以稍微影响结果的规律性：
- 确定列数和行数时，必须向结果添加一个，以便使单元格在每种情况下都合并。(即使你有一个正方形并将一个正方形数字传递为n，你也会得到连接的矩形。如果添加更多，将获得更多连接的矩形，结果看起来会更不规则。
Math.random()返回一个介于 0 和 1 之间的随机数。创建轴时，我在结果中添加了 0.5，这样您就不会得到非常窄的单元格。如果添加较少，坐标将更加不规则，如果添加更多，它们将分布更均匀。- 也许你可以通过使行坐标均匀并且笨拙坐标不规则来获得良好的效果。
您在评论中提到了好看的属性。当您创建网格并放置带有约束的矩形时，创建美观的结构可能比先创建网格然后重新调整关节更容易。