Abstract

Abstract

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

Full Text

Важным направлением снижения себестоимости продукции является оптимизация производства [1, 2]. Для проведения такой оптимизации во многих отраслях промышленности необходимо решение класса задача раскроя-упаковки. Данным задачам посвящено множество научных работ как отечественных [3, 4, 5], так и зарубежных [6, 7, 8] авторов. В существующих работах описывается много алгоритмов, которые позволяют находить достаточно хорошие решения. Однако во всех работах рассматриваются детали, представленные в удобном для алгоритмов виде. На практике чертежи деталей разрабатываются в отдельных CAD-системах, таких как AutoCad, Kompas и аналогичных. После чего данные чертежи загружаются в программную систему, выполняющую автоматический раскрой материала. Таким образом, возникает задача преобразования информации о детали, полученной из файла чертежа, в формат данных, удобный для алгоритмов. Все алгоритмы раскроя требуют информацию о внешнем контуре детали, заданную последовательным обходом элементов контура по или против часовой стрелки. Кроме того, деталь может содержать отверстия; существует ряд алгоритмов, которые могут размещать детали внутри этих отверстий, для таких алгоритмов также необходима информация и об отверстиях в деталях. В данной статье будут описаны два основных алгоритма преобразования информации, получаемой из чертежей, в информацию, необходимую для алгоритмов раскроя материала. Информацию о чертежах в систему раскроя материала, как правило, передают в файлах формата dxf, так как данный формат является открытым, а для его чтения существуют свободно распространяемые бибилиотеки, например библиотека kabeja [9]. Из чертежей данного формата можно получить информацию о примитивах, из которых состоит объект. В данной статье будут рассматриваться только следующие примитивы: - прямая; - дуга; - окружность. Данные примитивы встречаются наиболее часто, и в большинстве случаев имеет смысл рассматривать только их. Будем считать, что рассматриваемые контуры не самопересекаются, не пересекаются друг с другом и являются замкнутыми. Для получения необходимой информации о чертежах по примитивам необходимо выполнить следующие два шага: 1. Выделить все контуры детали. 2. Разделить контуры на внешний (внешняя граница детали) и внутренний (отверстия внутри детали). Выделение контуров деталей. На первом шаге заметим, что окружность является замкнутым контуром, поэтому сразу добавим окружности в список контуров и исключим их из списка рассматриваемых примитивов. Блок-схема алгоритма выделения контуров приведена на рисунке. Рис. Блок-схема алгоритма выделения контуров Шаги, обозначенные на блок-схеме, рассмотрим более подробно. Шаг 1. Выбрать любой примитив из списка. Любой из концов примитива выбрать как текущую точку. Другой конец примитива выбрать как начальную точку. Исключить данный примитив из списка. Шаг 2. Найти в списке примитивов тот, один из концов которого сопадает с текущей точкой. Выбрать другой конец примитива как текущую точку. Исключить примитив из списка. Шаг 3. Если начальная и конечная точка не совпадают, то вернуться к шагу 2, иначе выбранные на шагах 1–2 примитивы являются замкнутым контуром, а порядок, в котором они выбирались, соответствует порядку обхода по или против часовой стрелки. Шаг 4. Добавить полученный контур к списку контуров. Шаг 5. Если остались нерассмотренные примитивы, перейти к шагу 1, иначе – конец алгоритма. Необходимо отметить, что чертежи могут быть выполены не совсем точно, и точки, которые автор чертежа считает совпадающими, с точки зрения ЭВМ могут находится на небольшом расстоянии. Поэтому при определении совпадения точек необходимо использовать достаточно большую погрешность, например, порядка 0,1 мм. Предложенный алгоритм имеет квадратичную сложность от числа примитивов. С учетом того, что число примитивов на практике имеет порядок не больше десятки, время работы алгортма оказывается совсем незначительным и измеряется сотыми долями секунды. Разделение контуров на внутренние и внешние. Внутренним будем считать контур, который целиком лежит внутри какого-то другого контура. Тогда внешним будет контур, который не лежит ни в каком другом контуре. Так как контуры не пересекаются, следовательно, если один контур лежит внутри второго, то и любая точка, принадлежащая первому контуру, лежит внутри второго. Поскольку любой контур может быть описан невыпуклым многоугольником с достаточной степенью точности, то для проверки принадлежности точки контуру можно применить известный алгоритм проверки принадлежности точки невыпуклому многоугольнику, основанный на теореме Жордана [10]. Данный алгоритм можно описать следующими шагами. Шаг 1. Провести из проверяемой точки луч в произвольном направлении. Обычно для упрощения дальнейших расчетов выбирается направление одной из осей. Шаг 2. Посчитать количество пересечений луча и многоугольника. Если данное количество нечетное, точка лежит внутри многоугольника, иначе – вне его. Сам же алгоритм разбиения контуров на внутренние и внешние выглядит следующим образом: Шаг 1. Выбрать произвольный контур, считать его внешним. Шаг 2. Последовательно рассматривать оставшиеся контуры и проверять, лежит ли внутри них контур, который на текущем шаге считаем внешним. Если да, то текущий рассматриваемый контур считать внешним. Тот контур, который после выполнения данного алгоритма остался внешним, и является внешним для детали, все остальные – отверстиями. На практике чертежи могут содержать ошибки, поэтому необходимо рассмотреть три следующие исключительные ситуации: 1. Контур имеет самопересечения или несколько контуров пересекаются. Данную ситуацию можно распознать по одному из следующих признаков: - существуют пересекающиеся примитивы; - из одной точки выходит более двух примитивов. 2. Имеется незамкнутый контур. Ситуация возникнет, если в процессе выделения контуров текущая и начальная точки не совпадают и не осталось нерассмотренных примитивов. 3. Имеется несколько внешних контуров. Ситуация возникает, если после разбиения контуров на внутренние и внешний имеется контур, который не лежит внутри внешнего контура. Предложенные в данной статье подходы позволяют получить описание деталей в виде, удобном для абсолютного большинства алгоритмов раскроя материала. Рассмотренные алгоритмы реализованы и успешно функционируют в системе раскроя материала Itas Nesting.