Сабж: Оптимальное деление прямоугольника на мелкие прямоугольники.
Кто-то решал? как? сам писал, или что есть?

Типа, вот есть книжное издание (много прямоугольных листов такого-то габарита), и вот есть листы такого-то размера. Как "оптимально" разместить эти прямоугольники на листах. Можно для начала упростить - пусть есть лист AxB, и N одинаковых подлистов BxC (площадь N * BxC позволяет разместить). Вопрос, как оптимально разместить N подлистов (скорее, вопрос можно задать и так, какое максимальное кол. подлистов BxC можно разместить на листе AxB). Это не школьная задача, просто, я не возьмусь, но как помочь, за какую сумму задачедателю...

Есть известная математическая задача: "задача о разрезании прямоугольника"

Гугль дает много ссылок. Я по одной из ссылок посмотрел чего пишут...

Например? Обратьитесь к ребятам, которые умеют это делать?

Доб. Механику, математику этого дела как понять? Если она есть.

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

Доб. Немного упростим задачу - Возбьмем лист, на котором нужно разместить обьекты >= общей площади обьектов. Спросим себя, какова максимальная площадь (размеры) прямоугольника, заведомо вмещающего этот набор прямоугольников, желаемых к размещению на листе... Вроде бы хотя бы диапазон размеров нарисуется.. Хотя он ничего особого не даст...



Исправлено 3 раз(а). Последнее : of63, 18.11.18 23:56

Тут разве что leonid сможет пояснить. В этой задаче много разных частных случаев рассматривается. Какие-то формулы многоэтажные...

Simple777
Тут разве что leonid сможет пояснить. В этой задаче много разных частных случаев рассматривается. Какие-то формулы многоэтажные...

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

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

На раскрое плит в деревообработке такая задача - одна из основных. Думаю, для металлообработки задача тоже актуальна, но там не только прямоугольники, поэтому сложнее. Существует много программных решений для деревообработки, все довольно навороченные, все не идеальные, все позволяют делать ручную корректировку.
Дополнительные проблемы, на которые важно обращать внимание в раскрое плит: разный размер деталей, ширина пропила, ширина необрабатываемого края листа, минимальный размер детали, соблюдение ориентации рисунка (если он есть), количество одновременно разрезаемых станком листов (не всегда по одному пилят), и так далее. Программы раскроя, как правило, тоже имеют целевые функции: например, минимизация остатков, минимизация времени обработки (меньше пропилов и поворотов). При этом при жестко заданных параметрах поиск оптимальной раскладки деталей может выполняться очень долго, поэтому иногда еще настраивается оптимизация времени расчета. А вот какие именно математические алгоритмы используются, это производители не раскрывают.
Если брать полиграфию, то там, как правило, формат листа готового изделия всегда одинаковый. При этом для брошюрных макетов (книги, брошюры, тетради и т.п.) печатные листы большого формата определенным образом складываются, а потом подрезаются до нужного формата. То есть важна не минимизация отходов, а правильная компоновка страниц лица и оборота на большом формате (так называемый спуск полос). С этим хорошо справляются специализированные программы верстки. Для листовых макетов (листовки, флаеры, календари, буклеты и т.п.) расположение на печатном листе обычно задают вручную. Зачастую на одном листе совмещают макеты разного формата. Надо учитывать также: размер запечатываемой области, размеры заливок под обрезку, области для меток совмещения, цветовых шкал, меток обреза, фальцовки, биговки и прочего, совпадение набора используемых красок и послепечатной обработки для разных макетов, коррекцию реза на толщину переплета и т.д. Пусть для цифровой печати метки совмещения, шкалы и подбор макетов по используемым краскам не нужны, но остальное все равно надо учитывать.
Так что тут задача не чисто математическая.

of63
какое максимальное кол. подлистов BxC можно разместить на листе AxB

По моему, ответ совершенно очевиден: int(A/C)

Цитата:

Это не школьная задача

Естественно, это задача для дошкольного возраста, если, конечно, of63 в формулировке чего-то не напутал.

leonid

По моему, ответ совершенно очевиден: int(A/C)

5 баллов

leonid

Естественно, это задача для дошкольного возраста, если, конечно, of63 в формулировке чего-то не напутал.

+ 100500

Это платная штука
www.haitek.ru
Но есть и бесплатные варианты, доступные для реализации самому
Вечером пришлю ответ моего знакомого математика в Питере.
Там есть даже что-то типа лекции.
Еще есть текст программы на Алголе, который переписать на фокс
максимум пара часов, а то и десятков минут.

