Всем привет. Меня зовут Марат Исаев, я фронтенд-разработчик ВКонтакте, разрабатываю решения для VK Мессенджера. В этом посте я хочу рассказать о том, как сделать сетку предпросмотра фотографий (сейчас этот вариант доступен в фастчатах ВКонтакте, но уже в ближайшее время он появится в VK Мессенджере веб-версии). На практике всё не так просто, как может показаться на первый взгляд – изображения бывают разной ориентации и с разным соотношением сторон. Иногда хочется сделать акцент на каких-то изображениях из набора, но при этом показать и другие.

Популярный подход

Пожалуй, чаще всего сетку предпросмотра делают так: описывают несколько алгоритмов, которые будут применены к альбому в зависимости от количества фотографий, соотношения их сторон и ещё каких-то специфичных для проекта параметров. Например: «Если в альбоме три фотографии и большинство из них портретной ориентации, то применить Strategy3Portrait; если фотографий от 5 до 10, то применить Strategy5_10». При этом важно сохранить порядок следования фотографий.

Давайте по-другому

Я предлагаю рассмотреть другой способ решения этой задачи. Сначала откажемся от привязки к конкретному количеству фотографий и их пространственной ориентации. Сформулируем задачу так: «Разместить N фотографий со сторонами x_ny_n в прямоугольнике со сторонами ab, сохранив их очерёдность».

Затем выровняем все фотографии по высоте h и начнём их «выкладывать» как кирпичи.

Если фотография не помещается в текущий ряд, то перенесём её в новый и продолжим «выкладывать».

Закончив «кладку», изменим масштаб каждого ряда таким образом, чтобы заполнить «пробелы».

Теперь проверим «кладку», чтобы ни одна картинка не оказалась слишком маленькой (минимальные размеры h_min и w_min). Если мы близки к соотношению сторон прямоугольника a*b и проверка на критические размеры пройдена, то получившуюся сетку можно считать подходящей.

Очевидно, что чем удачнее мы выберем h в диапазоне от h_min до b, тем быстрее мы получим желаемый результат. К примеру, можно подбирать h бинарным поиском. Или можно поступить ещё проще: сделать несколько «кладок» с шагом дельта от h_min до b, а затем выбрать вариант, у которого соотношение сторон ближе всего к a/b.

Сложность алгоритма

Узкое место этого алгоритма — тот самый поиск оптимального h. Если мы будем идти с шагом дельта, то сложность будет линейная, потому что количество шагов — константа. И если будем искать бинарным поиском, то сложность тоже будет линейной, константой будет диапазон b − h_min, а следовательно и log₂(b − h_min).

Из мира идеального в мир реальный

Можно ли «разместить N фотографий со сторонами x_ny_n в прямоугольнике с размерами ab, сохранив их очерёдность»? Да. Можно ли «разместить N фотографий со сторонами x_ny_n в прямоугольнике с размерами ab, сохранив их очерёдность и выдержав критические размеры и оригинальные соотношения сторон»? Не всегда. Это будет зависеть от N, от соотношения сторон фотографий и от a и b. Во ВКонтакте количество изображений в предпросмотре ограничено 10. Если фотография одна, то сетка и не нужна. Значит, нам нужно как-то гарантировать хороший результат для 2—10 изображений.

Мы имеем дело с комбинаторикой. Нужно просчитать все возможные варианты и проанализировать результат. Причём для решения задачи нам нужно воспользоваться «размещением с повторениями» A_n^k = n^k . В нашем случае n — это количество всех возможных соотношений сторон отдельных фотографий, а k — общее количество фотографий (от 2 до 10). Отсюда вывод: чтобы количество размещений было конечным, нам важно: чтобы и количество возможных соотношений сторон было конечным. Например, выберем пять соотношений: 9/16, 3/4, 1/1, 4/3 и 16/9. Тогда количество размещений рассчитывается как 5^k , где k = 2, …, 10. То есть, если у нас есть в альбоме пять фотографий с пятью возможными соотношениями, то количество всех возможных вариантов их размещения равно 3125.

Описывать стратегии для всех частных случаев нет смысла, их слишком много. А если ограничиться лишь квадратами, то мы легко можем описать десять стратегий (напомню, что количество размещений в таком случае будет 1^k, k = 1, …, 10). Но ведь мы хотим сделать сетку предпросмотра по возможности разнообразной, поэтому давайте подумаем, как ещё можно улучшить алгоритм.

Объять необъятное. Как просмотреть и оценить все «сетки»

Обозначив диапазон соотношений сторон, мы можем отказаться и от проверки на критические размеры h_min и w_min для каждой отдельной фотографии, так как они станут взаимосвязаны (нам достаточно знать лишь, что выбранный h ≥ h_min и h ≤ b). Скрипт для набора пула возможных размещений вы можете взять здесь.

Теперь прогоним пул через наш алгоритм и проанализируем разброс отклонений соотношений сторон получившихся сеток от эталонной a/b. Если отклонения невелики, то фиксируем h_min, a, b и значения соотношений сторон фотографий. А если отклонения велики, то корректируем их. Возможно, стоит сократить количество соотношений или изменить размеры a и b. Зачастую общую картину портит последнее изображение, которое остаётся одно в последнем ряду. В таких случаях можно принудительно объединять два последних ряда.

Допустим, нам нужно скомпоновать фотографии в сетку с соотношением сторон 4/3. Примем ширину «окна» в 360 пикселей и укажем, что минимальная высота каждой отдельной фотографии должна быть не менее 80 пикселей. Не буду приводить все диаграммы, для понимания общей картины нам достаточно посмотреть на распределение всех получившихся «сеток» по диапазонам соотношений сторон для 2, 5 и 10 фотографий.

Чем больше фотографий, тем больше и пространство для манёвра. Например, если рядов больше двух и последний ряд содержит единственное изображение (то о чём мы говорили выше), мы можем применить принудительное объединение последних рядов.

Как видите, чем больше вариантов нам доступно, тем лучше сетка поддаётся постобработке. Потом можно, например, отсекать слишком высокие «сетки» отдавая предпочтение тем, что шире. Или наоборот, если вы формируете сетки под экраны смартфонов. Таких эвристик можно придумать много.

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

Мы придём к гарантированному результату для любого количества фотографий за время O(n).

P.S.: Если у вас есть свой «рецепт» для сетки предпросмотра, делитесь в комментариях.