Библиотека Packery реализует алгоритм пространственной упаковки элементов внутри контейнера. Основная задача алгоритма — размещение блоков различного размера таким образом, чтобы минимизировать пустоты и максимально эффективно использовать доступное пространство.
В отличие от традиционных сеточных систем, где каждый элемент занимает строго определённую ячейку, алгоритм Packery допускает гибкое размещение. Элементы могут занимать разное количество пространства, а их позиционирование определяется динамически в процессе построения макета.
Алгоритм относится к классу задач двумерной упаковки (2D bin packing) — широко известной вычислительной проблеме, применяемой в оптимизации пространства, компоновке интерфейсов, системах хранения и производстве.
Алгоритм Packery работает на основе нескольких ключевых сущностей:
Контейнер — область, внутри которой размещаются элементы.
Элементы (items) — блоки различного размера, которые необходимо расположить.
Свободные области (spaces) — прямоугольные области контейнера, ещё не занятые элементами.
Каждый новый элемент помещается в одну из свободных областей. После размещения алгоритм пересчитывает оставшиеся свободные зоны.
Таким образом, структура макета формируется итеративно:
Свободные области представлены прямоугольниками. Каждый прямоугольник описывается параметрами:
Пример структуры свободной области:
Space {
x: 0,
y: 0,
width: 800,
height: 600
}После размещения элемента свободное пространство делится на несколько новых областей. Например, если элемент занимает верхний левый угол контейнера, остаются две зоны:
Графически это выглядит следующим образом.
+-----------------------+
| item | |
| | space |
+------+----------------+
| space |
+-----------------------+Каждый элемент проходит несколько этапов размещения.
Алгоритм перебирает список свободных пространств и проверяет, помещается ли элемент внутри каждого из них.
Проверка выполняется по условиям:
item.width <= space.width
item.height <= space.heightЕсли условие выполняется, пространство считается кандидатом для размещения.
Если найдено несколько подходящих областей, алгоритм выбирает одну из них. В Packery используется стратегия, близкая к first-fit placement — первый подходящий участок пространства.
Дополнительно учитываются:
После выбора области элемент получает координаты:
item.x = space.x
item.y = space.yЭти координаты используются для установки CSS-позиции.
transform: translate(x, y)Именно такой подход обеспечивает высокую производительность анимаций.
После размещения элемента необходимо обновить список свободных областей.
Предположим:
space: 400 x 400
item: 200 x 200Элемент размещён в левом верхнем углу.
Оставшееся пространство делится на:
space_right
space_bottomspace_right:
x = space.x + item.width
y = space.y
width = space.width - item.width
height = item.heightspace_bottom:
x = space.x
y = space.y + item.height
width = space.width
height = space.height - item.heightПосле этого исходная область удаляется, а новые пространства добавляются в список.
В процессе деления могут появляться перекрывающиеся свободные пространства. Алгоритм Packery выполняет дополнительную очистку списка областей.
Проверяется условие:
spaceA полностью содержится в spaceBЕсли это так, меньшая область удаляется, поскольку она не несёт полезной информации.
Этот этап предотвращает накопление избыточных пространств и повышает эффективность размещения.
Свободные пространства хранятся в массиве. Для повышения эффективности поиска они сортируются.
Наиболее распространённая стратегия сортировки:
Такой порядок обеспечивает размещение элементов сверху вниз и слева направо, что соответствует естественному визуальному потоку интерфейса.
Одной из особенностей Packery является возможность инкрементального обновления макета.
При добавлении нового элемента:
Это значительно снижает вычислительную нагрузку по сравнению с полным пересчётом.
Алгоритм упаковки также используется при перетаскивании элементов.
Во время перемещения выполняется несколько операций:
Таким образом достигается эффект динамической перестройки макета.
Иногда требуется полная переработка расположения элементов. Это происходит в следующих ситуациях:
Процесс repack выполняется так:
Этот процесс аналогичен первоначальной инициализации.
Размеры элементов напрямую влияют на качество упаковки.
Наиболее эффективный результат достигается при:
Если элементы имеют случайные размеры, может возникать фрагментация пространства — большое количество мелких свободных областей.
Алгоритм Packery может работать в двух ориентациях.
Элементы заполняют пространство сверху вниз.
Контейнер увеличивает высоту при необходимости.
Используется в:
Элементы располагаются слева направо.
Контейнер расширяется по ширине.
Применяется в:
Сложность алгоритма зависит от:
В среднем время размещения одного элемента составляет:
O(n)где n — количество свободных пространств.
Оптимизации Packery включают:
| Характеристика | Сеточные системы | Packery |
|---|---|---|
| Размер элементов | фиксированный | произвольный |
| Заполнение пространства | часто остаются пустоты | минимальные пустоты |
| Перестройка макета | ограниченная | динамическая |
| Drag & Drop | обычно отсутствует | встроенная поддержка |
Алгоритм упаковки особенно важен в адаптивных интерфейсах.
При изменении ширины экрана:
В результате интерфейс сохраняет плотную компоновку без жёсткой сетки.
Внутренняя архитектура Packery включает несколько ключевых модулей:
Rect
объект прямоугольника, описывающий пространство.
Packer
ядро алгоритма упаковки.
Item
объект элемента, содержащий размеры и координаты.
Layout
система управления размещением.
Эти компоненты совместно формируют механизм вычисления и обновления макета.
Пусть контейнер имеет размер:
600 x 400Добавляются элементы:
A: 200 x 200
B: 200 x 100
C: 100 x 200
D: 300 x 100Элемент A размещается в точке:
(0,0)Свободные области:
(200,0) 400x200
(0,200) 600x200Элемент B помещается в первую свободную область:
(200,0)Область делится и создаются новые пространства.
Элемент C размещается в следующей подходящей зоне.
Элемент D занимает оставшееся место.
В результате контейнер заполняется максимально плотно без заранее заданной сетки.
Алгоритм упаковки Packery используется при разработке:
Гибкость размещения делает его одним из наиболее эффективных решений для интерфейсов, в которых элементы имеют различный размер и могут изменять своё положение во время работы приложения.