Я упростил, для начала (одинаковые малые прямоугольники), оказалось зря, (ответ очевидный, хотя не уверен, что именно INT от(отношение сторон листа и прямоугольника), каких именно сторон сторон?, почему без MIN() а если разрешено крутить прямоугольники?

Пишут, например, что есть частично платный плагин PlotCalk к корелу. Пишут также, что все просто - прямоугольники упорядочить от самого большого по площади, разместить его в центре, и далее размещать по спирали более мелкие вокруг этого самого большого, плюс ручная правилка, плюс возможность разных вариаций алгоритма, чтобы посмотреть варианты. Делать надо, пусть жизнь "жизнь покажет" Задача не кажется сложной, хотя как всегда, возможны недопонимания сложности, собственно, из-за отсутствия этого опыта использования и обратился...

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

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

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

Ответ мне от Алексея Скепко,
питерского математика, моего хорошего знакомого
Володя, привет!
Во времена моей учебы лучшей книгой по затронутому вопросу была монография Игоря Романовского "Алгоритмы решения экстремальных задач" (Из-во Наука). Дополнительным достоинством кн. является то, что все рассуждения подкрепляются алгоритмами на Алголе. Многое сейчас воспринимается наивно, однако читатель может однозначно проследить мысль автора... В 6-ой главе ($9) рассмотрена задача плоского раскроя (правда, только для прямоугольных деталей.

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

Книжку я скачал на mat.net.ua/mat/Romanovskiy-Algoritmi.htm. Если нужно, перешлю.
Тому перцу, который собирается что-то писать на эту тему очень рекомендую потратить 1 час 12 минут и посмотреть www.youtube.com
Несколько нудно, но очень подробно специалист рассказывает про свой продукт, написанный для раскроя плоского материала для мебельщиков.

Спс. Хороший у вас друг. Книжка и так качается. Перцем назвал, это комплимент вобще-то )
Ролик посмотрю, хотя уже 200г есть, нормально.

Просмотрел, докладываю, этот ролик - практическое пособие по использованию программы, показалось. И то хорошо. Понял, как это выглядит в конечном продукте, и как к этому относиться. Еще один респект автору. Нало думать, надо ли я в этом процессе деления листа на прямоугольники, ели ребята об этом могут говорить час, написав перед этим собственно "делящую" прогу... Да, понимаю )



Исправлено 1 раз(а). Последнее : of63, 20.11.18 23:08

of63
Я упростил, для начала (одинаковые малые прямоугольники), оказалось зря, (ответ очевидный, хотя не уверен, что именно INT от(отношение сторон листа и прямоугольника), каких именно сторон сторон?, почему без MIN() а если разрешено крутить прямоугольники?

Дело не в "отношении сторон", а в том что из имеющейся "площади" S никак невозможно получить более чем int(S/S1) целых частей с площадями S1.
Тут просто тупо "сократили на B" две заданные тобой площади Раз уж ты одну и ту же букву применил...

of63
Пишут также, что все просто

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

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

Исходя из практики, скажу, что для одинаковых по размеру прямоугольных макетов ничего сложного в определении их максимального количества, умещающегося на заданном формате, нет. И не надо для этого никаких навороченных программ. Там всего 2 варианта размещения, назовем их "вдоль" и "поперек". Все расчеты занимают полминуты, хоть с калькулятором, хоть тупо расположением макетов на листе в графическом редакторе.

В принципе, это можно алгоритмизировать. Берешь размеры печатного листа, отнимаешь размеры незапечатываемых полей, отнимаешь внешние отступы для меток обрезки и прочего, получаешь прямоугольник, в который надо вписать макеты. При необходимости к чистовым размерам каждого макета плюсуешь дозаливку под обрез и т.п., получаешь рабочие размеры одного макета. Далее смотришь, сколько маленьких прямоугольников вмещается в большой прямоугольник при продольном и поперечном расположении макетов.

Ну, к примеру, на листе А4 (210х297 мм) при незапечатываемых полях по 5 мм с каждой стороны получаем рабочий прямоугольник 200х287 мм. На нем можно разместить 10 визиток (стандартный размер 90х50 мм) без меток обреза и дозаливки под обрез при поперечном размещении (2х5 шт. или 180х250 мм) или 12 таких же визиток при продольном размещении (4х3 шт. или 200х270 мм). Но если еще надо метки реза поставить или между визитками оставить пространство для разрезания (что крайне редко применяют), то второй вариант уже не катит.

Вот еще
Есть демо версия чисто посмотреть,
на что может быть похожа своя собственная программа
www.orioncutting.ru

и еще
www.nipinfo.com



Исправлено 1 раз(а). Последнее : boba, 21.11.18 20:59

ry
Там всего 2 варианта размещения, назовем их "вдоль" и "поперек".

Ничего подобного. Возьмите квадрат 3*3, и попробуйте его заполнить прямоугольниками 1*2. Придется класть и вдоль и поперек.

leonid

ry
Там всего 2 варианта размещения, назовем их "вдоль" и "поперек".

Ничего подобного. Возьмите квадрат 3*3, и попробуйте его заполнить прямоугольниками 1*2. Придется класть и вдоль и поперек.

Я же про практическое применение. В теории укладывать можно разной мозаикой, хоть паркетной елочкой, но как потом разрезать тиражные оттиски? Ножницами?
Бывает и на практике часть макетов разворачивают для уменьшения расхода бумаги, но это скорее исключение, чем правило. И что-то я не слышал о применении в полиграфии программ для оптимизации раскладки. В первом вопросе вообще про книжное издание речь шла, а там не покрутишь как попало, там порядок и расположение страниц соблюдать надо. Причем в зависимости от применяемой технологии фальцовки и обрезки. А с задачей [url=https://ru.wikipedia.org/wiki/Спуск_полос]спуска полос[/url] легко справляются почти все популярные программы верстки.

Другое дело - раскрой плит или листов в производстве. Суммы экономии на уменьшении отходов там могут быть внушительными. Так что уже и покрутить можно, хотя на практике тоже далеко не всегда. Возьмем производство мебели из ламинированной ДСтП с имитацией естественной фактуры дерева. Во-первых, рисунок ориентирован, то есть уже деталь для оптимизации поворачивать нельзя. Во-вторых, раскрой на однопильном станке подразумевает совмещение линий реза. В-третьих, для каждого пропила требуется установить плиту в нужную позицию и закрепить, а это время, а время - деньги. В итоге иногда дешевле за 10 минут распилить 2 листа с меньшим полезным выходом, чем полчаса крутить один лист для экономии отходов.