| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Распределение прямоугольников на другом прямоуг. |
| Автор: ufna 17.7.2009, 13:39 |
| В общем, суть какая - есть прямоугольники, размеры их четко заданы. Могут быть повернуты на 90 градусов. Нужно их разместить на другом прямоугольнике, либо доказать что такого размещения нет. Я с таким типом алгоритмов не работал, не подскажете куда копать? :( |
| Автор: Lipetsk 17.7.2009, 14:57 |
| Предположим, такое размещение имеется, тогда снимая каждый раз самый левый из самых верхних прямоугольников получим последовательность прямоугольников по этой последовательности элементарно повторить размещение значит вам нужно перебрать все возможные последовательности прямоугольников и посмотреть, размещаются ли они нужным образом мне так видится ;) |
| Автор: maxdiver 17.7.2009, 21:48 |
| Ну да, только можно прямо на ходу: подбирать последовательность и сразу пытаться ставить - если дыра появляется, то текущее начало последовательности сразу отбрасываем как неподходящее. |
| Автор: скрябинъ 19.7.2009, 10:37 |
| Как заданы прямоугольники (координатами или чем-еще)? Каковы правила размещения? |
| Автор: ufna 19.7.2009, 11:18 |
| Счас пока изучаю в гугле packing problem, завтра сажусь за это дело вплотную. суть в том, что нужно размещение найти, либо доказать что его нет, с достаточно малой погрешностью. А правила - помещаемые прямоугольники не могут пересекаться, вращение допустимо только на 90 градусов. Прямоугольники заданы типом QRect  что дает быстрый доступ к любому параметру, будь то длины сторон, координаты точек, вычисление пересечения его с любым другим и т.п. |