Максимальный квадратный размер для неизвестного номера внутри прямоугольника

Ответ 1

Мне удалось найти "относительно" оптимальное решение. Частично основано на ответе псевдокода Zac.

        //total number of tiles
        var tile_count : Number = numberOfSlides;
        //height of rectangle
        var b : Number = unscaledHeight;
        //width of rectanlge
        var a : Number = unscaledWidth;

        //divide the area but the number of tiles to get the max area a tile could cover
        //this optimal size for a tile will more often than not make the tiles overlap, but
        //a tile can never be bigger than this size
        var maxSize : Number = Math.sqrt((b * a) / tile_count);
        //find the number of whole tiles that can fit into the height
        var numberOfPossibleWholeTilesH : Number = Math.floor(b / maxSize);
        //find the number of whole tiles that can fit into the width
        var numberOfPossibleWholeTilesW : Number = Math.floor(a / maxSize);
        //works out how many whole tiles this configuration can hold
        var total : Number = numberOfPossibleWholeTilesH * numberOfPossibleWholeTilesW;

        //if the number of number of whole tiles that the max size tile ends up with is less than the require number of 
        //tiles, make the maxSize smaller and recaluate
        while(total < tile_count){
            maxSize--;
            numberOfPossibleWholeTilesH = Math.floor(b / maxSize);
            numberOfPossibleWholeTilesW = Math.floor(a / maxSize);
            total = numberOfPossibleWholeTilesH * numberOfPossibleWholeTilesW;
        }

        return maxSize;

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

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

Я мог бы оптимизировать это дальше, делая что-то вроде уменьшения оптимального размера на -2 insted из -1 каждый раз, а затем, если все плитки увеличиваются на 1, чтобы убедиться, что я не пропустил допустимый размер. или я мог бы отскакивать больше, чем -2, скажем -10, тогда, если все плитки будут увеличиваться на 5, то если они не подходят, уменьшите на -2 и т.д., пока я не получу оптимальную подгонку.

Обратите внимание на http://kennethsutherland.com/flex/stackover/SlideSorterOK.html для моего примера. Спасибо за всю информацию.

Ответ 2

Это проблема упаковки. Оптимальных решений трудно найти. См. Например Упаковка N квадратов в квадрате.

Вы можете вычислить (оптимистичную) верхнюю границу, разделив общую поверхность на число квадратов: sqrt(width*height/n).

Ответ 3

Концептуально:

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

псевдокод: заданный прямоугольник M x N для заполнения квадратами K

// initial candidate grid within the rectangle
h=1
w=1
maxsquares=1
size=min(M,N) //size of the squares
while K > maxsquares
  if M/(h+1) >= N/(w+1)
    h=h+1
  else
    w=w+1
  endif
  maxsquares=h*w
  size=min(M/h,N/w)
done
print size

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

Ответ 4

Вот решение O (1) без петель.

Используя соотношение сторон (высота/ширина) прямоугольника, вы можете придумать начальное предположение о количестве плиток в направлениях x и y. Это дает верхнюю и нижнюю границу для общего количества плиток: между xy и (x + 1) (y + 1).

Основываясь на этих ограничениях, существует три возможности:

• Нижняя граница верна. Вычислите самый большой размер tileSize, который приведет к xy-фрагментам.
• Верхняя граница верна. Вычислите наибольший размер tileSize, который приведет к (x + 1) (y + 1) фрагментам
• Правильный ответ лежит где-то между верхней и нижней границами. Решите уравнение, чтобы определить правильные значения x и y, а затем вычислите самый большой размер tileSize, который приведет к правильному количеству фрагментов

