[WhiteShark]

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

Алгоритм решения (по сути брутфорсовый) уже придуман. В оригинале статья на эту тему нижу
http://www.codeproject.com/Articles/...gorithm-for-bu

Для тех, кто не дружит с английским, изложу ключевые моменты хода решения по-русски.
Предполагаем, что все размеры наших прямоугольничков (если хотите bounding box'ов) известны. Для тривиального решения и отправной точки для дальнейшего поиска можно отсортировать наши прямоугольники по высоте и выстроить их смежно в ряд по убыванию. Получим примерно такую полоску как на рис. 1. Сделать это просто, но, как видно, при этом неиспользованная площадь может получиться весьма внушительной, да и от квадрата наша окаймляющая область (ОО) далека. Но, тем не менее, на данные момент это первое успешное решение и мы запоминаем его (размеры).
Далее уменьшим ширину нашей полоски к примеру на 1 единицу и попробуем разместить наши прямоугольнички на получившейся ОО. Замечу, что прямоугольнички у нас выбираются из сортированного по высоте набора. А размещать их необходимо в первую очередь как можно левее и во вторую как можно выше. Очевидно, что теперь в нашу ОО влезут не все прямоугольнички. Что мы будем делать? Правильно: мы увеличим высоту нашей ОО на единицу и попробуем произвести размещение опять. Очевидно, что увеличивать высоту ОО на единицу не самый оптимальный вариант и реальная возможность изменить первоначальное размещение появится, только когда мы увеличим высоту нашей ОО на высоту самого правого (самого низкого) прямоугольничка. Тогда он сможет встать как можно левее, но уже под первым самым высоким прямоугольником, а у нас появится сократить ширину нашей ОО на ширину переехавшего только что прямоугольника.
Производя подобные манипуляции, мы, очевидно, тестируем пригодность окаймляющих областей от низких и широких до узких и высоких. Промежуточная стадия процесса показана на рис. 2. Очевидно, что где то в середине цикла мы получим ОО наиболее близкую к квадратной, а также в какой то момент и ОО с наменьшей неиспользованной площадью.
Кроме очевидной полезности изменять размеры ОО иногда больше чем на 1 единицу, парочка других ускоряющих моментов состоит в следующем. Если площадь вновь полученной на каком то шаге ОО меньше суммарной площади всех прямоугольников, то, очевидно, её тестировать нет смысла. Также нет смысла тестировать ОО после того как ее ширина станет меньше нашего самого большого левого прямоугольника. Но это всё мелочи. Далее, по сути сложностей.
Для отображения текущего состояния дел надо в каком то виде хранить наши данные. Предлагается следующее. Размещая первый прямоугольник на текущей ОО мы получаем 4 ячейки (рис. 3), высеченные прямыми, проходящими по сторонам прямоугольника. Одна из них занятая, три остальных - пустые. Так же на это можно посмотреть как на 2 колонки и 2 ряда. Размещая следующий прямоугольник, мы, в общем случае, получаем получаем уже 9 ячеек. При чем происходит рассечение нашего первого прямоугольника на 2 занятые ячейки. Далее всё аналогично (см. рис 4), но есть тонкий момент.
При размещении каждого следующего прямоугольника необходимо действовать так: находим самую левую пустую ячейку и проверяем влезает ли в нее прямоугольник по высоте. Если нет, то проверяем, а нет ли ниже в этой же колонке еще одной соседней пустой ячейки. Допустим есть и её высоты достаточно. Тогда проверяем, что у нас с шириной: влезаем ли мы в первую ячейку по ширине и если нет, то если ли рядом правее соседняя незанятая.

Теперь внимание вопрос! Пока на ум мне пришло только представлять подобную ячейковую структуру в виде матрицы - списка списков вида ( ( (x11 y11 w11 h11) (x12 y12 w12 h12) (x13 y13 w13 h13) ) ( (x21 y21 w21 h21) (x22 y22 w22 h22) (x23 y23 w23 h23) ) ... ) Где для каждой ячейки есть координаты левого верхнего угла x y и ширина w с высотой h. Но у такой структуры на мой взгляд будет сложность во впихивании при появлении новой секущей границы нового ряда или нового столбца и сложность при поиске свободных соседей.

Жду ваших мыслей по поводу прочитанного и заданного вопроса!

[Дима_]

Задача за которую Вы беретесь весьма не простая и в то же время интересная. Я не знаю область применения Вашего случая, но в большинстве своем брутфорсовые алгоритмы здесь не применимы (время поиска растет в геометрической прогрессии). Перед тем как подбирать решение, не забудьте про существенные важные физические факторы - каким методом проводиться резка - необходимо ли учитывать ширину фрезы, карта раскроя может быть любой или, под т.н. "гильотинную резку" - то есть рез может быть осуществлен только от края до края (большинство технологических процессов в реальности рассчитываются именно так), есть ли технологический смысл оптимизировать с учетом т.н. "полезных остатков" - то вводиться некий коэффицент соотношения остатка площади, на их количество и близость их к квадрату (проще говоря выгодней оставить пол листа 1 куском под будущею оптимизацию, чем 2\3 площади нарезанных на пять кусков - которые пойдут в мусор). Сейчас может ситуация и изменилась, но несколько лет назад, хорошие вероятностные алгоритмы (с нормальным коэффицентом оптимизации к времени выполнения), можно было только купить, да и то не сами алгоритмы, а в виде библиотек. Если Вам требуется сделать не абы как - а для крупного производства - то это наверное и сейчас самый правильный метод - окупиться очень быстро на сэкономленном материале - просто этот шаг надо "грамотно" обосновать с учетом человеко-часов на Вашу разработку (причем не факт что сделаете лучше) и соотношения реальной производительности Вашего решение к уже готовому. По поводу вопроса, я при всей своей любви к лиспу не стал-бы реализовывать "основной алгоритм" оптимизации на нем (в данном случая я имею в виду автолисп, на других диалектах кстати весьма вероятно) - т.к. задача это очень ресурсоемкая, да и "велосипедов" придется написать не мало. Но повторюсь все зависит от задачи - если она не выходит за рамки Вашего примера, то никаких проблем в бутфорсировании ее автолиспом я не вижу - вводите критерии оптимальности Ваших условий, шаги изменения (перебора взаимного размещения элементов) и ищете лучший.
з.ы. чуть не забыл, если все-же автолисп - то я бы рекомендовал связаться с Елпановым Евгением, вполне возможно он сможет поделиться с Вами какой либо частью своих разработок в этой области на какой-либо основе.
з.з.ы есть вполне рабочие демоверсии коммерческого ПО, по которым Вы сможете оценить и продемонстрировать реальную производительность и эффективность оптимизации.

[WhiteShark]

Дима_, спасибо за мысли.
Задачу решаю по большей части из практического и спортивного интереса. Стоит она именно так, как я описал. То есть учёта допусков на ширину фрезы нет, а также "гильотинность" резки не важна. На данный момент целевая оптимизация - по минимуму площади на которой будет произведено размещение. Поэтому время на решение задачи в данной постановке еще вполне приемлимо для варианта полного перебора (если не ошибаюсь nlog(n)) и тут, я думаю, трудностей с ресурсами возникнуть не должно. В моем случае количество размещаемых прямоугольников - десяток другой.
Да, знаю, что существует специальное ПО. Есть оно и у меня. Но, согласитесь, удобней выделить что то непосредственно в акаде, чем забивать размеры в стороннее ПО.
Да, знаю, что Евгений Елпанов решил задачу еще более сложную по размещению фасонных деталей! Но, боюсь, там и подход абсолютно другой и намного сложнее. У меня всё таки надежда, что для прямоугольных областей всё будет доступно даже таким как я. Ну и конечно будет прекрасно, если подобные Вам мастера подключатся к решению.
Да, есть и готовые решения на других языках. В частности по ссылке. Я, конечно, не многими владею, но насколько знаю, какой то сильно более подходящей структуры в других языках тоже нет.
То, что Вы говорите, что в указанных рамках задачу решать можно и на лиспе, радует. Какую структуру представления информации выбрали бы Вы? Я подозреваю, что это один из ключевых моментов в решении и если здесь принять неоптимальное решение, то возни с кодом будет намного больше, чем могло бы быть. Да, кстати, было поздно и я забыл написать, что еще в каждом списке есть элемент, отражающий занята ячейка или нет (0 и 1 как классический вариант), то есть (x y w h 0) к примеру. Есть и другой подход из более менее простых, который, видимо, ближе по структуре к лиспу, но там не совсем понятный мне критерий размещения в ту или иную ячейку нового прямоугольника. Ознакомиться можно по ссылке http://www.blackpawn.com/texts/lightmaps/default.html
Как считаете, какой проще в реализации?

[Дима_]

Сообщение от WhiteShark Какую структуру представления информации выбрали бы Вы?

А в автолиспе кроме списков ничего и нет (задавать длинной\шириной и 1 координатой, либо координатами углов - разницы большой нет - что удобней - зависит от реализации).

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

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

Сообщение от WhiteShark Как считаете, какой проще в реализации?

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

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

В случае перебора всех вариантов (да еще и с поворотом каждой) - даже это не мало.

[gumel]

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

Вот пример реализации того о чем я говорил. Делал для себя, можно наворачивать до бесконечности. Реализовано для 3DSolid'ов - составляется спецификация, подготавливаются данные для каттинга. Ориентировано на мебель.

[alex8888]

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

[Дима_]

Сообщение от alex8888 Кто сделает такую программу - памятник при жизни!

Памятник из чего?

[WhiteShark]

Сообщение от alex8888 ... Кто сделает такую программу - памятник при жизни!

Ну вам как раз к Елпанову Евгению
Я пока изучаю толстую книжку на эту тему, так что еще нескоро

[alex8888]

Сообщение от WhiteShark Ну вам как раз к Елпанову Евгению

Боюсь он тоже не в силах помочь.

Сообщение от Дима_ Памятник из чего?

Ну уж точно не из золота У меня его просто нет


В моем случае задача сводится не только к прямоугольникам, а большей частью к разверткам конусов, отводов, переходников, много шайб и крышек, а это несколько непрямоугольные элементы . Плюс к тому же на выкройках много отверстий. Они тоже должны учитываться при раскрое.
Так что задача больше кажется невыполнимой - компьютер ведь не заставить думать и мыслить как человек. Или я не прав?

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

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

[gumel]

Х.з. что за программы:


еще:

[alex8888]

gumel
да это похоже. Узнать бы теперь что это?

[gumel]

http://nesting.astrapro.ru/
http://tehtran.com/nestf.html
http://www.haitek.ru/products/sirius.php

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

Знаю, еще у одного знакомого на работе есть ЧПУ-шная плазменная резка. Со станком идет какая то прога. В нее закидываются (грубо говоря) контур деталей и их количество, а прога сама размещает эти детали на листе.

Поэтому 100% такие программы есть, погуглите - фигурный раскрой

еще, что нашел:
http://www.exactcam.com/ru/SampleNesting.htm
http://www.tflex.ru/products/priklad/raskr/
http://softpartal-com.narod.ru/index.htm
http://www.bestdownloads.ru/soft/plotcalc/1676/

p.s. ничего не проверял