7

アスペクト比 Aitem (X:Y) の N 個の長方形のアイテムがあります。
縦横比が Aview の長方形の表示領域があります

項目は、表のようなレイアウト (つまり、r 行、c 列) に配置する必要があります。

個々のアイテムが最大になるように、理想的なグリッド行 x 列は何ですか? (行 * 列 >= N、もちろん - つまり、「未使用」のグリッドの場所があるかもしれません)。

単純なアルゴリズムでは、rows = 1..N を反復処理し、必要な列数を計算して、行/列のペアを最大の項目に保つことができます。

ただし、非反復アルゴリズムがあるかどうかは疑問です (たとえば、Aitem = Aview = 1 の場合、rows / cols は sqrt(N) で近似できます)。

4

4 に答える 4

5

注: フレデリックの答えをよく理解できなかったので、自分で問題を解決し、同じ解決策と思われるものを思いつきました。それが役立つ場合に備えて、私が何をしたかを説明したほうがよいと思いました。

最初に、ビューのアスペクト比をアイテムのアスペクト比に正規化しました。（アイテムをローテーションしたくないと仮定しています。）

a = (view_width/view_height) / (item_width/item_height)

幅/高さの比率の長方形aを正方形でパックすることは、ビューをアイテムでパックすることと同じです。理想的なケースは、(現在は正方形の) グリッドが長方形を完全に埋めることです。

a = c/r

ここでr、 とcは行数と列数です。

N = r*c

これらの 2 つの方程式を乗算/除算すると、次のようになります。

N*a = c^2              N/a = r^2
c = sqrt(N*a)          r = sqrt(N/a)

グリッドが完全で整数rにcなる場合は、Frédéric が言及した 3 つのオプションを試して、r*c最小であるが よりも大きいオプションを保持する必要がありNます。

  • floor(r), ceil(c)
  • ceil(r), floor(c)
  • ceil(r), ceil(c)
于 2010-03-19T22:24:09.317 に答える
1

一般的なケースを処理するために、ソリューションを簡単に改善できます。

整数の行と列を持つ必要性を (一時的に) 忘れた場合、次のようになります。

行 * 列 = N

x = 品目 * y

aview = 行 * x = 行 * aitem * y

1 = 列 * y = (N/行) * ( aview / [aitem*rows]) = N * aview /(aitem * 行²)

したがって、rows=sqrt(N *aview/aitem) および columns = N/rows = sqrt(N * aitem / aview)

次に、ceil(rows) と ceil(columns) は解ですが、floor(rows) と floor(columns) は小さすぎて一緒に解にすることはできません (行と列が整数でない場合)。これにより、3 つの可能な解決策が残されます。

  • 床(行) 天井(列)
  • 天井(行) 床(列)
  • ceil(行) ceil(列)

方程式を修正するために編集されました。最初の結果は間違っていました (コメントを参照)

于 2010-03-19T11:29:28.130 に答える
0

良い質問。ビューの寸法が A x B (固定) で、項目の寸法が axb (可変、最大化) の場合、次のものが必要です。

trunc(A / a) * trunc(B / b) >= N

ただし、これを解決する方法がわかりません。切り捨ては非線形であるため、注意が必要です。

于 2010-03-19T11:22:56.213 に答える
0

この質問への回答を得ることができませんでしたが、Neptiloからの同様の質問に対する適切な実装を見つけました。ただし、長方形では機能せず、正方形のみでした。そこで、マッキードのアイデアを適用して長方形を正規化し、次に正方形のアルゴリズムに従いました。

その結果がfitToContainer() 関数です。フィットする四角形の数nとcontainerWidthとcontainerHeight元のitemWidthと を指定しitemHeightます。アイテムに元の幅と高さがない場合は、 と を使用itemWidthしitemHeightて、アイテムの目的の比率を指定します。

たとえば、480 x 270 (ピクセル、または単位が何であれ) の 4 つの列と 3 つの行になりますfitToContainer(10, 1920, 1080, 16, 9)。{nrows: 4, ncols: 3, itemWidth: 480, itemHeight: 270}

fitToContainer(10, 1920, 1080, 1, 1)そして、1920x1080 の同じ例の領域に 10 個の正方形を収めるには、次のように呼び出すことができます{nrows: 2, ncols: 5, itemWidth: 384, itemHeight: 384}。

function fitToContainer(n, containerWidth, containerHeight, itemWidth, itemHeight) {
    // We're not necessarily dealing with squares but rectangles (itemWidth x itemHeight),
    // temporarily compensate the containerWidth to handle as rectangles
    containerWidth = containerWidth * itemHeight / itemWidth;
    // Compute number of rows and columns, and cell size
    var ratio = containerWidth / containerHeight;
    var ncols_float = Math.sqrt(n * ratio);
    var nrows_float = n / ncols_float;

    // Find best option filling the whole height
    var nrows1 = Math.ceil(nrows_float);
    var ncols1 = Math.ceil(n / nrows1);
    while (nrows1 * ratio < ncols1) {
        nrows1++;
        ncols1 = Math.ceil(n / nrows1);
    }
    var cell_size1 = containerHeight / nrows1;

    // Find best option filling the whole width
    var ncols2 = Math.ceil(ncols_float);
    var nrows2 = Math.ceil(n / ncols2);
    while (ncols2 < nrows2 * ratio) {
        ncols2++;
        nrows2 = Math.ceil(n / ncols2);
    }
    var cell_size2 = containerWidth / ncols2;

    // Find the best values
    var nrows, ncols, cell_size;
    if (cell_size1 < cell_size2) {
        nrows = nrows2;
        ncols = ncols2;
        cell_size = cell_size2;
    } else {
        nrows = nrows1;
        ncols = ncols1;
        cell_size = cell_size1;
    }

    // Undo compensation on width, to make squares into desired ratio
    itemWidth = cell_size * itemWidth / itemHeight;
    itemHeight = cell_size;
    return { nrows: nrows, ncols: ncols, itemWidth: itemWidth, itemHeight: itemHeight }
}
于 2019-11-06T16:42:25.167 に答える