Как оптимизировать расположение прямоугольников

Question

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

Я знаю, каковы размеры экрана.

Как рассчитать оптимальное количество строк и столбцов, на которое мне нужно разделить экран, и к какому размеру мне нужно будет масштабировать объекты?

Спасибо

Джейми.

Answer 1

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

Давайте играть!

// Proportion of the screen
// w,h width and height of your rectangles
// W,H width and height of the screen
// N number of your rectangles that you would like to fit in

// ratio
r = (w*H) / (h*W)

// This ratio is important since we can define the following relationship
// nbRows and nbColumns are what you are looking for
// nbColumns = nbRows * r (there will be problems of integers)
// we are looking for the minimum values of nbRows and nbColumns such that
// N <= nbRows * nbColumns = (nbRows ^ 2) * r
nbRows = ceil ( sqrt ( N / r ) ) // r is positive...
nbColumns = ceil ( N / nbRows )

Я надеюсь, что я правильно понял математику, но это не может быть далеко от того, что вы ищете;)

EDIT: нет большого различия между соотношением, шириной и высотой ...

// If ratio = w/h
r = ratio * (H/W)

// If ratio = h/w
r = H / (W * ratio)

А затем вы снова используете 'r', чтобы узнать, сколько строк и столбцов используется.

Answer 2

Это почти точно так же, как вопрос Кеннета здесь, на SO. Он также написал это в своем блоге .

Если вы масштабируете пропорции в одном измерении, так что вы упаковываете квадраты, это становится той же проблемой.

Answer 3

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

Каждый возможный выбор (количество строк и столбцов прямоугольников) приводит к максимально возможному размеру прямоугольника для указанных пропорций. Цикл возможных вариантов и вычисление результирующего размера реализует простой линейный поиск по пространству возможных решений. Вот фрагмент кода, который делает это, используя пример экрана 480 x 640 и прямоугольников в пропорции 3 x 5.

def min (a, b)
  a < b ? a : b
end

screenh, screenw = 480, 640
recth, rectw = 3.0, 5.0
ratio = recth / rectw

puts ratio

nrect = 14

(1..nrect).each do |nhigh|
  nwide = ((nrect + nhigh - 1) / nhigh).truncate
  maxh, maxw = (screenh / nhigh).truncate, (screenw / nwide).truncate
  relh, relw = (maxw * ratio).truncate, (maxh / ratio).truncate
  acth, actw = min(maxh, relh), min(maxw, relw)
  area = acth * actw
  puts ([nhigh, nwide, maxh, maxw, relh, relw, acth, actw, area].join("\t"))
end

Запуск этого кода обеспечивает следующую трассировку:

1 14 480 45 27 800 27 45 1215
2 7 240 91 54 400 54 91 4914
3 5 160 128 76 266 76 128 9728
4 4 120 160 96 200 96 160 15360
5 3 96 213 127 160 96 160 15360
6 3 80 213 127 133 80 133 10640
7 2 68 320 192 113 68 113 7684
8 2 60 320 192 100 60 100 6000
9 2 53 320 192 88 53 88 4664
10 2 48 320 192 80 48 80 3840
11 2 43 320 192 71 43 71 3053
12 2 40 320 192 66 40 66 2640
13 2 36 320 192 60 36 60 2160
14 1 34 640 384 56 34 56 1904

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

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

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

Answer 4

Один из способов, которые мне нравятся, это использовать квадратный корень области:

Пусть

r = number of rectangles

w = width of display

h = height of display

Тогда

A = (w * h) / r это площадь на прямоугольник

и

L = sqrt(A) - базовая длина каждого прямоугольника.

Если они не квадратные, то просто умножьте соответственно, чтобы сохранить то же соотношение.

Другой способ сделать подобное - просто взять квадратный корень из числа прямоугольников. Это даст вам одно измерение вашей сетки (то есть количество столбцов):

C = sqrt(n) - количество столбцов в вашей сетке

и

R = n / C - количество строк.

Обратите внимание, что один из них должен будет ceiling, а другой floor, иначе вы урежете числа и можете пропустить строку.

Answer 5

Ваше упоминание о строках и столбцах предполагает, что вы предусмотрели расположение прямоугольников в сетке, возможно, с несколькими пробелами (например, некоторые из нижнего ряда) незаполненными. Предполагая, что это так:

Предположим, вы масштабируете объекты так, что (пока неизвестное число) n из них умещается по экрану. Тогда

objectScale=screenWidth/(n*objectWidth)

Теперь предположим, что есть N объектов, поэтому будет

nRows = ceil(N/n)

строк объектов (где ceil - это Функция потолка ), которые займут

nRows*objectScale*objectHeight

вертикальной высоты. Нам нужно найти n и выбрать самое маленькое n, чтобы это расстояние было меньше, чем screenHeight.

Простое математическое выражение для n усложняется наличием функции потолка. Если число столбцов будет довольно небольшим, вероятно, самый простой способ найти n - просто пройтись по циклу увеличения n, пока неравенство не будет удовлетворено.

Редактировать: Мы можем начать цикл с верхней границы

floor(sqrt(N*objectHeight*screenWidth/(screenHeight*objectWidth)))

для n, и работать вниз: решение тогда найдено в O (sqrt (N)). Решение O (1) состоит в том, чтобы предположить, что

nRows = N/n + 1

или взять

n=ceil(sqrt(N*objectHeight*screenWidth/(screenHeight*objectWidth)))

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

Пограничные случаи возникают, когда N=0, а когда N=1 и соотношение сторон объектов таковы, что objectHeight/objectWidth > screenHeight/screenWidth - с обоими легко справиться.