我有 N 个可扩展的正方形图块(按钮)，需要放置在固定大小的矩形表面(工具箱)内。我希望以相同的大小呈现这些按钮。
我应该如何解决图块的最佳大小，以提供被图块覆盖的矩形表面积最大化。
我应该如何解决图块的最佳大小，以提供被图块覆盖的矩形表面积最大化。
用缩放瓦片最大化覆盖矩形区域的算法
10
- Kendall Hopkins
5
您的工具箱在水平和垂直方向上是否有固定大小？您的按钮是否有最小和/或最大尺寸？ - ebynum
@ebynum 是的，X和Y都是预定义的。是的，按钮有最大尺寸，但如果找到的最佳尺寸比最大尺寸要高，我可以只使用最大尺寸（所以在我看来这并不会改变问题）。 - Kendall Hopkins
我想指出的是，如果应用于非矩形多边形形状，这将具有巨大的商业应用。对于制造业来说，“嵌套”形状以实现最大产品密度的产品始终是有需求的。 - Greg Buehler
@entens，你应该说“正方形制造业”。这就像是说解决2-SAT对于SAT有巨大的应用一样。不，一般适用于特殊情况，而不是相反。 - piccolbo
@piccolbo 我在思考如何切割/烧制钢板零件。剩余废料越少，你的利润空间就会越大。像SigmaNEST这样旨在优化切割图案的产品可以极大地提高大多数钢材切割操作的投资回报率。但是，这个原则适用于任何从板材中切割零件的业务。 - Greg Buehler
7个回答
14
设矩形的宽度和高度分别为W和H。
设正方形的边长为s。
那么你可以放入矩形中的正方形数目n(s)为floor(W/s)*floor(H/s)。你想找到最大的s值，使得n(s) >= N。
如果你将正方形数目绘制成关于s的函数图像，你将得到一个分段常数函数。不连续点位于W/i和H/j处，其中i和j分别运行正整数。
你想找到最小的i，使得n(W/i) >= N，以及类似地，最小的j使得n(H/j) >= N。把这些最小值称为i_min和j_min。则W/i_min和H/j_min中的最大值就是你想要的s。
换句话说，s_max = max(W/i_min,H/j_min)
要找出i_min和j_min，只需要进行暴力搜索：对于每个值，从1开始测试并递增。
如果N非常大，从1开始搜索和可能不太好（虽然很难想象它会有任何明显的性能差异）。在这种情况下，我们可以通过以下方式估计起始值。首先，瓷砖面积的大概估计是W*H/N，对应边长为sqrt(W*H/N)。如果W/i <= sqrt(W*H/N)，那么i >= ceil(W*sqrt(N/(W*H)))，类似地，j >= ceil(H*sqrt(N/(W*H)))
因此，我们可以把循环起点改成i = ceil(sqrt(N*W/H)) 和 j = ceil(sqrt(N*H/W)))，而不是从i=1和j=1开始。OP建议使用round而不是ceil——最多增加一次迭代。
以下是C++中展示出的算法：
#include <math.h>
#include <algorithm>
// find optimal (largest) tile size for which
// at least N tiles fit in WxH rectangle
double optimal_size (double W, double H, int N)
{
int i_min, j_min ; // minimum values for which you get at least N tiles
for (int i=round(sqrt(N*W/H)) ; ; i++) {
if (i*floor(H*i/W) >= N) {
i_min = i ;
break ;
}
}
for (int j=round(sqrt(N*H/W)) ; ; j++) {
if (floor(W*j/H)*j >= N) {
j_min = j ;
break ;
}
}
return std::max (W/i_min, H/j_min) ;
}
上面的代码是为了更清晰易懂而编写的。可以按照以下方式大大简化代码：
double optimal_size (double W, double H, int N)
{
int i,j ;
for (i = round(sqrt(N*W/H)) ; i*floor(H*i/W) < N ; i++){}
for (j = round(sqrt(N*H/W)) ; floor(W*j/H)*j < N ; j++){}
return std::max (W/i, H/j) ;
}
- brainjam
9
@Kendall，这个解决方案对你不起作用的原因是什么？ - brainjam
@brainjamin，您能为我们运行一个示例吗？如果最优的i与最优的j不同，则s也不同。但是如果W>>H，这显然是这种情况。所以我认为您的方法是矛盾的。 - piccolbo
1@piccolbo，我已经编辑了答案的最后一部分，试图澄清算法...我引入了i_min，j_min，s_max来区分实际的极值。 - brainjam
@brainjam 我希望有一种非暴力解决方案（在某些情况下，
N 可能非常大）。我想我已经想出了一种猜测最佳点的方法。此外，你的解决方案相当幼稚。它实际上并没有做任何比尝试每种可能性然后选择最佳的更多的事情。 - Kendall Hopkins1@Kendall，好的。我已经添加了i和j的起始估计值。在我的有限实验中，我发现这些估计值要么准确，要么偏差为1。 - brainjam
显示剩余4条评论
9
我相信这可以作为一个受限制的最小化问题来解决，需要一些基本的微积分知识。
定义：
a, l -> rectangle sides
k -> number of squares
s -> side of the squares
您需要将函数最小化：
f[s]:= a * l/s^2 - k
受以下限制的约束：
IntegerPart[a/s] IntegerPart[l/s] - k >= 0
s > 0
我编写了一个小的Mathematica函数来完成这个技巧
f[a_, l_, k_] := NMinimize[{a l/s^2 - k ,
IntegerPart[a/s] IntegerPart[l/s] - k >= 0,
s > 0},
{s}]
易于阅读，因为公式与上面相同。
使用此函数，我制作了一个分配6个正方形的表格。
据我所见，结果是正确的。
正如我所说，您可以在环境中使用标准微积分包，也可以开发自己的最小化算法和程序。如果您决定选择最后一种选项，请按铃，我会提供一些好的指针。
希望有所帮助！
编辑
只是为了好玩，我用结果做了一个图。
对于31个瓷砖：
编辑2：特征参数
问题有三个特征参数：
1. 瓷砖的尺寸 2. 瓷砖数量 3. 围合矩形的l/a比率
也许最后一个结果有些令人惊讶，但很容易理解：如果您有一个7x5矩形和6个要放置的瓷砖的问题，在上面的表格中查找，正方形的大小将为2.33。现在，如果您有一个70x50的矩形，显然，所得到的瓷砖将是23.33，与问题等距缩放。
因此，我们可以取这三个参数并构造它们之间的三维图，并最终将曲线与某些更容易计算的函数匹配（例如使用最小二乘法或计算等值区域）。
无论如何，所得到的缩放图是：
- Dr. belisarius
3
目标函数不应该是
a * l - k * s ^ 2吗？以表示最大面积由瓷砖覆盖的原始约束条件？你的目标函数是基于正方形数量，当考虑到正方形数量必须是整数时，可能会变得有些棘手。 - Ricardo Marimon@marimon 你可以两种方式考虑……结果是一样的（程序已经运行过）。 - Dr. belisarius
仅是想到库恩-塔克条件就让我感到头痛！ - Ricardo Marimon
4
我知道这是一个旧的主题，但最近我以一种高效且始终给出正确答案的方式解决了这个问题。它旨在保持给定的长宽比。如果您希望子元素（在本例中为按钮）为正方形，请使用1的长宽比。我目前在几个地方使用此算法，效果很好。
double VerticalScale; // for the vertical scalar: uses the lowbound number of columns
double HorizontalScale;// horizontal scalar: uses the highbound number of columns
double numColumns; // the exact number of columns that would maximize area
double highNumRows; // number of rows calculated using the upper bound columns
double lowNumRows; // number of rows calculated using the lower bound columns
double lowBoundColumns; // floor value of the estimated number of columns found
double highBoundColumns; // ceiling value of the the estimated number of columns found
Size rectangleSize = new Size(); // rectangle size will be used as a default value that is the exact aspect ratio desired.
//
// Aspect Ratio = h / w
// where h is the height of the child and w is the width
//
// the numerator will be the aspect ratio and the denominator will always be one
// if you want it to be square just use an aspect ratio of 1
rectangleSize.Width = desiredAspectRatio;
rectangleSize.Height = 1;
// estimate of the number of columns useing the formula:
// n * W * h
// columns = SquareRoot( ------------- )
// H * w
//
// Where n is the number of items, W is the width of the parent, H is the height of the parent,
// h is the height of the child, and w is the width of the child
numColumns = Math.Sqrt( (numRectangles * rectangleSize.Height * parentSize.Width) / (parentSize.Height * rectangleSize.Width) );
lowBoundColumns = Math.Floor(numColumns);
highBoundColumns = Math.Ceiling(numColumns);
// The number of rows is determined by finding the floor of the number of children divided by the columns
lowNumRows = Math.Ceiling(numRectangles / lowBoundColumns);
highNumRows = Math.Ceiling(numRectangles / highBoundColumns);
// Vertical Scale is what you multiply the vertical size of the child to find the expected area if you were to find
// the size of the rectangle by maximizing by rows
//
// H
// Vertical Scale = ----------
// R * h
//
// Where H is the height of the parent, R is the number of rows, and h is the height of the child
//
VerticalScale = parentSize.Height / lowNumRows * rectangleSize.Height;
//Horizontal Scale is what you multiply the horizintale size of the child to find the expected area if you were to find
// the size of the rectangle by maximizing by columns
//
// W
// Vertical Scale = ----------
// c * w
//
//Where W is the width of the parent, c is the number of columns, and w is the width of the child
HorizontalScale = parentSize.Width / (highBoundColumns * rectangleSize.Width);
// The Max areas are what is used to determine if we should maximize over rows or columns
// The areas are found by multiplying the scale by the appropriate height or width and finding the area after the scale
//
// Horizontal Area = Sh * w * ( (Sh * w) / A )
//
// where Sh is the horizontal scale, w is the width of the child, and A is the aspect ratio of the child
//
double MaxHorizontalArea = (HorizontalScale * rectangleSize.Width) * ((HorizontalScale * rectangleSize.Width) / desiredAspectRatio);
//
//
// Vertical Area = Sv * h * (Sv * h) * A
// Where Sv isthe vertical scale, h is the height of the child, and A is the aspect ratio of the child
//
double MaxVerticalArea = (VerticalScale * rectangleSize.Height) * ((VerticalScale * rectangleSize.Height) * desiredAspectRatio);
if (MaxHorizontalArea >= MaxVerticalArea ) // the horizontal are is greater than the max area then we maximize by columns
{
// the width is determined by dividing the parent's width by the estimated number of columns
// this calculation will work for NEARLY all of the horizontal cases with only a few exceptions
newSize.Width = parentSize.Width / highBoundColumns; // we use highBoundColumns because that's what is used for the Horizontal
newSize.Height = newSize.Width / desiredAspectRatio; // A = w/h or h= w/A
// In the cases that is doesnt work it is because the height of the new items is greater than the
// height of the parents. this only happens when transitioning to putting all the objects into
// only one row
if (newSize.Height * Math.Ceiling(numRectangles / highBoundColumns) > parentSize.Height)
{
//in this case the best solution is usually to maximize by rows instead
double newHeight = parentSize.Height / highNumRows;
double newWidth = newHeight * desiredAspectRatio;
// However this doesn't always work because in one specific case the number of rows is more than actually needed
// and the width of the objects end up being smaller than the size of the parent because we don't have enough
// columns
if (newWidth * numRectangles < parentSize.Width)
{
//When this is the case the best idea is to maximize over columns again but increment the columns by one
//This takes care of it for most cases for when this happens.
newWidth = parentSize.Width / Math.Ceiling(numColumns++);
newHeight = newWidth / desiredAspectRatio;
// in order to make sure the rectangles don't go over bounds we
// increment the number of columns until it is under bounds again.
while (newWidth * numRectangles > parentSize.Width)
{
newWidth = parentSize.Width / Math.Ceiling(numColumns++);
newHeight = newWidth / desiredAspectRatio;
}
// however after doing this it is possible to have the height too small.
// this will only happen if there is one row of objects. so the solution is to make the objects'
// height equal to the height of their parent
if (newHeight > parentSize.Height)
{
newHeight = parentSize.Height;
newWidth = newHeight * desiredAspectRatio;
}
}
// if we have a lot of added items occaisionally the previous checks will come very close to maximizing both columns and rows
// what happens in this case is that neither end up maximized
// because we don't know what set of rows and columns were used to get us to where we are
// we must recalculate them with the current measurements
double currentCols = Math.Floor(parentSize.Width / newWidth);
double currentRows = Math.Ceiling(numRectangles/currentCols);
// now we check and see if neither the rows or columns are maximized
if ( (newWidth * currentCols ) < parentSize.Width && ( newHeight * Math.Ceiling(numRectangles/currentCols) ) < parentSize.Height)
{
// maximize by columns first
newWidth = parentSize.Width / currentCols;
newHeight = newSize.Width / desiredAspectRatio;
// if the columns are over their bounds, then maximized by the columns instead
if (newHeight * Math.Ceiling(numRectangles / currentCols) > parentSize.Height)
{
newHeight = parentSize.Height / currentRows;
newWidth = newHeight * desiredAspectRatio;
}
}
// finally we have the height of the objects as maximized using columns
newSize.Height = newHeight;
newSize.Width = newWidth;
}
}
else
{
//Here we use the vertical scale. We determine the height of the objects based upong
// the estimated number of rows.
// This work for all known cases
newSize.Height = parentSize.Height / lowNumRows;
newSize.Width = newSize.Height * desiredAspectRatio;
}
在算法的结尾处，“newSize”保存了适当的大小。这是用C#编写的，但将其移植到其他语言应该相对容易。
- Shawn
2
你可以在这里看到我代码的完整解释：
http://www.codeproject.com/KB/recipes/TileScalingCode.aspx - Shawn
谢谢！请问如何在矩形子元素之间添加填充/边距/间隔？ - Nemi
0
第一个非常粗略的启发式方法是采用
s = floor( sqrt( (X x Y) / N) )
其中s是按钮的边长，X和Y是工具箱的宽度和高度，N是按钮的数量。
在这种情况下，s将是最大可能的边长。然而，将此按钮集映射到工具栏上并不一定可行。
想象一个带有5个按钮的20 x 1单位大小的工具栏。启发式算法会给出2的边长（面积为4），覆盖总面积为20。但是，每个按钮的一半都将超出工具栏范围。
- ebynum
0
我会采用迭代的方法。
首先，我会检查是否可能将所有按钮放在一行中。
如果不行，就检查是否可以分成两行等等。
假设 W 是工具箱的较小边，H 是另一边。
对于每次迭代，我会按顺序检查最佳和最差情况。最佳情况是指，在第 n 次迭代中，尝试大小为 W/n X W/n 的按钮。如果 h 值足够，则完成。如果不行，则最坏情况是尝试 (W/(n+1))+1 X (W/(n+1))+1 大小的按钮。如果可以放置所有按钮，则我会在 W/n 和 (W/(n+1))+1 之间尝试二分法。如果不能，则迭代继续在 n+1 进行。
- tafa
0
令n(s)为可以容纳的正方形数量，s为它们的边长。让W、H为要填充的矩形的边长。那么n(s)=floor(W/s)* floor(H/s)。这是一个单调递减的函数，也是分段常数函数，因此您可以对二分搜索进行轻微修改，以找到最小的s，使得n(s) >= N但n(s+eps) < N。您从上限和下限开始搜索s，u = min(W, H)和l = floor(min(W,H)/N)，然后计算t = (u + l) / 2。如果n(t) >= N，则l = min(W/floor(W/t), H/floor(H/t))，否则u = max(W/floor(W/t), H/floor(H/t))。当u和l在连续迭代中保持不变时停止搜索。所以这就像二分搜索，但您利用了函数是分段常数函数且更改点是W或H是s的精确倍数的事实。很好的问题，感谢您提出。
- piccolbo
0
我们知道任何最优解（可能有两个）都会横向或纵向填充矩形。如果您找到了一个未在一个维度上填充矩形的最优解，您可以始终增加瓷砖的比例来填充一个维度。
现在，任何最大化覆盖面积的解决方案都将具有接近矩形长宽比的纵横比。解决方案的纵横比是垂直瓷砖数/水平瓷砖数（而矩形的长宽比是Y/X）。
您可以通过强制Y>=X来简化问题；换句话说，如果X>Y，请转置矩形。这样，只要记得将解决方案转置回来，就可以仅考虑纵横比>=1。
一旦计算出宽高比，您需要找到解决方案来解决 V/H ~= Y/X 的问题，其中 V 是垂直瓷砖数，H 是水平瓷砖数。您将找到最多三个解决方案：最接近 Y/X 和 V+1，V-1 的最接近的 V/H。此时，只需根据比例使用 V 和 H 计算覆盖范围并取最大值（可能会有多个）。
- MSN
3
你的初始陈述是不正确的。如果我有4个瓷砖和一个5x5的表面，我的最佳正方形尺寸将是2x2，覆盖了5x5中的4x4总面积，对吗？3x3的正方形（每个9个）将覆盖36个单位，而表面仅有25个单位。 - ebynum
@ebynum，我的假设是比例尺不是整数。如果它们是整数，那么我不知道我的解决方案是否最优。如果它们不是整数，那么我的解决方案是最优的。 - MSN
据我理解，问题在于这些瓷砖不是整数，因为它们是工具箱上的按钮。好吧，也许它们实际上是整数（像素），但由于像素大小可以被认为比工具箱大小小得多，所以问题是连续的（即在R中）。 - Dr. belisarius
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接