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

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

к алгоритму раскроя задача не имеет отношения

прямоугольники ориентированные или нет?
вращаться могут?

для упрощения считаем, что вращаться не могут и все они нормально ориентированы X-Y

(3) тогда простейший (тупейший) алгоритм это найти все "свободные" незанятые максимальные прямоугольники
с отбрасыванием в процессе поиска всех вписанных в другие

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

и затем перебор всех этих отрезков с построением прямоугольников из них (валидных)

(0) а из ДО уже бы перенес это дерево иппучее и всё бы работало...

Вдруг на мысль натолкнёт
http://catalog.mista.ru/public/267268/

(0) Хорошая задачка! Пространственное воображение поднапрячь надо.

пока пришел к выводу, что алгоритм нужен многопроходный.

проблемы возникают со скоростью расчета когда на канве уже размещены 200 или более элементов, по этому и нужен алгоритм основанный на теории а не на переборе

(8) вроде даже одномерный рюкзак решается перебором, а 2D тем более. Теория тут только поможет оптимизировать алгоритмы.
имхо

если задача просто "найти куда засунуть еще один прямоугольник"
то можно через окружности и "гравитацию" делать

пусть каждый из уже размещенных элементов создает "силу тяжести" в своем центре

тогда точки поля где наименьшая "сила тяжести" с большой вероятностью свободны, можно их проверять на вписывание

и если в некоторой окружности (куда вписывается наш прямоугольник) "сила тяжести" меньше некоторой величины то точно влезет

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

(10) небольшое уточнение
это алгоритм хорош только для прямоугольников близким к квадратным

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

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

Навскидку можно вот такое решение предложить.
Берем заданный прямоугольник (который нужно поместить). Рассматриваем его в паре со всеми уже размещенными. Таким образом находим прямоугольники, куда нельзя поместить верхний левый угол нового. Это будет прямоугольник с длинами сторон - суммами длин прямоугольников пары, с фиксированным правым нижним углом. В итоге получаем множество прямоугольников, закрывающих плоскость. Нам нужно определить незакрытые ни одним прямоугольником места. Что-то вроде Z-буфера.
Но и без этого понятно, что ответ даст сканирование по строкам (или столбцам, а как лучше? - лучше всего по рандому, чтобы проигрыш в худшем случае минимизировать).
При сканировании по строке нужно будет объединять отрезки в интервалы, чтобы найти свободные. Это уже известные алгоритмы. Обычно бинарное дерево в этом случае используется.
Но дерево можно с предыдущей строки уточнять..., поэтому все же лучше сразу смотреть алгоритм на тему покрытий прямоугольниками и определение не покрытых точек.

В общем, нужно еще подумать.

(0) - Размер прямоугольника который надо поместить известно? Прямоугольник может быть внутри другово прямоугольника(Проверять только пересечение линий?)?

(0) - А так RectF со всеми прямоугольниками, циклом справа на лево, и сверху в низ, с определеным заданным шагом. Если есть пересечение с другим прямоугольником то можно сдвинуть на область пересечения и опять проверить со всеми прямоугольниками.

(14) задача не в том, что бы разместить как можно больше, а в том, что бы разместить красиво.

(13) практический смысл - реализация структуры компании в графическом виде

(15) для начала нужно определить в числах, что есть красиво

пока буду пробовать такой алгоритм

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

(15) Ага, тогда ваша задача это все-таки "упаковка". То есть имеется последовательность шагов. И нужна структура данных, которая будет это поддерживать. В (6) уже указали на похожую проблему. Можно применить в точности тот же алгоритм (и структуры данных), взяв короб толщиной в сантиметр. Будет работать. В (17) похожий подход.

Но, возвращаясь к исходной задаче, можно посмотреть https://toster.ru/q/240609 и http://sis.khashaev.ru/2013/july/b-prime/BHLNY5WzX-Q/ . Идею про сжатие координат.
То есть все оказывается проще.
1) находим множество "запретных" точек, в которые нельзя поместить верхний левый угол. Это множество будет состоять из N "расширенных" по идее из (13) прямоугольников, которые могут пересекаться.
2) находим проекции их сторон на Х, на Y. Далее комбинируем все пары проекций. И смотрим, входит ли центр пары в один из "запретных" прямоугольников. Если нет - то это часть ответа.
Все очень просто. Для 200 прямоугольников можно и О(N^3) обойтись.

(15) "практический смысл - реализация структуры компании в графическом виде"
месье знает толк в извращениях

(15) Тогда может не размещать прямоугольники, а делить существующие на более мелкие?

(20) пробовал, не выходит из-за неопределенности возникающей на более низких уровня обхода дерева

(21) А какая там неопределенность? Или у вас не строго иерархическая структура?

Можно ввести "виртуальные" уровни иерархии, куда искусственно группировать подразделения. Чисто для красоты.

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

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

(25) походу не отделы внутри групп, а группы внутри отделов

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

(26) + а если групп много то не влезшие снаружи отдела рисуются

ЗЫ может не выделываться с автоматическим размещением и сделать полуавтомат?

т.е. комп выводит объекты на форму (подразделения, отделы, группы и т.д.) согласно структуре в виде дерева сверху вниз
или вообще как получится
связанные стрелками

далее человек перетаскивает объекты как ему больше нравится, при этом стрелки и форма (размеры) объектов подгоняется автоматически

(27) Зачем так сложно? Есть же старая добрая SequoiaView, в которой чудесно отображается иерархическая структура внутри прямоугольника http://i030.radikal.ru/0810/33/bf1fa430d030.jpg

(15) что такое "красиво"?

(28) насчет это старой доброй не знаю
но вообще то это да, можно просто найти и заюзать нечто внешнее готовое

http://www.fox-manager.ru/fox-manager-orgstruktura.html
http://mymanager.com.ua/bp/bs/overview/organizational_structure.php
http://www.orgplus.com/