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

Ищу практическую реализацию алгоритма или решение в алгоритмич. форме.
Помогите чем можете







p.s.
То что это NP-полная "задача о рюкзаке", то что существуют десятки статей и научных работ мне известно.
Также, я в состоянии составить greedy алгоритм, аналогичный имеющемуся на gamedev.net, но он работает
из рук вон плохо. Я не ищу исследовательские статьи и диссертации о проблеме, я не математик, мне интересна конкретика =)

Здравствуйте, Георгиевич, Вы писали:

Г>Встала задача, упаковать множество картинок в одну как можно более плотно,
Г>чтобы занимаемая площадь была минимальна.

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

Г>Встала задача, упаковать множество картинок в одну как можно более плотно,
Г>чтобы занимаемая площадь была минимальна.

Г>Ищу практическую реализацию алгоритма или решение в алгоритмич. форме.
Г>Помогите чем можете

Вот нечто попалось на глаза:
http://www.blackpawn.com/texts/lightmaps/default.html



Г>Я не ищу исследовательские статьи и диссертации о проблеме, я не математик, мне интересна конкретика =)

Судя по всему, конкретика интересует многих:
(из кеша Гугла)

=
2D-раскрой могу продать... статическую библиотеку или DLL'ку.. или софтину. есть готовая софтина выполняющая раскрой (сорцов не дам).
=
хз, уже 5 лет занимаюсь задачами раскроя разнопланового.. технологичного (там где сквозные резы), гильотинного, нерегулярного, фигурного... да, универсального решения нет, но популярные случаи учесть можно.. ну и там ко всему, одних стандартных алгоритмов не всегда достаточно, а точнее, всегда недостаточно, приходится придумывать что-то свое, а это довольно кропотливый труд. Поэтому хорошие реализации (и даже описания алгоритмов) в сети все платные.
=

Г>>Встала задача, упаковать множество картинок в одну как можно более плотно,
Г>>чтобы занимаемая площадь была минимальна.
_>а с какой практической задачей это связано? не с полиграфией случайно, где надо как можно больше мелких картинок отпечатать на большом ватмане?

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

A>Судя по всему, конкретика интересует многих:

Пол-недели ищу.
Нездоровую коммерциализацию в этой области уже отметил. Продают всё, даже статьи.

Здравствуйте, Георгиевич, Вы писали:

Г>Пол-недели ищу.
Г>Нездоровую коммерциализацию в этой области уже отметил. Продают всё, даже статьи.

Вот именно упомянутый BSP (http://www.blackpawn.com/texts/lightmaps/default.html), после некоторой доработки напильником заработал вот так:
http://antigrain.com/stuff/rect_packer_screenshot.png
Причем, до 30 тысяч точек характеристика почти линейная: http://antigrain.com/stuff/rect_packer.png

Там нет абсолютно ничего сложного, просто сортировать прямоугольники надо по высоте-ширине и пытаться укладывать их сначала по впрево и если не лелет — уже вверх. А сортировать по площади — это глупость. есть еще несложные алгоритмические ухищрения для ускорения.

Здравствуйте, Георгиевич, Вы писали:

Г>Встала задача, упаковать множество картинок в одну как можно более плотно,
Г>чтобы занимаемая площадь была минимальна.

Г>Ищу практическую реализацию алгоритма или решение в алгоритмич. форме.
Г>Помогите чем можете


Г>p.s.
Г>То что это NP-полная "задача о рюкзаке", то что существуют десятки статей и научных работ мне известно.
Г>Также, я в состоянии составить greedy алгоритм, аналогичный имеющемуся на gamedev.net, но он работает
Г>из рук вон плохо. Я не ищу исследовательские статьи и диссертации о проблеме, я не математик, мне интересна конкретика =)

Здесь решали: http://zcontest.ru/2006.02/zris.php
Исходники лучших решений там же )

А>Вот именно упомянутый BSP (http://www.blackpawn.com/texts/lightmaps/default.html), после некоторой доработки напильником заработал вот так:
А>http://antigrain.com/stuff/rect_packer_screenshot.png
А>Причем, до 30 тысяч точек характеристика почти линейная: http://antigrain.com/stuff/rect_packer.png
А>Там нет абсолютно ничего сложного, просто сортировать прямоугольники надо по высоте-ширине и пытаться укладывать их сначала по впрево и если не лелет — уже вверх. А сортировать по площади — это глупость. есть еще несложные алгоритмические ухищрения для ускорения.

Кто этот "Аноним" мог быть, кроме как McSeem =)
..Так вот вот ты чем занимался =) я тебе кстати отправил письмо по адресу указаному у тебя в инфо здесь на борде, ждал ответа. Представляешь, как раз, вторым письмом планировал спросить, не сталкивался ли ты с этой задачей. =)

...Насчет этого алгоритма.
Насколько я понял, здесь иная задача — дана готовая площадь (скорее всего 256x256) и требовалось разложить прямоугольники, чтобы не раскладывать вручную.

