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

Question

У меня есть N прямоугольных элементов с соотношением сторон Aitem (X: Y).
У меня есть прямоугольная область отображения с соотношением сторон Aview

Элементы должны быть расположены в виде таблицы.(т. е. r строк, c столбцов).

Что такое идеальная сетка строк x столбцов, чтобы отдельные элементы были самыми большими?(строки * столбцы> = N, конечно - то есть могут быть «неиспользуемые» места сетки).

Простой алгоритм может выполнять итерации по строкам = 1..N, вычислять необходимое количество столбцов и сохранятьпара строка / столбец с самыми большими элементами.

Интересно, есть ли не итерационный алгоритм, хотя (например, для Aitem = Aview = 1, строки / столбцы могут быть аппроксимированы как sqrt (N)).

Answer 1

Примечание. Я не совсем понял ответ Фредерика, поэтому сам решил проблему и придумал то, что кажется тем же решением. Я подумал, что мог бы также объяснить, что я сделал, если это будет полезно.

Сначала я нормализовал соотношение сторон вида и вида предметов. (Я предполагаю, что вы не хотите вращать предметы.)

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

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

a = c/r

где r и c - номера строк и столбцов:

N = r*c

Умножение / деление этих двух уравнений дает нам

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

Если сетка идеальна, r и c будут целыми числами, но если нет, вы должны попробовать три варианта, упомянутых Фредериком, и оставить тот, где r*c наименьший, но все же больше N :

• floor(r), ceil(c)
• ceil(r), floor(c)
• ceil(r), ceil(c)

Answer 2

Ваше решение может быть легко улучшено для обработки общего случая:

Если мы (временно) забудем о необходимости иметь целое число строк и столбцов, мы получим

строки * столбцы = N

x = aitem * y

aview = строки * x = строки * aitem * y

1 = столбцы * y = (N / строки) * (aview / [aitem * строки]) = N * aview / (aitem * строки²)

следовательно, строки = sqrt (N * aitem / aview) и столбцы = N / строки = sqrt (N * aitem / aview)

Тогда ceil (строки) и ceil (столбцы) являются решением, в то время как floor (строки) и floor (столбцы) слишком малы, чтобы быть решением вместе (если строки и столбцы не являются целыми числами). Это оставляет 3 возможных решения:

• пол (ряды), потолок (колонны)
• потолок (ряды), пол (колонны)
• ceil (ряды) ceil (столбцы)

отредактировано для исправления уравнений. Первый результат был неверным (см. Комментарии)

Answer 3

Хороший вопрос. Если ваш вид имеет размеры A x B (фиксированный), а ваши элементы имеют размеры a x b (переменный, который будет развернут), вам необходимо:

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

Я не знаю, как решить эту проблему - усечение - сложная часть, так как она нелинейная.