Добрый день, славный и доблестный народ, программисты!

Есть две таблицы. Обе нужны для хранения материалов. У материалов есть свойства: цвет, тип и что самое сложное - форма (или размер?). Нужен алгоритм (или движок?), который сможет по-умному помочь конструктору со сборкой проектов (например деталей).
Умность №1 заключается во в чем: для изготовления детали потребуется лист железа размером 2х2 метра квадратной формы. А на складе валяется лист с размером 3х3. Нужно, чтоб программа "обрезала" имеющийся лист на складе (то есть 3х3 - 2х2, вычитание фигур), и запечатлела эти изменения в таблице. Более того, детали же разные, разные формы, поэтому со следующей деталей уже сложнее: она меньше размером и треугольной формы. Умность №2 заключается в следующем: робот ищет подходящий материал в таблице по форме, которую имеют материалы. И прежде всего смотрит те материалы, формы которых уже были изменены ранее. И вот, к примеру, терминатор находит тот тот самый шестигранник, оставшийся с предыдущего раза и примеряет к нему наш треугольник. Видит, что треугольник вмещается и аккуратно с краюшку отрезает квадратную область, из которой потом мастер вырежет треугольник.
Умность №3 похожая, только теперь уже с деталью круглой формы.

Нюанс №1: терминатор должен всегда отрезать квадратную область независимо от того, какой формы ему нужна деталь.
Нюанс №2: терминатор должен всегда отрезать с краюшку имеющегося листа (а не с середины), чтобы можно было потом еще отрезать от этого листа (соблюдать экономичность).

Приму любую помощь и совет, пример кода на любом языке, как вам удобно. Мне самое главное - понять принцип, логику.
И да: желательно с применением ООП, мне так легче понять будет. Ну это только желательно, а не обязательно )))

Заранее спасибо!

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

ДохтаР,
Звучит заманчиво. Только вот я понять никак не могу, как применить эту задачу к моей? У меня задача скорее из области оптимального раскроя, т.е. как найти выгодное место, чтоб отрезать. Или я не въезжаю в тему, что скорее всего так и есть

авторCryptic, у тебя только треугольники круги и прямоугольники? Или есть еще фигуры сложной (невыпуклой) полигональной формы?

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

У меня есть идея. Но прокомментируйте ее адекватность, пжлст, ув. программисты.

В таблице хранения материалов хранить двумерный массив булевского типа. Количество его элементов будет совпадать с количеством сантиметров в размерах листов материалов. Например 300x300 см. размер листа ДСП. И пока лист еще ни разу не резали, все элементы его массива будут равны true. Но как только отрезали четвертую часть, та область, которой не стало будет равна false. Тем самым форма, которая будет изменяться - фиксируется в бд.
Да кстати, еще и площади можно отнимать и записывать новое значение, чтобы по площади можно было автоматически проверять, имеет ли смысл вообще тот или иной лист кроить.

Как считаете, внес я новое слово в эту область? :)

ДохтаР, до меня сегодня ночью дошло, как применить задачу рюкзака в моей задаче. Спасибо большое за совет. Сразу и не оценил. Я уже даже нашел алгоритм в сети. Буду продолжать пляски с бубном :)

Вот тут я поместил свою схему бд, взгляните