Распределение прямоугольников в прямоугольнике Опции

[ufna]

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

Я с таким типом алгоритмов не работал, не подскажете куда копать?

[AD]

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

Я с таким типом алгоритмов не работал, не подскажете куда копать?

Суть такая: следует проверить, входит ли один прямоугольник в другой или же нет! Такие операции есть у QRect в Qt. Или же Вам надо самому это реализовать?

[ufna]

Вы неправильно поняли суть проблемы - мне нужно проверить не входит ли один в другой. Мне нужно поместить некоторое количество прямоугольников в другой, а не узнать находятся ли они в нем (работаю как раз с QRect).

На другом форуме подсказали что это сие есть packing problem, копаю в эту сторону.

[Kagami]

Грубую оценку можно получить сравнив сумму площадей упаковываемых прямоугольников с площадью контейнера. Можно ввести коэффициент достоверности (0,8-0,9) и умножать сумму площадей на него, что слегка повысит точность оценки.
А так задачу скорее всего придется решать полным перебором, пока не будут опробованы все варианты или не будет найдено первое подходящее решение.

[Litkevich Yuriy]

либо доказать что такого размещения нет.

т.е. помещаются ли они в заданный?
И по условию непонятно, как помещаемые прямоугольники, собственно помещаются. Рядом, один в другой или накладываясь друг на друга.

А вообще задача должна быть решена програмным путём, или аналитически?

[ufna]

Да, либо нужно размещение найти, либо доказать что его нет, с достаточно малой погрешностью.

Помещаемые прямоугольники не могут пересекаться, вращение допустимо только на 90 градусов.

Решение нужно программное, т.к. это цель автозаполнителя поля.

[Tonal]

Нужно разместить все или можно не все?
Важен только факт возможности размещения или само размешение тоже важно?
Если важно размещение и можно разместить несколькими способами какое использовать?
Если можно разместить не все, то какое из размещений будет лучшим?

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

Сообщение отредактировал Tonal - 21.7.2009, 7:21

[Litkevich Yuriy]

вообще было время, когда я учился на машиностроительном факультете. Имя преподователя я сейчас не вспомню, но он посвятил всю жизни изучению вопроса "об оптимальном раскрое листовых заготовок" я думаю это можно взять за ключевые слова для сёрфинга по интернету.
Насколько я помню существует аналитическое решение этой задачи для любых фигур состоящих из примитивных (непомню как они строго называются, толи какого-то рода, толи какого-то порядка)

[kwisp]

Задача решается полным перебором,

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

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

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

Сообщение отредактировал kwisp - 21.7.2009, 14:34

[ufna]

Закопался в эту задачу, тут нужна нехилая математика. Фишку эту требовал заказчик, т.к. в программе-"идейном вдохновителе это было". Короче, про математику не буду, там разные варианты есть, в том числе и перебор. Нашел кое-что на эту тему, только на С#, если кому интересно, могу поделиться.

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

Всем спасибо, т.к. заставили много думать над идеями