固定サイズの長方形の面 (ツールボックス) 内に配置する必要が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は正の整数を通過します。
which の最小値を検索し、同様に、iwhichの最小値を検索します。これらの最小値を および と呼びます。次に、 andの最大のものは、必要な です。n(W/i) >= Njn(H/j) >= Ni_minj_minW/i_minH/j_mins
いえs_max = max(W/i_min,H/j_min)
とを見つけるi_minにj_minは、ブルート フォース検索を実行するだけです。それぞれについて、1 から開始し、テストし、インクリメントします。
iN が非常に大きい場合、 と を 1 から検索するのは不愉快かもしれません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)))
したがって、 と でループを開始するのではなく、i=1とでループをj=1開始できます。そしてOPは、最悪の場合、余分な反復よりもうまく機能することを示唆しています。i = 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: 特性パラメータ
この問題には、次の 3 つの特徴的なパラメーターがあります。
- タイルの結果サイズ
- タイルの数
- 囲んでいる長方形の比 l/a
最後の結果は少し驚くかもしれませんが、簡単に理解できます: 7x5 の長方形と 6 つのタイルの配置に問題がある場合、上記の表を見ると、正方形のサイズは 2.33 になります。ここで、70x50 の長方形がある場合、明らかに、結果のタイルは 23.33 になり、問題で等角的にスケーリングされます。
したがって、これらの 3 つのパラメーターを取得して、それらの関係の 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
最適解 (2 つある場合もあります) は、長方形を水平方向または垂直方向に塗りつぶすことがわかっています。四角形を 1 次元で埋めない最適解が見つかった場合は、いつでもタイルのスケールを大きくして 1 次元を埋めることができます。
ここで、カバーされる表面を最大化するソリューションは、長方形の縦横比に近い縦横比を持ちます。解の縦横比は ですvertical tile count/horizontal tile count(長方形の縦横比は ですY/X)。
強制することで問題を単純化できY>=Xます。つまり、 の場合X>Y、長方形を転置します。これにより、ソリューションを元に戻すことを覚えている限り、アスペクト比 >= 1 についてのみ考えることができます。
アスペクト比を計算したら、V/H ~= Y/XはV垂直方向のタイル数、Hは水平方向のタイル数です。とに最もV/H近い解を最大 3 つ見つけることができます。その時点で、 と を使用してスケールに基づいてカバレッジを計算し、最大値を取得します (複数ある可能性があります)。Y/XV+1V-1VH
于 2010-10-12T18:14:36.403 に答える
0
収まる正方形の数を n(s) とし、その辺を s とします。塗りつぶす長方形の辺を W、H とします。次に、n(s) = フロア(W/s)*フロア(H/s)。これは s の単調減少関数であり、区分定数でもあるため、二分探索をわずかに変更して、n(s) >= N で n(s+eps) < N となるような最小の s を見つけることができます。 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 に答える