оптимизированная сетка для прямоугольных объектов
У меня есть прямоугольные объекты N с соотношением сторон Aitem (X:Y).
У меня есть прямоугольная область дисплея с соотношением сторон Aview
Объекты должны быть расположены в подобном таблице расположении (т.е. r строки, c столбцы).
каковы идеальные строки сетки x столбцы, так, чтобы отдельные объекты были самыми большими? (строки * colums> = N, конечно - т.е. могут быть "неиспользованные" места сетки).
Простой алгоритм мог выполнить итерации по строкам = 1.. N, вычислите необходимое число столбцов и сохраните пару строки/столбец с самыми большими объектами.
Интересно, существует ли неитеративный алгоритм, хотя (например, для Aitem = Aview = 1, строки / седла могут быть приближены sqrt (N)).
3 ответа
Примечание. Я не совсем понял ответ Фредерика, поэтому решил проблему сам и нашел то же решение. Я подумал, что могу также объяснить, что я сделал, если это будет полезно.
Сначала я нормализовал соотношение сторон изображения к изображению предметов. (Я предполагаю, что вы не хотите вращать элементы.)
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), этаж (c)ceil (r), ceil (c)
Ваше решение может быть легко улучшено для обработки общего случая:
Если мы (временно) забудем о необходимости иметь целое число строк и столбцы, у нас есть
строки * столбцы = N
x = aitem * y
aview = rows * x = rows * aitem * y
1 = columns * y = (N / rows) * ( aview / [aitem * rows]) = N * aview / (aitem * rows²)
, следовательно, rows = sqrt (N * aview / aitem) и columns = N / rows = sqrt (N * aitem / aview)
Тогда ceil (строки) и ceil (столбцы) являются решением, в то время как floor (строки) и floor (столбцы) слишком малы, чтобы быть решением вместе (если строки и столбцы не являются целыми числами). Это оставляет 3 возможных решения:
- этаж (строки) ceil (столбцы)
- ceil (строки) этаж (столбцы)
- ceil (строки) ceil (столбцы)
отредактировано для исправления уравнений . Первый результат был неверным (см. Комментарии)
Хороший вопрос. Если ваш вид имеет размеры A x B (фиксированные), а ваши элементы имеют размеры a x b (переменные, которые нужно максимизировать), то вам нужно:
trunc(A / a) * trunc(B / b) >= N
Я понятия не имею, как это решить - усечение является сложной частью, поскольку оно нелинейное.