Решение геометрических ограничений - это удовлетворение ограничений в настройках вычислительной геометрии , которое имеет основное применение в автоматизированном проектировании . [1] Решаемая задача состоит из заданного набора геометрических элементов и описания геометрических ограничений между элементами, которые могут быть непараметрическими (касание, горизонтальность, соосность и т. д.) или параметрическими (например, расстояние, угол, радиус). ). Цель состоит в том, чтобы найти положения геометрических элементов в 2D или 3D пространстве, которые удовлетворяют заданным ограничениям, [2] что делается с помощью специальных программных компонентов, называемых решателями геометрических ограничений.
Решение геометрических ограничений стало неотъемлемой частью CAD-систем в 80-х годах, когда Pro/Engineer впервые представил новую концепцию параметрического моделирования на основе признаков. [3] [4]
Существуют дополнительные проблемы решения геометрических ограничений, связанные с наборами геометрических элементов и ограничений: динамическое перемещение заданных элементов с соблюдением всех ограничений, [5] обнаружение наборов и подмножеств с чрезмерными и недостаточными ограничениями, [6] [7] автоматическое ограничение задач с недостаточным ограничением и т. д.
Общая схема решения геометрических ограничений состоит из моделирования набора геометрических элементов и ограничений с помощью системы уравнений, а затем решения этой системы с помощью нелинейного алгебраического решателя. Ради производительности можно использовать ряд методов декомпозиции , чтобы уменьшить размер набора уравнений: [8] алгоритмы планирования декомпозиции-рекомбинации, [9] [10] декомпозиция дерева, [11] декомпозиция C-дерева. , [12] редукция графа, [13] перепараметризация и редукция, [14] вычисление фундаментальных схем, [15] структура body-and-cad, [16] или метод конфигурации свидетеля.[17]
Некоторые другие методы и подходы включают анализ степеней свободы, [18] [19] символьные вычисления, [20] вычисления на основе правил, [21] программирование ограничений и распространение ограничений, [21] [22] и генетические алгоритмы. [23]
Системы нелинейных уравнений в основном решаются итерационными методами, которые решают линейную задачу на каждой итерации, наиболее популярным примером является метод Ньютона-Рафсона. [21]