Оригинальная же задача имеет на входе набор прямоугольников, и алгоритм должен скомпоновать их так, чтобы результирующий bounding rectangle получился как можно меньше, потери именно ПЛОЩАДИ (читай — остатков материала при раскрое) как можно меньше. Прямоугольник в котором все это будет лежать как раз в начале не определен и должен быть установлен.

Если внимательно присмотреться к картинкам на http://www.blackpawn.com/texts/lightmaps/default.html то там видны белые промежутки между прямоугольниками — это он показал зазоры. Они хаотично раскиданы, и визуально глазу кажется что всё отлично, все площадь заполнена. Но на самом деле этих "зазоров" у него легко набежит до ~10%-15% и более.

Когда прямоугольники мелкие и их много, они "засыпают" площадь. С ними проще. Чем они мельче, тем лучше будут результаты. Они словно мелкий песок, хорошо повторяют форму "банки". Однако, когда есть всего лишь несколько (~20-30шт) "корявых" прямоугольников — вот тут-то и начинаются трудности.

p.s.
Но скажу, что меня твое решение (скриншоты на antigrain'е) порадовали. Действительно, все красиво разложено. Как будто так и росло =) Поделись уж доработками. Любопытно.

В дополнение.

Статья про упаковку Lightmaps была даже переведена,
Packing_Lightmaps

А по поводу последних работ по поиску наиболее оптимального заполнения я наконец нашел вот что (только нашел, еще особо не вычитывал). "A new heuristic algorithm for rectangle packing" http://portal.acm.org/citation.cfm?id=1236134
Статья платная, текста нет. Зато указаны цитируемые статьи. Я с трудом нашел текст статьи, но увы без изображений. http://findarticles.com/p/articles/mi_qa5473/is_200708/ai_n21296600/pg_1

Судя по всему, "самая мода" в данной области — привлекать для решения задачи генетический алгоритм.

Г>Я с трудом нашел текст статьи, но увы без изображений.
Г>http://findarticles.com/p/articles/mi_qa5473/is_200708/ai_n21296600/pg_1

Вот тут посмотрите:
http://paper.ijcsns.org/07_book/200612/200612A17.pdf

Здравствуйте, Георгиевич, Вы писали:

Г>Встала задача, упаковать множество картинок в одну как можно более плотно,
Г>чтобы занимаемая площадь была минимальна.

Г>Ищу практическую реализацию алгоритма или решение в алгоритмич. форме.
Г>Помогите чем можете

Г>p.s.
Г>То что это NP-полная "задача о рюкзаке", то что существуют десятки статей и научных работ мне известно.
Г>Также, я в состоянии составить greedy алгоритм, аналогичный имеющемуся на gamedev.net, но он работает
Г>из рук вон плохо. Я не ищу исследовательские статьи и диссертации о проблеме, я не математик, мне интересна конкретика =)

Коллеги, здравствуйте!

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

Более формально... Есть набор пропорций прямоугольничков. Т.е. пусть дано 1:3, тогда можно получить как 10x30 так и 1500x500. Нужно оптимально замостить прямоугольную область, причем красиво , т.е. вариант одна большАя картинка, а все остальные сжатые не подходит. Очень интересно Ваши соображения и, может кто-то знает какие-нибудь серьезные статьи\материалы по этой теме?

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

С уважением, О.О.

А>Столкнулся с аналогичной проблемой, но только картинки можно растягивать и нужно минимизировать свободное место в некотром прямоугольнике.
А>Более формально... Есть набор пропорций прямоугольничков. Т.е. пусть дано 1:3, тогда можно получить как 10x30 так и 1500x500. Нужно оптимально замостить прямоугольную область, причем красиво , т.е. вариант одна большАя картинка, а все остальные сжатые не подходит. Очень интересно Ваши соображения и, может кто-то знает какие-нибудь серьезные статьи\материалы по этой теме?
А>Вариант наклепать всевозможные прямоугольники, получаемый из пропорций, а потом свести задачу к задаче с фиксированными размерами не эффективен..

У меня задача стояла размещать автоматом и оптимально, ибо порой глифов оч много. О красоте речь не шла, потому что порой автомат раскладывает совершенно на глаз хаотично, зато оптимально. Когда я слышу о "красоте" — тут сразу отпадают тупые оптимизационные машинные алгоритмы и на ум приходит полу-автоматическая работа в паре человек-машина.
Нельзя ли делать полуавтоматически — т.е. раскладывает человек мышкой при помощи машины? Т.е. быстрый сдвиг пере-упорядочивает прямоугольники (раз можно можно/нужно масштабировать — это скорей всего для визуального эффекта..)

А вообще, я хотел раньше в данную тему вернуться, и сказать что откопал единственного человека, реального ученого занимающегося этой проблемой, единственного среди всех этих гамадрилов, продающих статьи и алгоритмы.
Имя ему — David Pisinger. Сайт http://www.diku.dk/~pisinger/codes.html

Здравствуйте, Георгиевич, Вы писали:

