Алгоритм макета

Question

У меня есть массив из N картинок, каждая с размерами WxH. Я хочу отобразить их в прямоугольной матрице, максимально приближенной к квадрату. Последний ряд может быть неполным. Как рассчитать количество строк и столбцов?

Answer 1

Итак, предположим, что у вас p и q;тогда все ваше изображение будет pW на qH.Вы хотите включить все изображения, поэтому pq> = N;только последняя строка может быть неполной, поэтому p (q-1)

Условия N

Итак, очень грубо, p / (N / p) ~ = H / W, поэтому p ~ = sqrt (NH / W).

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

Итак, супернаивный, но, вероятно, адекватный псевдокод выглядит следующим образом (обратите внимание, что он игнорирует такие вещи, как преобразование между целочисленными значениями и значениями с плавающей запятой):

target_ratio = H/W;
p = round(sqrt(N*H/W)); // initial guess
current_ratio = p / ceiling(N/p);
merit = merit_function(current_ratio, target_ratio);
best_p = p; best_merit = merit; prev_merit = merit;
// [define merit_function however you like; e.g., -abs(log(x/y)-1)
// or -max(x/y-1,y/x-1) or whatever.]
if (current_ratio > target_ratio) {
  // p might be too big
  while (true) {
    --p; if (p<=0) break;
    current_ratio = p / ceiling(N/p);
    merit = merit_function(current_ratio, target_ratio);
    if (merit > best_merit) { best_p=p; best_merit=merit; }
    else if (merit < prev_merit) break;
    prev_merit = merit;
  }
}
else if (current_ratio < target_ratio) {
  // p might be too small
  // similar loop, but in the other direction
}

Я подозреваю, что для разумного выбора merit_function вам когда-либо придется делать только одну итерацию, но я не чувствую, что пытаюсь доказать это прямо сейчас.

Если адекватное решение, а не оптимальное,достаточно хорош, тогда вы можете просто использовать p=round(sqrt(N*H/W)) и покончить с этим.Или, для немного лучшего приближения, вы могли бы сказать, что ceiling(N/p), вероятно, в среднем примерно N/p+0.5, что, я думаю, в конечном итоге означает, что вы хотите что-то вроде p = round(sqrt(N*H/W+0.25*H*H/(W*W)) - 0.25*H/W.(Вам, вероятно, следует проверить мою алгебру, прежде чем полагаться на нее. Я просто упрощаю p / (N / p-1/2) = H / W и решаю полученное квадратное уравнение.)

Answer 2

Вы можете попробовать все возможные макеты, если N достаточно мало.

Score(N, W, H, columnCount):
    rowCount = ceiling(N / columnCount)
    xPixels = W * columnCount
    yPixels = H * rowCount
    return min(xPixels, yPixels) / max(xPixels, yPixels)

bestColumnCount = columnCount with max Score(N, W, H, columnCount) in [1,N]
bestRowCount = ceiling(N / bestColumnCount) 

Answer 3

(1-я попытка была совершенно неверной ..

(так было и со второй попытки)

3-я попытка:

columns = floor( sqroot( N * H / W ) + 0.5 )
rows = ceiling( N / columns )