int GetTileSize(int width, int height, int tileCount)
{
    // quick bailout for invalid input
    if (width*height < tileCount) { return 0; }

    // come up with an initial guess
    double aspect = (double)height/width;
    double xf = sqrtf(tileCount/aspect);
    double yf = xf*aspect;
    int x = max(1.0, floor(xf));
    int y = max(1.0, floor(yf));
    int x_size = floor((double)width/x);
    int y_size = floor((double)height/y);
    int tileSize = min(x_size, y_size);

    // test our guess:
    x = floor((double)width/tileSize);
    y = floor((double)height/tileSize);
    if (x*y < tileCount) // we guessed too high
    {
        if (((x+1)*y < tileCount) && (x*(y+1) < tileCount))
        {
            // case 2: the upper bound is correct
            //         compute the tileSize that will
            //         result in (x+1)*(y+1) tiles
            x_size = floor((double)width/(x+1));
            y_size = floor((double)height/(y+1));
            tileSize = min(x_size, y_size);
        }
        else
        {
            // case 3: solve an equation to determine
            //         the final x and y dimensions
            //         and then compute the tileSize
            //         that results in those dimensions
            int test_x = ceil((double)tileCount/y);
            int test_y = ceil((double)tileCount/x);
            x_size = min(floor((double)width/test_x), floor((double)height/y));
            y_size = min(floor((double)width/x), floor((double)height/test_y));
            tileSize = max(x_size, y_size);
        }
    }

    return tileSize;
}

Я тестировал эту функцию для всех целых ширин, высот и tileCounts между 1 и 1000, используя следующий код:

for (width = 1 to 1000)
{
    for (height = 1 to 1000)
    {
        for (tileCount = 1 to 1000)
        {
            tileSize = GetTileSize(width, height, tileCount);

            // verify that increasing the tileSize by one
            // will result in too few tiles
            x = floor((double)width/(tileSize+1));
            y = floor((double)height/(tileSize+1));
            assert(x*y < tileCount);

            // verify that the computed tileSize actually
            // results in the correct tileCount
            if (tileSize > 0)
            {
                x = floor((double)width/tileSize);
                y = floor((double)height/tileSize);
                assert(x*y >= tileCount);
            }
        }
    }
}

Ответ 5

Следующая функция вычисляет плиту максимального размера для данной информации.

Если тот факт, что он написан на Python, затрудняет вам понимание, дайте мне знать в комментарии, и я попытаюсь сделать это на другом языке.

import math
from __future__ import division

def max_tile_size(tile_count, rect_size):
    """
    Determine the maximum sized tile possible.

    Keyword arguments:
    tile_count -- Number of tiles to fit
    rect_size -- 2-tuple of rectangle size as (width, height)
    """

    # If the rectangle is taller than it is wide, reverse its dimensions
    if rect_size[0] < rect_size[1]:
        rect_size = rect_size[1], rect_size[0]

    # Rectangle aspect ratio
    rect_ar = rect_size[0] / rect_size[1]

    # tiles_max_height is the square root of tile_count, rounded up
    tiles_max_height = math.ceil(math.sqrt(tile_count))

    best_tile_size = 0

    # i in the range [1, tile_max_height], inclusive
    for i in range(1, tiles_max_height + 1):

        # tiles_used is the arrangement of tiles (width, height)
        tiles_used = math.ceil(tile_count / i), i

        # tiles_ar is the aspect ratio of this arrangement
        tiles_ar = tiles_used[0] / tiles_used[1]

        # Calculate the size of each tile
        # Tile pattern is flatter than rectangle
        if tile_ar > rect_ar:
            tile_size = rect_size[0] / tiles_used[0]
        # Tile pattern is skinnier than rectangle
        else:
            tile_size = rect_size[1] / tiles_used[1]

        # Check if this is the best answer so far
        if tile_size > best_tile_size:
            best_tile_size = tile_size

    return best_tile_size

print max_tile_size(4, (100, 100))

Алгоритм можно легко описать следующим образом

• Если прямоугольник выше ширины, переверните его так, чтобы он был шире, чем высокий.
• Вычислить s, квадратный корень из числа плиток, округленный вверх. (Именован tiles_max_height в коде.)
• Loop, где я идет от 1 до включительно:
  • Постройте сетку квадратов, которая представляет собой количество фрагментов /i квадратов в ширину и я квадратов. (Закруглите все вверх. Это "прокладывает" недостающие плитки, например, используя 2 плитки на 2 плитки, когда ваше общее количество плиток равно 3.)
  • Сделайте эту сетку максимально возможной. (Рассчитайте это с использованием пропорций.) Определите размер одной плитки.
  • Используя этот размер, определите общую площадь, покрываемую фрагментами.
  • Убедитесь, что это лучшая общая область; если это так, сохраните квадратный размер