А>>Столкнулся с аналогичной проблемой, но только картинки можно растягивать и нужно минимизировать свободное место в некотром прямоугольнике.
А>>Более формально... Есть набор пропорций прямоугольничков. Т.е. пусть дано 1:3, тогда можно получить как 10x30 так и 1500x500. Нужно оптимально замостить прямоугольную область, причем красиво , т.е. вариант одна большАя картинка, а все остальные сжатые не подходит. Очень интересно Ваши соображения и, может кто-то знает какие-нибудь серьезные статьи\материалы по этой теме?
А>>Вариант наклепать всевозможные прямоугольники, получаемый из пропорций, а потом свести задачу к задаче с фиксированными размерами не эффективен..

Г>У меня задача стояла размещать автоматом и оптимально, ибо порой глифов оч много. О красоте речь не шла, потому что порой автомат раскладывает совершенно на глаз хаотично, зато оптимально. Когда я слышу о "красоте" — тут сразу отпадают тупые оптимизационные машинные алгоритмы и на ум приходит полу-автоматическая работа в паре человек-машина.
Г>Нельзя ли делать полуавтоматически — т.е. раскладывает человек мышкой при помощи машины? Т.е. быстрый сдвиг пере-упорядочивает прямоугольники (раз можно можно/нужно масштабировать — это скорей всего для визуального эффекта..)

Г>А вообще, я хотел раньше в данную тему вернуться, и сказать что откопал единственного человека, реального ученого занимающегося этой проблемой, единственного среди всех этих гамадрилов, продающих статьи и алгоритмы.
Г>Имя ему — David Pisinger. Сайт http://www.diku.dk/~pisinger/codes.html

Мне тоже нужно в автоматическом режиме. Вообще смысл — размещать фотографии при печати. Т.е. "красивость" обусловлена желанием, чтобы все фотографии были видны (ну т.е. чтобы не было крайнего случая когда есть фотка 2x2 пикселя и есть фотка 1000x1000 пикселей).

За сайт спасибо

Здравствуйте, <Аноним>, Вы писали:

А>Более формально... Есть набор пропорций прямоугольничков. Т.е. пусть дано 1:3, тогда можно получить как 10x30 так и 1500x500. Нужно оптимально замостить прямоугольную область, причем красиво , т.е. вариант одна большАя картинка, а все остальные сжатые не подходит. Очень интересно Ваши соображения и, может кто-то знает какие-нибудь серьезные статьи\материалы по этой теме?
Тут очень много варьируемых параметров — помимо положения каждого прямоугольника, у нас есть еще и его масштаб.
При этом понятие "красоты" сводится к ограничениям на разброс масштабов. Это если пренебречь естественным желанием сделать побольше масштаб фотографий молодых, а родственники и в малом масштабе сгодятся

Лично мне задача кажется плохо разрешимой. В том смысле, что только масштабирования — недостаточно. Мы, когда делали альбом, делали так:
1. Придумали несколько "раскладок", которые разрезали страницу альбома на несколько более-менее подходящих прямоугольников
2. Подбирали фотографии под эти раскладки, интенсивно пользуясь инструментом crop (который заодно и исправлял нам масштаб)

В "обратную сторону" можно применить такие соображения:
1. Посмотреть, каково количество различных пропорций. Предполагаем, что их немного по сравнению с количеством фотографий. Например, 1:3, 3:4, 4:3.
2. Попробовать сконструировать композитные блоки, которые удовлетворяют ограничениям на разброс масштабов. Способов композиции — всего два:
а) склеивание двух прямоугольников по вертикали:

+----+--+
|    |  |
|    |  |
+----+--+

и то же самое по горизонтали.
б) склеивание блока из 4х прямоугольников с дыркой посреди:

+---+------+
|   |      |
|   +--+---+
|   |  |   |
+---+--+   |
|      |   |
+---+--+---+

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

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

OO>Мне тоже нужно в автоматическом режиме. Вообще смысл — размещать фотографии при печати. Т.е. "красивость" обусловлена желанием, чтобы все фотографии были видны (ну т.е. чтобы не было крайнего случая когда есть фотка 2x2 пикселя и есть фотка 1000x1000 пикселей).
OO>За сайт спасибо

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

У вас задача совсем иная, она связана с человеческим восприятием (вы это называете "красотой"). Это восприятие должно быть максимально гармоничным.
Как сделать восприятие гармоничным? Почитайте про так называемое понятие "композиции" у художников (композиция третями, композиция диагоналей). Почитайте про золотое сечение.

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

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

Здравствуйте, OlegOl, Вы писали:

Г>>А вообще, я хотел раньше в данную тему вернуться, и сказать что откопал единственного человека, реального ученого занимающегося этой проблемой, единственного среди всех этих гамадрилов, продающих статьи и алгоритмы.
Г>>Имя ему — David Pisinger. Сайт http://www.diku.dk/~pisinger/codes.html

OO>Мне тоже нужно в автоматическом режиме. Вообще смысл — размещать фотографии при печати. Т.е. "красивость" обусловлена желанием, чтобы все фотографии были видны (ну т.е. чтобы не было крайнего случая когда есть фотка 2x2 пикселя и есть фотка 1000x1000 пикселей).

Который раз убеждаюсь, что "все уже украдено до нас"
Я сейчас стою перед аналогичной задачей. OlegOl, ты нашел что то по этой теме?