我有N需要放置在固定大小的矩形表面（工具箱）内的可缩放方形瓷砖（按钮）。我想以相同的大小呈现所有按钮。
我怎样才能解决瓷砖的最佳尺寸，以提供被瓷砖覆盖的矩形表面的最大面积。
问问题
4024 次
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你想要的。
IEs_max = max(W/i_min,H/j_min)
要找到i_minand j_min，只需进行蛮力搜索：对于每个，从 1 开始，测试并递增。
如果 N 非常大，从 1 开始搜索i' 和j' 可能会令人反感（尽管很难想象性能会有任何明显的差异）。在这种情况下，我们可以如下估计起始值。首先，瓷砖面积的大致估计是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)))
因此，我们可以从and开始，而不是从 and 开始i=1循环。并且 OP 建议这比- 在最坏的情况下额外的迭代更好。j=1i = ceil(sqrt(N*W/H))j = ceil(sqrt(N*H/W)))roundceil
这是用 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) ;
}
于 2010-10-05T01:45:26.207 回答
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：特征参数
该问题具有三个特征参数：
- 瓷砖的最终尺寸
- 瓷砖数量
- 包围矩形的比率 l/a
也许最后一个结果可能有点令人惊讶，但很容易理解：如果您对 7x5 矩形和 6 个瓷砖放置有问题，查看上表，正方形的大小将为 2.33。现在，如果您有一个 70x50 的矩形，显然生成的图块将是 23.33，与问题等距缩放。
因此，我们可以采用这三个参数并构建它们关系的 3D 图，并最终将曲线与一些更易于计算的函数匹配（例如使用最小二乘法或计算等值区域）。
无论如何，生成的缩放图是：
于 2010-10-12T18:59:41.437 回答
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# 编写的，但很容易移植到其他语言。
于 2011-06-28T14:46:46.527 回答
0
第一个非常粗略的启发式方法是采取
s = floor( sqrt( (X x Y) / N) )
其中s是按钮边长，X是Y工具箱的宽度和高度，N是按钮数。
在这种情况下，s将是最大可能的边长。但是，不一定可以将这组按钮映射到工具栏上。
想象一个工具栏，它是 20 个单位乘 1 个单位，有 5 个按钮。启发式将为您提供 2 的边长（面积为 4），总覆盖面积为 20。但是，每个按钮的一半将在工具栏之外。
于 2010-10-04T23:39:00.630 回答
0
我会在这里采用迭代方法。我会检查是否可以将所有按钮放在一行中。如果不是，请检查是否可以放入两行，依此类推。
假设 W 是工具箱中较小的一侧。H是另一边。
对于每次迭代，我都会按顺序检查可能的最佳和最坏情况。最好的情况意味着，假设它是第 n 次迭代，将尝试 W/n XW/n 大小的按钮。如果 h 值足够，那么我们就完成了。如果不是，最坏的情况是尝试 (W/(n+1))+1 X (W/(n+1))+1 大小的按钮。如果可以安装所有按钮，那么我会尝试 W/n 和 (W/(n+1))+1 之间的二等分法。如果不是，迭代在 n+1 处继续。
于 2010-10-05T00:06:40.767 回答
0
让 n(s) 是可以适合和 s 边的正方形的数量。令 W, H 为要填充的矩形的边。那么 n(s) = floor(W/s)* floor(H/s)。这是 s 中的单调递减函数，也是分段常数，因此您可以对二进制搜索进行轻微修改以找到最小的 s，使得 n(s) >= N 但 n(s+eps) < N。您从su = 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 的精确倍数时变化点。不错的小问题，谢谢提出。
于 2010-10-11T03:54:02.510 回答
0
我们知道任何最优解（可能有两个）都会水平或垂直填充矩形。如果您找到了一个未填充一维矩形的最佳解决方案，您始终可以增加图块的比例以填充一维。
现在，任何最大化覆盖表面的解决方案都将具有接近矩形纵横比的纵横比。解的纵横比是vertical tile count/horizontal tile count（矩形的纵横比是Y/X）。
您可以通过强制来简化问题Y>=X；换句话说，如果X>Y，则转置矩形。这允许您只考虑纵横比 >= 1，只要您记得将解决方案转回即可。
一旦你计算了纵横比，你想找到问题的解决方案V/H ~= Y/X，其中V是垂直瓦片数，H是水平瓦片数。您将找到最多三个解决方案：V/H最接近Y/X和V+1，V-1。此时，只需使用V和计算基于比例的覆盖率H并取最大值（可能不止一个）。
于 2010-10-12T18:14:36.403 回答