Определение траектории режущего инструмента с отсутствием пересечения резов

Т.А. Макаровских,
 доц., к. ф.-м.н., kwark@mail.ru
А.В. Панюков,
 проф., д-р. ф.-м.н., проф., paniukovav@susu.ac.ru
НИУ ЮУрГУ, г. Челябинск

При технологической подготовке процесса раскроя возникают различные ограничения на траекторию движения режущего инструмента, в частности: отрезанная от листа часть не допускает разрезаний; не допускается самопересечения траектории резки. В статье предложен полиномиальный алгоритм построения самонепересекающегося OE-маршрута в плоском эйлеровом графе, являющемся гомеоморфным образом раскройного плана. Алгоритм состоит в преобразовании графа в 4-регулярный плоский эйлеров граф применением расщепления вершин на k искусственных вершин и введения k искусственных ребер, инцидентных полученным после расщепления вершинам и образующим цикл. Далее в полученном графе строится AOE-цепь, которая будет искомым самонепересекающимся OE‑маршрутом после стягивание в ней искусственных ребер и инцидентных им искусственных вершин, полученных при расщеплении вершины.

 

The technological support of cutting process often deals with different restrictions on cutter trajectory, particularly, the part cut off a sheet does not require additional cuts; the trajectory should avoid intersections of the cuts. The polynomial algorithm for constructing of non-intersecting OE-trails for a plane Eulerian graph being the homeomorphic image of the cutting plan is considered in this paper. Algorithm works by transforming the initial graph to a plane 4-regular Eulerian graph. This transformation needs splitting of the vertices to k fictive ones and adding of k fictive edges incident to these vertices. These edges form a cycle. Then an AOE-trail is being constructed for the graph obtained. This trail is to be the non-intersected OE-trail for the initial graph after absorbing all the fictive edges and vertices obtained while splitting vertices of initial graph.

Введение

Развитие автоматизации производства привело к появлению технологического оборудования с числовым программным управлением, используемого для резки листовых материалов. Новые технологии позволяют осуществлять вырезание по произвольной траектории с достаточной для практики точностью. Снятие требования резки только сквозными прямолинейными резами позволяет существенно снизить отходы материала. Технологии ECP и ICP за счет возможности совмещения границ вырезаемых деталей позволяют сократить расход материала, длину горячей резки, и длину холостых проходов [1]. Проблемы уменьшения отходов материала и максимального совмещения фрагментов контуров вырезаемых деталей решается на этапе составления раскройного плана. В статье дано решение проблемы маршрутизации при вырезании деталей, когда на маршрут движения режущего инструмента наложены дополнительные технологические ограничения: отрезанная от листа часть не требует дополнительных разрезаний [2, 3] и отсутствуют пересечения имеющихся резов [4].

1. Основные определения и обозначения

Моделью раскройного листа будем считать плоскость S, моделью раскройного плана – плоский граф G с внешней гранью  на плоскости S. Для плоского графа G далее через  будем обозначать множество его ребер, представляющих плоские жордановы кривые с попарно непересекающимися внутренностями, гомеоморфные отрезкам. Через  обозначим множество граничных точек этих кривых.

Топологическое представление плоского графа  на плоскости S с точностью до гомеоморфизма определяется заданием для каждого ребра  следующих функций [3]:

1.  ,  – вершины, инцидентные ребру e;

2.   – грань, находящаяся справа при движении по ребру e от вершины  к вершине , ;

3.   – ребро, инцидентное грани  и , ;

4.   –  ребро, инцидентное грани  и , .

Поскольку функции ,  , , , , построенные на ребрах графа , для каждого ребра определяют инцидентные вершины, инцидентные грани и смежные ребра, то справедливо следующее

Утверждение 1. Функции ,  , , ,  построенные на ребрах графа  определяют плоский граф  с точностью до гомеоморфизма.

Далее будем считать, что все рассматриваемые плоские графы представлены указанными функциями. Пространственная сложность такого представления будет .

В дальнейшем будем использовать ряд понятий, определения которых имеется в работах [5] – [9]. В [4] доказаны следующие теоремы.

Теорема 1. Если в плоском графе G графе существует A-цепь, то существует и AOE-цепь.

Теорема 2. В плоском связном 4-регулярном графе G существует AOE-цепь.

Определение 1. Рангом ребра [2] будем называть значение функции , определяемую рекурсивно: пусть  – множество ребер, ограничивающих внешнюю грань  графа , тогда ; пусть  – множество ребер ранга 1 графа  тогда .

Ранг ребра определяет его удаленность от внешней грани и показывает, какое минимальное число граней необходимо пересечь, чтобы добраться от внешней грани  до этого ребра.  Это позволяет для определения ранга использовать граф , топологически двойственный исходному графу : множеством вершин графа  является множество F граней графа G, а ребрам графа  соответствует наличие между двумя гранями границы ненулевой длины, т.е. ребра .

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

