Информационный портал для профессионалов в области САПР
Вы не вошли. Пожалуйста, войдите или зарегистрируйтесь.
Форумы CADUser → Программирование → Разное → Nesting. Оптимальный раскрой листа.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Нужен алгоритм оптимального размещения различных деталей произвольной формы на прямоугольном листе заданного размера. Так же задается минимальный зазор между деталями. Точно знаю, что такие алгоритмы есть даже в объеме, но мне нужно хотя бы на плоскости. Кто что знает, помогите. Хотя бы ссылку на литературу и т.д.
Для этого есть специальные приложения, например Техтран: Раскрой.
http://www.cadmaster.ru/articles/02_teh … cutout.cfm
Посмотрите, может быть, эта программа подойдет для ваших задач.
Занимаюсь той же задачей. Предлагаю обмен информацией и опытом находок. Мне правдв необх. раскраивать лист в полосы заготовок одинакового размера. Есть алгоритм склейки - поиск оптимального раскроя со сквозными разрезами - для гильотинной рубки. Есть список литературы - кое - что нарыл в местной библиотеке.
пиши
Это так называемая NP-полная задача,
для произвольных фигур в прямоугольнике фиксированной ширины она решается только полным перебором.
Решена для фигур прямоугольного типа, кем-то, кто получил за это нобелевскую премию - "задача фанерного треста".
А вообще все алгоритмы здесь довольно серъезные и большинство скрываются разработчиками.
Про нобелевскую премию не знал, а скрываются, я бы сказал, не большинство, а все. Это понятно и правильно. Но задача по прежнему висит, и я готов заплатить, если буду уверен, что алгоритм подойдет, ну и за разумную цену для России.
Мой раскрой листа для серии найдете на сайте legorutcha.narod.ru.Я сама техолог и научила комп тому ,что сама знаю.Сейчас продумываю раскрой для единичного пр-ва.Проблема в том ,что комп может все учесть,люди не смогут в этом порядке все выполнить.Будут хватать ,что под руку попадется.
Если кто-то отыскал, просьба поделиться. Я пока нарыл, что это делается в автомате при помощи ГОДОГРАФА, т.е. алгоритма построенного на основе ТЕОРИИ ГРАФОВ. Имеется, сама книга в электронном виде по ТЕОРИИ ГРАФОВ буржуйная, но очень хорошая (с подробными примерами). Если надо могу выслать. Но там годограф придётся самому строить, разобравшись с теорией графов и правильной постановкой самой задачи под неё.
Сам пока работаю над этим. Всё сведётся к решению систем линейных уравнений при помоши матриц.
[rus]Poprobujte sdelat' poisk v Gooogle na familiju Kantorovich
imenno on reshil zadachu fanernogo tresta, a dal'she nado probovat' samomu i fil'trovat' informaciju.v godu 1992-93 ja reshal zadachu v Gomel'skom stankostrojtel'nom z-de kogda rabotal tehnologom SAPR.No reshenie bylo na bejjsike pod Iskru.Uspehov[/rus]
Присоединяюсь к реплике Стаса (Stas). Друзья, ищите книгу:
Л.В. Канторович, В.А. Залгаллер
Рациональный раскрой промышленных материалов.
Изд-во "НАУКА", Сибирское отделение
Новосибирск, 1971
Были ли более поздние издания, мне не известно. Первое издание вышло в 1951 г.
Прелюбопытный, кстати, жанр - нобелевский лауреат (по экономике) с коллегой написали книгу для заводских технологов.
- общая постановка задач о раскрое;
- линейный раскрой (прутки, трубы, профили);
- раскрой листов на прямоугольные заготовки;
- подходы к более сложным задачам раскроя листов (фигурные заготовки).
Желаю удачи.
Сдается мне, что публика сильно завышает сложность задачи. С ней справится даже не самый крутой программист.
> Алексей
Программист то справится. А вот как быть с математикой?
> Forma
Полностью согласен. Задача может быть достаточно проста с логической точки зрения для строго определенных условий - например, материал типа стекло, металл; лист прямоугольный, заготовки только прямоугольные, без учета отходов.
> Алексей
Возьми, к примеру, дерево (у которого угол между пилами волокон должен не превышать, кажется, 30 градусов), да заготовки непрямоугольные, да учет отходов. И реши. И код покажи :)
Шутка шуткой а задача на мой взгляд сложная. Ее начали активно решать в СССР еще в 30-х, когда молодой республике не хватало материала для авиастроения и на тот момент каким-то образом математики ее решили ...
А кто здесь шутит? Здесь деньги вращаются. И не малые.
> Сергей
Ага, решили эвристическим методом...
Они вместо полного перебора, отбрасывали варианты с похожими экономическими результатами.
Например, есть квадратная заготовка и квадратная деталь, причем одна, ее можно до посинения двигать по заготовке, но оптимально будет ее расположить в углу, причем нет смысла проверять, в каком именно углу будет лучше.
Я тоже решил задачу оптимального раскроя (работа у меня такая - фирма занимается художественным паркетом) могу сказать только, что не нужно искать самый оптимальный раскрой, достаточно сделать раскрой, который отличается от оптимального на заранее известный % тогда количество вариантов перебора уменьшится с геометрической прогрессии до линейной...
Короче!
Кто-нибудь может четко и ясно сформулировать задачу, входные данные и выходные, нужно ли писать именно приложение к Автокаду и т.д.
Какую задачу? Для кого? Какие данные? Резать лазером листы платины что ли? Или фанеру для "молодой республики"?
> Василий
Василий, пожалуйста, вышлите книжицу на sweetpain@mail.ru
Короче!Кто-нибудь может четко и ясно сформулировать задачу, входные данные и выходные, нужно ли писать именно приложение к Автокаду и т.д.
Что то я не понял...
Могу, как пример дать решенную мной задачу.
Есть несколько тысяч замкнутых полилиний, с дуговыми сегментами, отверстиями (один контур, внутри другого) - самой различной формы, единственное ограничение - узловых точек не более 3000. Их нужно разместить на заготовки, заранее известных размеров, причем, если заготовка заполняется не полностью, нужно делать минимальное заполнение по ширине (заготовки склеиваются из планок, можно делать заготовки уже).
Для достижения более оптимального раскроя, детали можно вращать, но только на 180гр - чтоб сохранить направление текстуры.
Заранее извесны размеры планок, из которых склеивается заготовка, нельзя допускать попадание узких кончиков деталей на стыки планок в заготовке.
Предусмотреть изменяемый зазор между деталями на заготовке, причем для мелких деталей, необходим больший зазор.
Программа должна уметь обрабатывать связанные детали - детали, которые расположены рядом, но их нельзя двигать относительно друг друга.
Все вышеизложенное должно применяться для всего чертежа - имеется несколько слоев (материалов - не больше 30) и по каждому материалу свои типоразмеры заготовок...
> Алексей
По теории графов
http://www.mtas.ru/uploads/file_44.pdf
> Евгений Елпанов
тут кто-то был готов платить за программу. вот я и спросил об этом, потому как заинтересовался
> Алексей
Обрати внимание на даты ответов и создания темы.
обратил, обратил так же, что книжка это для сетевого планирования и перевозки грузов, для размещения заготовок от нее толку мало
тут кто-то был готов платить за программу
Был готов, не за программу, за алгоритм, 3.5 года назад. Сейчас для меня задача не актуальна.
Если интересно, вот вкратце примерное (без нюансов) ТЗ на программу:
1. Быстрое размещение набора плоских деталей, различной геометрической формы, в области заданной площади, с обеспечением высокого процента заполнения и других заданных условий.
2. Параметры раскраиваемого материала: задание количества и размеров раскраиваемых полос, прямоугольные полосы, полосы произвольной формы с расположением зажимов и технологических отверстий, минимальный зазор между деталями на листе, задание раскроя на одном листе деталей нескольких типов, учет анизотропных свойств материала.
3. Задание и управление следующими параметрами деталей при раскрое: количество деталей каждого типа, приоритет деталей, возможность свободного или дискретного поворота и зеркального переворота детали, расположение мелких деталей внутри вырезов больших.
4. Возможность ручного редактирования полученных результатов, с сохранением ручных результатов при следующих итерациях.
5. Геометрия контура деталей может включать любые кривые: линии, дуги, окружности, конические сечения, сплайны и т.д.
6. Технологический расчет: задание плотности и толщины материала; расчет площади, объема и веса раскраиваемого материала, общего веса деталей, процента использования материала, веса каждой детали с отверстиями и без; получение подробного отчета стандартной и настраиваемой формы.
7. Передача геометрии деталей и сохранение полученных листов с раскроенными деталями для подготовки управляющих программ для электроэрозионных, лазерных, плазменных и других станков и машин с ЧПУ.
Повторюсь, мне сейчас это уже не нужно.
Надо решить более простую задачу: Имеется произвольный упорядоченный массив точек на плоскости. Известно, что массив точек идёт вокруг повёрнутого на произвольный угол (скажем от -30 до +30 к оси Х) прямоугольника, то с внутренней стороны, то с внешней или с внутренней или с внешней. Если соединить эти точки полилинией (ТК0, ТК1, ТК2, ... ТКn, ТК0), образуется произвольный многоугольник (линии нигде не пересекутся т.к. массив описан(вписан или вьётся вокруг прямоугольника), эта проблема уже решена). Задача состоит в том, чтобы вписать в него прямоугольник НАИБОЛЬШЕЙ ПЛОЩАДИ. Получив при этом: 1. Размерения прямоугольника. 2. Привязку X,Y любой вершины найденного прямоугольника к любой из точек массива (надо только знать к какой именно). 3. Угол наклона длинной стороны искомого прямоугольника к оси Х.
Страницы 1
Чтобы отправить ответ, вы должны войти или зарегистрироваться
Форумы CADUser → Программирование → Разное → Nesting. Оптимальный раскрой листа.
Форум работает на PunBB, при поддержке Informer Technologies, Inc