• Вернуть этот квадратный размер

Это, вероятно, один из самых быстрых алгоритмов, перечисленных здесь, поскольку он вычисляет лучший квадратный размер в O (sqrt (n)) для n плит.

Обновление

При дальнейшем рассмотрении эта задача имеет более простое решение, основанное на решении выше. Скажем, вам дано 30 плиток. Ваши возможные схемы плитки легко вычислить:

• 30 x 1 (соотношение сторон 30.0000)
• 15 x 2 (соотношение сторон 7.5000)
• 10 x 3 (соотношение сторон 3.3333)
• 8 x 4 (соотношение сторон 2.0000)
• 6 x 5 (соотношение сторон 1,2000)
• 6 x 6 (соотношение сторон 1.0000)

Скажите, что ваш прямоугольник равен 100 x 60. Соотношение сторон вашего прямоугольника равно 1.6667. Это от 1,2 до 2. Теперь вам нужно только рассчитать размеры плитки для 8 x 4 и 6 x 5.

Первый шаг по-прежнему технически занимает O (sqrt (n)), поэтому этот обновленный метод не асимптотически быстрее первой попытки.

Некоторые обновления из потока комментариев

/*
Changes made:

tiles_used -> tiles_used_columns, tiles_used_rows
    (it was originally a 2-tuple in the form (colums, rows))
*/

/* Determine the maximum sized tile possible. */
private function wesleyGetTileSize() : Number {
    var tile_count : Number = slideCount.value;
    var b : Number = heightOfBox.value;
    var a : Number = widthOfBox.value;
    var ratio : Number;    

    // // If the rectangle is taller than it is wide, reverse its dimensions    

    if (a < b) {
        b = widthOfBox.value;
        a = heightOfBox.value;
    } 

    // Rectangle aspect ratio   
    ratio = a / b;    

    // tiles_max_height is the square root of tile_count, rounded up    
    var tiles_max_height : Number = Math.ceil(Math.sqrt(tile_count))    
    var tiles_used_columns : Number;
    var tiles_used_rows : Number;
    var tiles_ar : Number;
    var tile_size : Number;

    var best_tile_size : Number = 0;    

    // i in the range [1, tile_max_height], inclusive   
    for(var i: Number = 1; i <= tiles_max_height + 1; i++) {       
        // tiles_used is the arrangement of tiles (width, height)        
        tiles_used_columns = Math.ceil(tile_count / i);   
        tiles_used_rows = i;

        // tiles_ar is the aspect ratio of this arrangement        
        tiles_ar = tiles_used_columns / tiles_used_rows;        

        // Calculate the size of each tile        
        // Tile pattern is flatter than rectangle       
        if (tiles_ar > ratio){           
            tile_size = a / tiles_used[0]   ;
        }    
        // Tile pattern is skinnier than rectangle        
        else {            
            tile_size = b / tiles_used[1];
        }        
        // Check if this is the best answer so far        
        if (tile_size > best_tile_size){           
            best_tile_size = tile_size;
        }   
    }

    returnedSize.text = String(best_tile_size);
    return best_tile_size;
}

Ответ 6

Не могли бы вы рассказать о том, как вы определяете заполнение? Если я последую вашему описанию (большое, если), кажется, что многие из описанных вами случаев фактически не заполняют прямоугольник. Например, вы говорите, что 2 квадрата в прямоугольнике 100 * 100 будут 50 * 50. Если я правильно понимаю вашу конфигурацию, они будут помещены в "диагональ" этого прямоугольника. Но тогда в этом прямоугольнике было бы два "зазора" размером 50 * 50. Это не то, что я считаю "заполнением" прямоугольника. Вместо этого я поставил бы проблему как самый возможный размер для 2 (квадраты равного размера), чей ограничивающий прямоугольник будет 100 * 100 (при условии, что каждый квадрат должен был быть связан хотя бы с одним другим квадратом?).

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