Различные способы вычисления значений функции  приведены в работах [9, 10]. Вычислительная сложность определения ранга для всех ребер графа не превосходит .

В [11] введено следующее определение и приводятся следующие утверждения.

Определение 2. Суграф  графа G, для которого  назовем суграфом ранга k.

Предложение 1. Вершина, инцидентная четырем ребрам, смежным внешней грани, является точкой сочленения.

Предложение 2. Внешняя грань суграфа  является объединением всех граней ранга k в графе G.

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

2. Алгоритм построения АОЕ-цепи в графе

Приведённый далее алгоритм AOE-TRAIL накладывает достаточно жесткие ограничения на граф: требуется отсутствие точек сочленения для всех суграфов  . Тем не менее, если предварительно «правильно» расщепить все точки сочленения суграфов , то в результате расщепления получим граф, у которого любой суграф  не содержит точек сочленения. Под «правильным» будем понимать переход между дугами, соответствующими циклическому порядку и инцидентными различным парам граней [4].

АЛГОРИТМ CUT-POINT-DELETING

Input: плоский связный 4-регулярный граф , представленный для всех  функциями , .

Output: гомеоморфный образ графа , представленный для всех  функциями , , в котором любой суграф  не имеет точек сочленения.

Промежуточные данные: : массивы , , ;  : массив .

Initiate():// Инициализация

for    ; ;

Ranking (G); //Определение ранга всех вершин, ребер и граней графа

Finding():// Поиск

for  do

   

enddo

for  do

; ;

if ( ) then   else ;

;

if ( ) then , ;

if ( ) then , ;

if ( ) then ,

if ( ) then

if (( and ) or (  and )) then

, , ,

, ;

else

, , ,

, ;

enddo

Конец алгоритма

 

Очевидно, что вычислительная сложность алгоритма не превосходит .

Приведем описание алгоритма, который позволяет построить AOE-цепь в любом плоском связном 4-регулярном графе G, любой суграф  которого не имеет точек сочленения [4,11].

 

АЛГОРИТМ AOE-TRAIL

Input: плоский связный 4-регулярный граф  без точек сочленения; начальная вершина .

Output:  – выходной поток, содержащий построенную алгоритмом цепь, удовлетворяющую ограничениям.

Initiate(G, ); // Инициализация

Ranking(G); // Ранжирование

Constructing (v); // Построение цепи

Конец алгоритма

 

ПРОЦЕДУРА Constructing (v)

; ;

do {

if ( ) REPLACE(e);

Trail << v << e;

; counter++;  ;

if ( ) then

if ( ) then

 else ;

else if ( )  then  else ;

} while( );

Конец Процедуры

 

Процедура Initiate() заключается в инциализации значением 0 счетчика counter количества ребер, включенных в результирующую цепь, а также в присваивании всем ребрам пометки true, соответствующей непройденному ребру.

Функциональное назначение процедуры Ranking() – определить для каждого ребра  графа его ранг . Как отмечалось ранее, различные алгоритмы вычисления значений функции  приведены в работах [9,10], их вычислительная сложность не превосходит величины .

При выполнении процедуры Constructing (v) производится взаимообмен номеров инцидентных ребру e вершин, таким образом, чтобы вершина  посещалась при обходе раньше вершины . Данную функцию реализует процедура REPLACE.

 

Процедура REPLACE ( )

; ; ;

; ; ;

; ; ;

Конец Процедуры

 

Теорема 3 [4]. Алгоритм AOE-TRAIL и процедура Constructing(v) строют AOE-цепь в плоском связном 4-регулярном графе G за время .

3. Алгоритм построения самонепересекающейся ОЕ-цепи в плоском эйлеровом графе

Класс AOE-цепей не охватывает полностью всех возможных маршрутов движения режущего инструмента, при которых отсутствуют пересечения имеющихся резов. Общим случаем является решение задачи построение самонепересекающейся OE-цепи.

Определение 3. Эйлеров цикл в  плоском графе G называется самонепересекающимся [12], если он гомеоморфен циклическому графу , который может быть получен из графа G с помощью  применения  операций расщепления вершин.

Определение 4. Систему переходов цепи, соответствующую самонепересекающейся цепи, будем называть системой непересекающихся переходов [12].

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

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

На множестве вершин графа  определим булеву функцию

При выполнении функции инициализации Initiate() все вершины объявить непросмотренными.

Процедура Non-intersecting () расщепляет в графе  все вершины ,  на k искусственных вершин степени 4 и вводит k искусственных ребер, инцидентных полученным после расщепления вершинам и образующим цикл.

 

ФУНКЦИЯ Non-intersecting (G)

Вход: плоский эйлеров граф ;

Выход: плоский связный 4-регулярный граф ;

