Comments 14
Постановка задачи заумная, лучше сказали бы что надо создать атлас картинок для игры или упаковать лайтмапы.
Простите, что?
Такой алгоритм часто используется для создания атласов картинок для игр или упаковки освещения. Нужно для того чтобы драйвер видеокарты не переключался каждый раз на новую текстуру для отрисовки очередного объекта.
en.wikipedia.org/wiki/Texture_atlas
en.wikipedia.org/wiki/Texture_atlas
Слишком специфичная задача, домохозяйки не поймут (и не только домохозяйки). Все-таки лучше всего подходит нарезка листа металла с наименьшим количеством отходов. Оно, так же, как и ваш пример, включает в себя описание двумерного пространства, но при этом явно указывает на то, что должно остаться минимальное число отрезков(отходов), имеющих при этом наибольшую площадь.
Вы называете читателей хабра домохозяйками?
Что-то мне подсказывало, что вы прицепитесь к этому слову )
Это принцип «проще — лучше», только не в программировании, а в изложении информации. Уровень подготовки у всех разный, а вы попытались объяснить простое явление более сложным, введя сразу кучу понятий малознакомых широкой аудитории, как то: атласы, текстуры и лайтмапы, что не соответствует правилу хорошего примера — он должен быть понятен наибольшему кругу лиц с разнообразной подготовкой и вносить ясность. Зачем плодить сущности в воображении — оперативная память у человека и без того небольшая!
Это принцип «проще — лучше», только не в программировании, а в изложении информации. Уровень подготовки у всех разный, а вы попытались объяснить простое явление более сложным, введя сразу кучу понятий малознакомых широкой аудитории, как то: атласы, текстуры и лайтмапы, что не соответствует правилу хорошего примера — он должен быть понятен наибольшему кругу лиц с разнообразной подготовкой и вносить ясность. Зачем плодить сущности в воображении — оперативная память у человека и без того небольшая!
Да домохозяйки и есть, в общем-то.
Странно, что не описан такой алгоритм: сортируем по невозрастанию. Нарезаем пространство на свободные прямоугольники сортируем их по неубыванию и по наименьшему количеству пересечений. Вставляем.
Правда он достаточно затратный, но, не о том речь, как я понимаю.
Правда он достаточно затратный, но, не о том речь, как я понимаю.
Можно поподробнее? Свободные прямоугольники — это как? Насколько я понимаю (в чем я вообще сомневаюсь), пространство в данном случае должно быть строго ограничено, тогда да, это уже другие условия.
Есть еще алгоритм MaxRects — тоже неплохо упаковывает.
Статья очень интересная. Занимаюсь схожей тематикой. Большинство статей с которыми я знакомился задействовали больше эвристику: генетические алгоритмы, имитация отжига, поиск с запретами и т.д.
При этом существуют методы поиска глобально-оптимального решения. Самый популярный из мне известных — метод ветвей и границ. Но с ним одна беда — низкая размерность задач. Хотя существуют исключительные ситуации (качественные границы) когда он может реально применяться
При этом существуют методы поиска глобально-оптимального решения. Самый популярный из мне известных — метод ветвей и границ. Но с ним одна беда — низкая размерность задач. Хотя существуют исключительные ситуации (качественные границы) когда он может реально применяться
А есть ли алгоритмы такой же задачи, но для произвольных полигонов?
Sign up to leave a comment.
Про двумерную упаковку: offline алгоритмы