Кроме того, можете ли вы написать функциональный интерфейс для этого расчета? Вам нужно сделать это для n возможных квадратов с учетом размеров ограничивающей рамки?

Ответ 7

Указанные значения:

N - number of tiles
a, b - sides of the rectangle

сторона плитки может быть рассчитана с использованием этой функции:

def maxSize(n: Int, a: Int, b: Int) = {
  var l = 0
  for (i <- 1 until a.min(b)) { // 
    val newL = (a.min(b) / i).min( (a.max(b) * i)/n )
    if (l < newL && ((a.min(b)/newL) * (a.max(b)/newL) >= n )  )
      l = newL
  }
  return l
}

Я предположил, что вы не собираетесь делать плитки меньше 1x1, независимо от того, какая мера 1

сначала вы начинаете с размера 0:

l = 0

то вы повторяете от 1 до K столбцов фрагментов, где

K = min(a, b)

для каждой итерации вычисляет новую максимальную сторону плитки, используя эту формулу

val newL = ( a.min(b) / i ).min( (a.max(b) * i)/n )

эта формула принимает меньшее значение из этих двух значений:

1. min(a, b)/i -- maximum length of a tile if there are i columns in the smaller side of the rectangle
2. (i * max(a, b))/n -- maximum length of a tile if there are i columns and n tiles in the bigger side of the rectangle

если кандидат newL больше начального значения l и максимально возможное количество фрагментов, которые могут быть помещены в квадрат без перекрытия, больше или равно числу плит n, тогда

l = newL

в конце return l

Ответ 8

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

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

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

Предположим, что мы уже знаем, что 10 квадратов должны быть помещены в первую строку и что это идеально подходит для ширины. Тогда длина стороны width/10. Поэтому мы можем разместить квадраты m = height/sidelength в первом столбце. Эта формула могла бы сказать, что мы можем разместить 2.33 квадрата в первом столбце. Невозможно разместить 0,33 квадрата, мы можем разместить только 2 квадрата. Действительная формула m = floor(height/sidelength).

Не очень быстрый (но LOT быстрее, чем попытка каждой комбинации) алгоритм состоит в том, чтобы попытаться сначала поместить 1 квадрат в первую строку/столбец, а затем посмотреть, можем ли мы разместить достаточно прямоугольников в прямоугольнике. Если это не сработает, мы попробуем 2 квадрата в первой строке/столбце и т.д., Пока мы не сможем подобрать количество нужных фрагментов.

Я думаю, что существует O (1) алгоритм, если вам разрешено делать арифметику в O (1), но я до сих пор не понял.

Вот рубиновая версия этого алгоритма. Этот алгоритм O (sqrt (# of tiles)), если прямоугольник не очень тонкий.

def squareside(height, width, tiles)
  n = 0
  while true
    n += 1
    # case 1: the squares fill the height of the rectangle perfectly with n squares
    side = height/n
    m = (width/side).floor # the number of squares that fill the width
    # we're done if we can place enough squares this way
    return side if n*m >= tiles
    # case 2: the squares fill the width of the rectangle perfectly with n squares
    side = width/n
    m = (height/side).floor
    return side if n*m >= tiles
  end
end

Вы также можете использовать двоичный поиск этого алгоритма. В этом случае это O (log (# плит)).

Ответ 9

x = max(rectHeight/numberOfSquares, rectangleLength/numberOfSquares)

if x <= retangleHeight && x <= rectangleLength then
  squareSideLength = x
else
  squareSideLength = min(rectangleHeight, rectangleLength)

Ответ 10

Разделите большую сторону на количество плиток. Используйте меньшую сторону как размер плитки. Presto! # плиток.

Rectagle = 200 x 10
Each tile is 10 x 10 (length of shorter side)
200/10 = 20 (number of tiles needed)