Маляренко Артём Андреевич

Группа 22126
Руководитель: Рыков Иван Александрович

Текст ВКР

Аннотация

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

В работе исследованы основные подходы к геометрической декомпозиции систем ограничений, включая упрощение, отделяющую декомпозицию, введение жёсткости и разбиение на двусвязные компоненты. Реализованы 11 шаблонов упрощения, 3 шаблона отделяющей декомпозиции, а также модули введения жёсткости и двусвязной декомпозиции.

Для представления геометрических объектов и ограничений использован метод декартового алгебраического моделирования. Разработаны трансляторы ограничений в систему нелинейных алгебраических уравнений для различных типов геометрических объектов и ограничений.

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