Программно расположить прямоугольные объекты пользовательского интерфейса абстрактно, без пробелов

Question

Учитывая коллекцию, скажем, 50 изображений различной ширины и высоты, как можно было бы программно расположить их интересным * абстрактным способом?(см. изображение ниже)

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

В моем конкретном случае все изображения имеют установленный максимальный размер 150 пикселей, что может означать, что высота ИЛИ ширина составляет максимум 150 пикселей (может быть 150 пикселей на 450 пикселей или 378 пикселей на 150 пикселей)..

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

РЕДАКТИРОВАТЬ: Изменено изображение, чтобы показать, что нет никаких ограничений на то, какобщее расположение должно быть (не должно помещаться внутри заданной области)

Answer 1

Если вы не против jquery-плагина, вы можете проверить это - http://masonry.desandro.com/

Answer 2

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

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

Answer 3

Ваша проблема NP-Hard .

Этот поток показывает, что даже с одним типом прямоугольников nXm сложно найти решение, если есть решение, поэтому ваша более обобщенная проблема, конечно же, тоже NP-сложная [ один тип прямоугольника является частным случаем этой проблемы]

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