Алгоритм максимизации покрытия прямоугольной области масштабными плитками

Question

У меня есть N масштабируемые квадратные плитки (кнопки), которые должны быть размещены внутри прямоугольной поверхности фиксированного размера (набор инструментов). Я хотел бы представить все кнопки одинакового размера.

Как я могу выбрать оптимальный размер плиток, который бы обеспечивал наибольшую площадь прямоугольной поверхности, покрытой плитками.

Answer 1

Пусть 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 очень большое, может быть неприятно искать i и j, начиная с 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=1 и j=1, мы можем запустить их с i = ceil(sqrt(N*W/H)) и j = ceil(sqrt(N*H/W))).И 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) ;
}

Answer 2

Я считаю, что это можно решить как ограниченную задачу минимизации, которая требует некоторого базового исчисления.,

Определения:

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 квадратов

, насколько я вижу, результаты верны,

Как я уже сказал, вы можете использовать стандартный пакет исчисления для вашей среды, или вы можете также разработать свой собственный алгоритм и программы минимизации.Позвоните в звонок, если вы выберете последний вариант, и я предоставлю несколько хороших указателей.

HTH!

Редактировать

Просто для удовольствияЯ сделал сюжет с результатами.

И для 31 плитки:

Редактировать 2: Параметры характеристик

Задача имеет три характерных параметра:

1. Итоговый размер плиток
2. Количество плиток
3. Отношение l / a окружающего прямоугольника

Возможно, последнее может несколько удивить, но это легко понять: если у вас есть проблема с прямоугольником 7х5 и размещением 6 плиток, посмотрите в приведенной выше таблице размер квадратовбудет 2,33.Теперь, если у вас есть прямоугольник 70x50, очевидно, что получающиеся плитки будут иметь размер 23,33, масштабируясь изометрически с проблемой.

Итак, мы можем взять эти три параметра и построить трехмерный график их взаимосвязи и в конечном итоге сопоставитькривая с некоторой функцией, которую легче вычислить (например, используя наименьшие квадраты или вычисляя области значений iso).

В любом случае, получающийся масштабированный график будет иметь вид:

Answer 3

Я понимаю, что это старая тема, но недавно я решил эту проблему таким образом, что я считаю эффективным и всегда дает правильный ответ.Он предназначен для поддержания заданного соотношения сторон.Если вы хотите, чтобы дочерние элементы (в данном случае кнопки) были квадратными, просто используйте соотношение сторон 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 #, но было бы довольно легко перенести на другие языки.

Answer 4

Мы знаем, что любое оптимальное решение (может быть два) заполнит прямоугольник либо горизонтально, либо вертикально.Если вы нашли оптимальное решение, которое не заполняло прямоугольник в одном измерении, вы всегда можете увеличить масштаб плиток, чтобы заполнить одно измерение.

Теперь любое решение, которое максимизирует покрытую поверхность, будет иметь соотношение сторон.близко к соотношению сторон прямоугольника.Соотношение сторон решения равно 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, и возьмите максимум (их может быть больше одного).

Answer 5

Позвольте n (s) быть числом квадратов, которые могут соответствовать и их стороне.Пусть W, H - стороны прямоугольника для заполнения.Тогда n (s) = этаж (Вт / с) * этаж (H / с).Это монотонно убывающая функция от s, а также кусочно-постоянная, поэтому вы можете выполнить небольшую модификацию бинарного поиска, чтобы найти самые маленькие s, такие что n (s)> = N, но n (s + eps) = N, то l= min (W / floor (W / t), H / floor (H / t)), в противном случае u = max (W / floor (W / t), H / floor (H / t)).Остановитесь, когда вы и я останетесь прежними в последовательных итерациях.Так что это похоже на бинарный поиск, но вы используете тот факт, что функция является кусочно-постоянной, а точки изменения - это когда W или H являются точным кратным s.Хорошая маленькая проблема, спасибо за предложение.

Answer 6

Я бы выбрал итерационный подход здесь. Я бы проверил, можно ли разместить все кнопки в одном ряду. Если нет, проверьте, можно ли разместить в два ряда и т. Д.

Скажем, 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.

Answer 7

Первая, очень грубая эвристика - взять

s = floor( sqrt( (X x Y) / N) )

, где s - длина стороны кнопки, X и Y - ширина и высота панели инструментов, а N - количество кнопок.

В этом случае s будет МАКСИМАЛЬНОЙ возможной длиной стороны. Однако не обязательно отобразить этот набор кнопок на панель инструментов.

Представьте себе панель инструментов размером 20 на 1 единицу с 5 кнопками. Эвристика даст вам длину стороны 2 (область 4) с общей площадью покрытия 20. Однако половина каждой кнопки будет находиться за пределами панели инструментов.