Аннотация:
В CAD/CAM-системах технологической подготовки процессов раскроя встает задача построения маршрута движения режущего инструмента, при котором отрезанная от листа часть не требует дополнительных разрезаний и запрещены пересечения траектории резки (касания допускаются). Формально такая задача может быть сформулирована как задача построения самонепересекающейся цепи в плоском эйлеровом графе, представляющим гомеоморфный образ раскройного плана. В конечном счете задачи построения маршрутов, удовлетворяющих технологическим ограничениям, сводятся к нахождению A-цепи с упорядоченным охватыванием в плоском связном 4-регулярном графе. В статье предложен алгоритм нахождения такой цепи. Выполнение алгоритма состоит из двух этапов. На первом этапе выявляются и расщепляются точки сочленения ранга k. На втором этапе построение цепи начинается из произвольной вершины, инцидентной внешней грани; первым ребром цепи выбирается инцидентное данной вершине ребро максимального ранга; далее организуется итерационный процесс, где в качестве следующего ребра выбирается непройденное ребро максимального ранга, являющееся левым либо правым соседом текущего ребра. Показано, что для плоского связного 4-регулярного графа алгоритм строит маршрут с указанными свойствами за линейное время. Представленные алгоритмы реализованы в виде компьютерной программы. Приведены примеры решения ряда тестовых задач.
Образец цитирования:
Т. А. Макаровских, “Программное обеспечение для построения A-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе”, Вестн. ЮУрГУ. Сер. Выч. матем. информ., 8:1 (2019), 36–53
\RBibitem{Mak19}
\by Т.~А.~Макаровских
\paper Программное обеспечение для построения \textit{A}-цепей с упорядоченным охватыванием в плоском связном 4-регулярном графе
\jour Вестн. ЮУрГУ. Сер. Выч. матем. информ.
\yr 2019
\vol 8
\issue 1
\pages 36--53
\mathnet{http://mi.mathnet.ru/vyurv205}
\crossref{https://doi.org/10.14529/cmse190103}
\elib{https://elibrary.ru/item.asp?id=37074207}
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/vyurv205
https://www.mathnet.ru/rus/vyurv/v8/i1/p36
Эта публикация цитируется в следующих 1 статьяx:
Т. А. Макаровских, А. В. Панюков, “Программное обеспечение для задачи построения траектории движения режущего инструмента для CAD/CAM систем технологической подготовки процессов раскроя”, Автомат. и телемех., 2021, № 3, 123–137; T. A. Makarovskikh, A. V. Panyukov, “Software for the problem of constructing cutting tool paths in CAD/CAM systems for technological preparation of cutting processes”, Autom. Remote Control, 82:3 (2021), 468–480
Цитирование в формате AMSBIB
Обратная связь: