Алгоритм размещения нескольких изображений - алгоритм коллажа

Question

Я создаю приложение для одновременного отображения нескольких видео (скажем, 2-10 видео). Я в основном ищу алгоритм, который может помочь в размещении видео на экране. Проблема, с которой я сталкиваюсь, заключается в том, что каждое видео может иметь разное соотношение сторон, и мне, очевидно, потребуется изменить размер видео, чтобы они все уместились на экране. Но я хочу изменить их размер и подогнать их так, чтобы максимально использовать экран (и минимизировать искажения пропорций). Кроме того, я хочу, чтобы пользователь мог увеличить размер одного или нескольких видео, чтобы он занимал больше места на экране. Таким образом, алгоритм должен быть стабильным в том смысле, что увеличение одного видео не заставляет все места размещения перепрыгивать.

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

Так кто-нибудь знает алгоритм размещения?

Для пояснения приведу пример. У меня есть три видео, со следующими размерами. Я хочу, чтобы первое видео занимало примерно 50% экрана, а последние два видео занимали примерно 25% экрана.

(464, 336) 50%
(624, 480) 25%
(608, 336) 25%

Как бы я разместил их на экране (1024x800) для достижения этой цели? Я решил, что сначала разделю экран пополам, и лучше всего подойдет первое видео в верхней половине. Затем я разделил бы нижнюю половину на две части и поместил бы оба оставшихся видео как можно лучше.

спасибо заранее

Answer 1

Я думаю, Treemap - это то, что вам может понадобиться.

Хорошее описание истории алгоритма здесь

Упорядоченные квантовые древовидные карты, более соответствующие текущему поиску, здесь

HTH!

Answer 2

Это версия проблемы с упаковкой в ​​бункер http://en.wikipedia.org/wiki/Bin_packing_problem который NP-hard, так что вы захотите выбрать разумную эвристику. Если вы не хотите, чтобы видео изменялось при изменении его размера, вам нужно оставить кучу дополнительного мертвого пространства или автоматически уменьшить другие.

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

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

Answer 3

Квадратный корень + логика на основе округления. Если остаток от sqrt <0,5, округлите результат вниз, используйте результат в виде строк / столбцов и добавьте 1 к числу строк или столбцов; если остаток от sqrt> = 0.5, округлите результат и используйте его как число строк / столбцов.

10 videos = 4x3 (3.16; rounded down, so add 1 row or col)
9 videos = 3x3 (3; abs)
8 videos = 3x3 (2.82; round up)
7 videos = 3x3 (2.64; round up)
6 videos = 3x2 (2.44; round down, so add 1 row or col)
5 videos = 3x2 (2.23; round down, so add 1 row or col)
4 videos = 2x2 (2; abs)
3 videos = 2x2 (1.73; round up)
2 videos = split screen in half vertically or horizontally (however you'd like)
1 video = full screen

Теперь это должно сделать все видео "квадратными", и, вероятно, лучшим вариантом, потому что вы действительно не можете легко учесть различные разрешения / отношения, которые существуют там (если это не статично для вас).

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

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

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

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