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

Question

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

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

Каковы идеальные строки сетки x столбцов, так что отдельные предметы являются наибольшими? (строки * colums> = 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 будут целыми, но если нет, то вы должны попробовать три варианта Frédéric упомянутых и сохранить тот, где r*c самый маленький, но все же больше, чем N:

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

Answer 2

Хороший вопрос. Если вид имеет размеры А х В (фиксированный) и ваши детали, имеют размер AXB (переменная, которая должна быть развернуто), то вам необходимо:

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

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

Answer 3

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

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

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

х = у * aitem

AView = строка * х = строка * aitem * у

1 = столбцы * Y = (N/строки) * (AView/[айт ет * строк]) = N * AView/(aitem * rows²)

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

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

• этаж (строки) CEIL (колонны)
• CEIL (строки) этаж (столбцы)
• CEIL (строки) CEIL (колонны)

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