for ( ) do

       k=1;

       while ( ) do

                   if (not ) then

                               Handle ( , , k);

                   k++;

       endwhile

endfor

return ;

Конец Функции

 

В теле функции используется процедура Handle ( , , k), которая обрабатывает каждую непросмотренную вершину графа . Обработка заключается в расщеплении вершины  в соответствии с рис.1.

          

Рис.1. Расщепление вершины (жирными линиями показаны ребра графа , тонкими линиями –
дополнительные (фиктивные) ребра) и модификация указателей в соответствии с расщеплением

ПРОЦЕДУРА Handle (e,v,k)

// Проход 1: Определение степени вершины v

;

; //Степень вершины

do

;

if ( ) then REPLACE(le);

;    ;

while ( );

//Проход 2: Расщепление вершин, степень которых выше 4

if (d>4) then

; ; fl=new EDGE;   fle=fl;     ;     ;

do

                   ;     ;    fr=fl; fl=new EDGE;      ;

Pointers(e,le,fr,fl); //Расставить указатели для ребер

while ( );

Pointers(efirst, lk(efirst), fle, fe); //Расставить указатели для ребер

endif

Конец Процедуры

 

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

Заключение

Предложенные в работе алгоритмы дают решение проблемы маршрутизации при вырезании деталей, когда на маршрут движения режущего инструмента наложены такие технологические ограничения, как (1) отрезанная от листа часть не требует дополнительных разрезаний, (2) отсутствуют самопересечения траектории резки. Изложенные в работе алгоритмы задачи маршрутизации в плоских графах решают задачу определения последовательности резки в соответствии с наложенными ограничениями по раскройному плану при использовании технологий  ECP и ICP допускающих возможность совмещения границ вырезаемых деталей. Их применение позволяет сократить расход материала, длину горячей резки, и длину холостых проходов.

Литература

1.  Dewil, R., Vansteenwegen, P., Cattrysse, D., Laguna, M., Vossen, T. An improvement heuristic framework for the laser cutting tool path problem // International Journal of Production Research, 2015. Volume 53, Issue 6, Pages 1761–1776.

2.  Makarovskikh Т.А., Panyukov А.V., Savitsky E.A. Mathematical Models and Routing Algorithms for CAM of Technological Support of Cutting Processes // ScienceDirect IFAC-PapersOnLine 49-12 (2016) 821–826. http://www.sciencedirect.com/science/article/pii/S2405896316311624

3.  Makarovskikh T., Savitskiy E. Algorithms for constructing resource-saving cutting machines // Procedia Engineering. 2015. Vol. 129. P. 781-786.

4.  Makarovskikh T.A., Panyukov A.V. AOE-Trails Constructing for a Plane Connected 4-Regular Graph. // CEUR Workshop Proceedings. Vol 1623. Pp. 62–71. htpp://ceur-ws.org/Vol-1623

5.  Szeider S. Finding Paths in Graphs Avoiding Forbidden Transitions // Discrete Applied Mathematics, 2003. № 126. P. 261–273.

6.  Фляйшнер, Г. Эйлеровы графы и смежные вопросы / Г. Фляйшнер. – М.: Мир, 2002. – 335 с., ил.

7.  Panioukova, T.A. Algorithms for Construction of Ordered Enclosing Traces in Planar Eulerian Graphs / T.A. Panioukova, A.V. Panyukov // The International Workshop on Computer Science and Information Technologies' 2003, Proceedings of Workshop, Ufa, September 16–18, 2003/ Ufa State Technical University. – Ufa, 2003. – Vol. 1. – Р. 134–138.

8.  Panyukova T. Chain sequences with ordered enclosing. – Journal of Computer and System Sciences International, 2007, Vol. 46, No. 1; 10. – P. 83–92.

9.  Панюкова Т.А. Цепи с упорядоченным охватыванием в плоских графах// Дискретный анализ и исследование операций. Новосибирск: Часть 2. 2006. Т.13, No. 2, С. 31–43.

10.  Савицкий Е. А. Использование алгоритма поиска в ширину для определения уровней вложенности ребер плоского графа // Информационные технологии и системы: тр. Третьей междунар. науч. конф. / Челябинск: Изд-во ЧелГУ, 2014. C 43–45.

11.  Макаровских Т.А., Панюков А.В. Алгоритм построения АОЕ-цепи в плоском связном 4-регулярном графе // Материалы XII Международного научного семинара «Дискретная математика и ее приложения» имени академика О. Б. Лупанова. – М.: Издательство механико-математического факультета МГУ. С. 293–296.

12.  Макаровских Т.А. О числе ОЕ-цепей для заданной системы переходов // Вестник Южно-Уральского государственного университета. Серия: Математика. Механика. Физика. 2016. Т. 8. № 1. С. 5–12.