如果我有一组可以是任意数字的图块（正方形）并且它们要填充未知大小的容器（矩形），我如何计算出图块的最大尺寸而不使它们重叠。
因此，如果我有 2 个图块且矩形为 100 * 100，则最大图块大小为 50 * 50。如果这种大小的矩形有 3 或 4 个图块，这也将是图块的最大尺寸，恰好如此在这个例子中是一个正方形。
如果矩形是 100 * 30 并且我有 2 个图块，则正方形的最大尺寸为 30 * 30，如果我有 4 个图块，则最大尺寸为 25 * 25。
我怎样才能以编程方式做到这一点，而不会通过所有可能的组合来占用处理器。
我尝试更好地总结一下，我有一个：
矩形/边界框，我需要尽可能多地填充而不使瓷砖重叠。
我知道矩形的高度和宽度（但这可以在运行时改变）。
我有 X 个图块（这可以在运行时更改），这些是正方形。
任何瓦片都不应重叠，每个瓦片的最大尺寸是多少。它们都应具有相同的尺寸。
这是一个包装问题。很难找到最佳解决方案。参见例如Packing N 个 squares in a square。
您可以通过将总表面除以平方数来计算（乐观）上限：sqrt(width*height/n)。
从概念上讲：
伪代码：给定 M x N 个矩形以填充 K 个正方形
// initial candidate grid within the rectangle
h=1
w=1
maxsquares=1
size=min(M,N) //size of the squares
while K > maxsquares
if M/(h+1) >= N/(w+1)
h=h+1
else
w=w+1
endif
maxsquares=h*w
size=min(M/h,N/w)
done
print size
可能有更快的方法可以跳到非常大的 K 的答案，但我想不出它们。如果您知道 M 和 N 是整数，那么可能会有更快的方法。
这是一个没有循环的 O(1) 解决方案。
使用矩形的纵横比（高度/宽度），您可以初步猜测 x 和 y 方向上的瓦片数量。这给出了瓷砖总数的上限和下限：在 xy 和 (x+1)(y+1) 之间。
基于这些界限，存在三种可能性：
int GetTileSize(int width, int height, int tileCount)
{
// quick bailout for invalid input
if (width*height < tileCount) { return 0; }
// come up with an initial guess
double aspect = (double)height/width;
double xf = sqrtf(tileCount/aspect);
double yf = xf*aspect;
int x = max(1.0, floor(xf));
int y = max(1.0, floor(yf));
int x_size = floor((double)width/x);
int y_size = floor((double)height/y);
int tileSize = min(x_size, y_size);
// test our guess:
x = floor((double)width/tileSize);
y = floor((double)height/tileSize);
if (x*y < tileCount) // we guessed too high
{
if (((x+1)*y < tileCount) && (x*(y+1) < tileCount))
{
// case 2: the upper bound is correct
// compute the tileSize that will
// result in (x+1)*(y+1) tiles
x_size = floor((double)width/(x+1));
y_size = floor((double)height/(y+1));
tileSize = min(x_size, y_size);
}
else
{
// case 3: solve an equation to determine
// the final x and y dimensions
// and then compute the tileSize
// that results in those dimensions
int test_x = ceil((double)tileCount/y);
int test_y = ceil((double)tileCount/x);
x_size = min(floor((double)width/test_x), floor((double)height/y));
y_size = min(floor((double)width/x), floor((double)height/test_y));
tileSize = max(x_size, y_size);
}
}
return tileSize;
}
我已经使用以下代码针对 1 到 1000 之间的所有整数宽度、高度和 tileCounts 测试了此函数：
for (width = 1 to 1000)
{
for (height = 1 to 1000)
{
for (tileCount = 1 to 1000)
{
tileSize = GetTileSize(width, height, tileCount);
// verify that increasing the tileSize by one
// will result in too few tiles
x = floor((double)width/(tileSize+1));
y = floor((double)height/(tileSize+1));
assert(x*y < tileCount);
// verify that the computed tileSize actually
// results in the correct tileCount
if (tileSize > 0)
{
x = floor((double)width/tileSize);
y = floor((double)height/tileSize);
assert(x*y >= tileCount);
}
}
}
}
我设法想出了一个“相对”的最佳解决方案。部分基于 Zac 的伪代码答案。
//total number of tiles
var tile_count : Number = numberOfSlides;
//height of rectangle
var b : Number = unscaledHeight;
//width of rectanlge
var a : Number = unscaledWidth;
//divide the area but the number of tiles to get the max area a tile could cover
//this optimal size for a tile will more often than not make the tiles overlap, but
//a tile can never be bigger than this size
var maxSize : Number = Math.sqrt((b * a) / tile_count);
//find the number of whole tiles that can fit into the height
var numberOfPossibleWholeTilesH : Number = Math.floor(b / maxSize);
//find the number of whole tiles that can fit into the width
var numberOfPossibleWholeTilesW : Number = Math.floor(a / maxSize);
//works out how many whole tiles this configuration can hold
var total : Number = numberOfPossibleWholeTilesH * numberOfPossibleWholeTilesW;
//if the number of number of whole tiles that the max size tile ends up with is less than the require number of
//tiles, make the maxSize smaller and recaluate
while(total < tile_count){
maxSize--;
numberOfPossibleWholeTilesH = Math.floor(b / maxSize);
numberOfPossibleWholeTilesW = Math.floor(a / maxSize);
total = numberOfPossibleWholeTilesH * numberOfPossibleWholeTilesW;
}
return maxSize;
这样做是计算矩形的总面积，然后将其除以所需的瓷砖数量。由于每个图块都是一个正方形，我可以对它进行 SQRT，以便获得最佳图块的最大尺寸。
有了这个最佳尺寸，我然后检查我可以在宽度和高度中容纳多少个完整的瓷砖。将这些相乘，如果它小于所需的瓷砖数量，那么我会减小最佳尺寸并再次执行检查，直到所有瓷砖都适合矩形。
我可以通过做一些事情来进一步优化这一点，比如每次将最佳尺寸减少 -2 或 -1，然后如果所有瓷砖都适合增加 1，以确保我没有错过有效尺寸。或者我可以跳回超过-2，比如说-10，然后如果它们所有的瓷砖都适合增加5，那么如果不适合减少-2等等，直到我得到最佳配合。
查看http://kennethsutherland.com/flex/stackover/SlideSorterOK.html以获取我的示例。感谢所有各种信息。
以下函数计算给定信息的最大尺寸图块。
如果它是用 Python 编写的这一事实让您难以理解，请在评论中告诉我，我会尝试用其他语言来完成。
import math
from __future__ import division
def max_tile_size(tile_count, rect_size):
"""
Determine the maximum sized tile possible.
Keyword arguments:
tile_count -- Number of tiles to fit
rect_size -- 2-tuple of rectangle size as (width, height)
"""
# If the rectangle is taller than it is wide, reverse its dimensions
if rect_size[0] < rect_size[1]:
rect_size = rect_size[1], rect_size[0]
# Rectangle aspect ratio
rect_ar = rect_size[0] / rect_size[1]
# tiles_max_height is the square root of tile_count, rounded up
tiles_max_height = math.ceil(math.sqrt(tile_count))
best_tile_size = 0
# i in the range [1, tile_max_height], inclusive
for i in range(1, tiles_max_height + 1):
# tiles_used is the arrangement of tiles (width, height)
tiles_used = math.ceil(tile_count / i), i
# tiles_ar is the aspect ratio of this arrangement
tiles_ar = tiles_used[0] / tiles_used[1]
# Calculate the size of each tile
# Tile pattern is flatter than rectangle
if tile_ar > rect_ar:
tile_size = rect_size[0] / tiles_used[0]
# Tile pattern is skinnier than rectangle
else:
tile_size = rect_size[1] / tiles_used[1]
# Check if this is the best answer so far
if tile_size > best_tile_size:
best_tile_size = tile_size
return best_tile_size
print max_tile_size(4, (100, 100))
该算法可以大致描述如下
tiles_max_height（在代码中命名。）这可能是这里列出的更快的算法之一，因为它计算n 个图块的 O(sqrt( n )) 中的最佳平方大小。
更新
进一步考虑，这个问题有一个基于上述解决方案的更简单的解决方案。假设你有 30 个瓷砖。您可能的瓷砖排列很容易计算：
假设你的矩形是 100 x 60。你的矩形的纵横比是 1.6667。这介于 1.2 和 2 之间。现在，您只需计算 8 x 4 和 6 x 5 排列的图块大小。
第一步在技术上仍然需要 O(sqrt( n ))，所以这个更新的方法并不比第一次尝试快。
来自评论线程的一些更新
/*
Changes made:
tiles_used -> tiles_used_columns, tiles_used_rows
(it was originally a 2-tuple in the form (colums, rows))
*/
/* Determine the maximum sized tile possible. */
private function wesleyGetTileSize() : Number {
var tile_count : Number = slideCount.value;
var b : Number = heightOfBox.value;
var a : Number = widthOfBox.value;
var ratio : Number;
// // If the rectangle is taller than it is wide, reverse its dimensions
if (a < b) {
b = widthOfBox.value;
a = heightOfBox.value;
}
// Rectangle aspect ratio
ratio = a / b;
// tiles_max_height is the square root of tile_count, rounded up
var tiles_max_height : Number = Math.ceil(Math.sqrt(tile_count))
var tiles_used_columns : Number;
var tiles_used_rows : Number;
var tiles_ar : Number;
var tile_size : Number;
var best_tile_size : Number = 0;
// i in the range [1, tile_max_height], inclusive
for(var i: Number = 1; i <= tiles_max_height + 1; i++) {
// tiles_used is the arrangement of tiles (width, height)
tiles_used_columns = Math.ceil(tile_count / i);
tiles_used_rows = i;
// tiles_ar is the aspect ratio of this arrangement
tiles_ar = tiles_used_columns / tiles_used_rows;
// Calculate the size of each tile
// Tile pattern is flatter than rectangle
if (tiles_ar > ratio){
tile_size = a / tiles_used[0] ;
}
// Tile pattern is skinnier than rectangle
else {
tile_size = b / tiles_used[1];
}
// Check if this is the best answer so far
if (tile_size > best_tile_size){
best_tile_size = tile_size;
}
}
returnedSize.text = String(best_tile_size);
return best_tile_size;
}
您能否详细说明您如何定义填充？如果我按照您的描述（大如果），您描述的许多情况似乎实际上并没有填充矩形。例如，您说 100*100 矩形中的 2 个正方形将是 50*50。如果我正确理解您的配置，它们将被放置在该矩形的“对角线”上。但是在那个矩形中也会有两个大小为 50*50 的“间隙”。这不是我认为的“填充”矩形。相反，我会将问题描述为边界框为 100*100 的 2 个（相等大小的正方形）的最大可能大小（假设每个正方形必须与至少一个其他正方形接触？）。
这里的关键点是您的矩形似乎是一个边界框并且没有填充。
另外，你能为这个计算写一个功能接口吗？给定边界框的尺寸，您是否需要对 n 个可能的正方形进行此操作？
给定值：
N - number of tiles
a, b - sides of the rectangle
可以使用此函数计算瓷砖的一侧：
def maxSize(n: Int, a: Int, b: Int) = {
var l = 0
for (i <- 1 until a.min(b)) { //
val newL = (a.min(b) / i).min( (a.max(b) * i)/n )
if (l < newL && ((a.min(b)/newL) * (a.max(b)/newL) >= n ) )
l = newL
}
return l
}
我假设你不会制作小于 1x1 的瓷砖，无论 1 的度量是多少
首先你从 0 号开始：
l = 0
然后你从 1 到 K 列的瓷砖迭代
K = min(a, b)
对于每次迭代，使用此公式计算图块的新最大边
val newL = ( a.min(b) / i ).min( (a.max(b) * i)/n )
此公式采用以下两个值中的较小值：
1. min(a, b)/i -- maximum length of a tile if there are i columns in the smaller side of the rectangle
2. (i * max(a, b))/n -- maximum length of a tile if there are i columns and n tiles in the bigger side of the rectangle
如果候选 newL 大于初始值 l 并且可以放置在正方形中而不重叠的最大可能瓷砖数大于或等于瓷砖数 n 则
l = newL
最后返回 l
我假设正方形不能旋转。我很确定如果允许旋转它们，问题就会非常困难。
所以我们从左上角开始用正方形填充矩形。然后我们把正方形放在那个正方形的右边，直到我们到达矩形的右边，然后我们对下一行做同样的事情，直到我们到达底部。这就像在纸上写文字一样。
请注意，永远不会出现右侧和底部留有空间的情况。如果两个方向都有空间，那么我们仍然可以增加正方形的大小。
假设我们已经知道应该在第一行放置 10 个方格，并且这完全符合宽度。那么边长为width/10。所以我们可以m = height/sidelength在第一列中放置正方形。这个公式可以说我们可以在第一列中放置 2.33 个正方形。不可能放置 0.33 个正方形，我们只能放置 2 个正方形。真正的公式是m = floor(height/sidelength)。
一种不是很快（但比尝试每种组合要快很多）的算法是先尝试在第一行/列上放置 1 个正方形，然后看看我们是否可以在矩形中放置足够多的正方形。如果它不起作用，我们会在第一行/列上尝试 2 个方块，等等，直到我们可以满足您想要的瓷砖数量。
如果允许您在 O(1) 中进行算术运算，我认为存在 O(1) 算法，但到目前为止我还没有弄清楚。
这是该算法的 Ruby 版本。如果矩形不是很薄，这个算法是 O(sqrt(# of tiles))。
def squareside(height, width, tiles)
n = 0
while true
n += 1
# case 1: the squares fill the height of the rectangle perfectly with n squares
side = height/n
m = (width/side).floor # the number of squares that fill the width
# we're done if we can place enough squares this way
return side if n*m >= tiles
# case 2: the squares fill the width of the rectangle perfectly with n squares
side = width/n
m = (height/side).floor
return side if n*m >= tiles
end
end
您也可以对这个算法使用二分搜索。在这种情况下，它是 O(log(# of tiles))。
x = max(rectHeight/numberOfSquares, rectangleLength/numberOfSquares)
if x <= retangleHeight && x <= rectangleLength then
squareSideLength = x
else
squareSideLength = min(rectangleHeight, rectangleLength)
将较长的一侧除以瓷砖的数量。使用较短的一侧作为瓷砖尺寸。快！#瓷砖。
Rectagle = 200 x 10
Each tile is 10 x 10 (length of shorter side)
200/10 = 20 (number of tiles needed)