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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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