Геометрический решатель САПР: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
Содержимое удалено Содержимое добавлено
Спасено источников — 3, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.8.8
Спасено источников — 7, отмечено мёртвыми — 0. Сообщить об ошибке. См. FAQ.) #IABot (v2.0.9.2
Строка 7: Строка 7:
Общая схема работы геометрических решателей состоит в генерации системы нелинейных уравнений, которая моделирует геометрические ограничения, наложенные на объекты, и решении этой системы, как правило, с помощью использования итеративных методов, таких как метод Ньютона-Рафсона. Существенное значение для корректности и производительности геометрических решателей имеет способ моделирования.
Общая схема работы геометрических решателей состоит в генерации системы нелинейных уравнений, которая моделирует геометрические ограничения, наложенные на объекты, и решении этой системы, как правило, с помощью использования итеративных методов, таких как метод Ньютона-Рафсона. Существенное значение для корректности и производительности геометрических решателей имеет способ моделирования.


Для ускорения работы решателей используют различные методы [[декомпозиция|декомпозиции]] задачи:<ref>{{книга |заглавие=A formalization of geometric constraint systems and their decomposition |ссылка=https://link.springer.com/article/10.1007%2Fs00165-009-0117-8 |язык=en |автор=Pascal Mathis, Simon E. B. Thierry}}</ref> декомпозиция-рекомбинация,<ref>{{книга |заглавие=Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD |ссылка=http://www.sciencedirect.com/science/article/pii/S0747717100904024 |язык=en |автор=Christoph M.Hoffman, Andrew Lomonosov, Meera Sitharam}}</ref><ref>{{книга |заглавие=Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms |ссылка=http://www.sciencedirect.com/science/article/pii/S0747717100904036 |язык=en |автор=Christoph M.Hoffman, Andrew Lomonosov, Meera Sitharam}}</ref> древовидная декомпозиция,<ref>{{книга |заглавие=h-graphs: A new representation for tree decompositions of graphs |ссылка=http://www.sciencedirect.com/science/article/pii/S0010448515000688 |язык=en |автор=Marta Hidalgoa, Robert Joan-Arinyo}}</ref> C-tree decomposition,<ref>{{книга |заглавие=A C-tree decomposition algorithm for 2D and 3D geometric constraint solving |ссылка=http://www.sciencedirect.com/science/article/pii/S0010448505000813 |язык=en |автор=Xiao-Shan Gao, Qiang Lin, Gui-Fang Zhang}}</ref> graph reduction,<ref>{{книга |заглавие=A 2D geometric constraint solver using a graph reduction method |ссылка=http://www.sciencedirect.com/science/article/pii/S0965997810001006 |язык=en |автор=Samy Ait-Aoudia, Sebti Foufou}}</ref> re-parametrization and reduction,<ref>{{книга |заглавие=Re-parameterization reduces irreducible geometric constraint systems |ссылка=http://www.sciencedirect.com/science/article/pii/S0010448515001116 |язык=en |автор=Hichem Barki, Lincong Fang, Dominique Michelucci, Sebti Foufou}}</ref> computing fundamental circuits,<ref>{{книга |заглавие=Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity |ссылка=http://www.sciencedirect.com/science/article/pii/S001044851400030X |язык=en |автор=R.Joan-Arinyo, M.Tarrés-Puertas, S.Vila-Marta}}</ref> body-and-cad structure,<ref>{{книга |заглавие=Body-and-cad geometric constraint systems |ссылка=http://www.sciencedirect.com/science/article/pii/S0925772112000235 |язык=en |автор=Kirk Haller, Audrey Lee-St.John, Meera Sitharam, Ileana Streinu, Neil White}}</ref> и witness configuration method.<ref>{{книга |заглавие=Geometric constraint solving: The witness configuration method |ссылка=http://www.sciencedirect.com/science/article/pii/S001044850600025X |язык=en |автор=Dominique Michelucci, Sebti Foufou}}</ref>
Для ускорения работы решателей используют различные методы [[декомпозиция|декомпозиции]] задачи:<ref>{{книга |заглавие=A formalization of geometric constraint systems and their decomposition |ссылка=https://link.springer.com/article/10.1007%2Fs00165-009-0117-8 |язык=en |автор=Pascal Mathis, Simon E. B. Thierry }} {{Wayback|url=https://link.springer.com/article/10.1007%2Fs00165-009-0117-8 |date=20180118182624 }}</ref> декомпозиция-рекомбинация,<ref>{{книга |заглавие=Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD |ссылка=http://www.sciencedirect.com/science/article/pii/S0747717100904024 |язык=en |автор=Christoph M.Hoffman, Andrew Lomonosov, Meera Sitharam}}</ref><ref>{{книга |заглавие=Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms |ссылка=http://www.sciencedirect.com/science/article/pii/S0747717100904036 |язык=en |автор=Christoph M.Hoffman, Andrew Lomonosov, Meera Sitharam}}</ref> древовидная декомпозиция,<ref>{{книга |заглавие=h-graphs: A new representation for tree decompositions of graphs |ссылка=http://www.sciencedirect.com/science/article/pii/S0010448515000688 |язык=en |автор=Marta Hidalgoa, Robert Joan-Arinyo}}</ref> C-tree decomposition,<ref>{{книга |заглавие=A C-tree decomposition algorithm for 2D and 3D geometric constraint solving |ссылка=http://www.sciencedirect.com/science/article/pii/S0010448505000813 |язык=en |автор=Xiao-Shan Gao, Qiang Lin, Gui-Fang Zhang}}</ref> graph reduction,<ref>{{книга |заглавие=A 2D geometric constraint solver using a graph reduction method |ссылка=http://www.sciencedirect.com/science/article/pii/S0965997810001006 |язык=en |автор=Samy Ait-Aoudia, Sebti Foufou}}</ref> re-parametrization and reduction,<ref>{{книга |заглавие=Re-parameterization reduces irreducible geometric constraint systems |ссылка=http://www.sciencedirect.com/science/article/pii/S0010448515001116 |язык=en |автор=Hichem Barki, Lincong Fang, Dominique Michelucci, Sebti Foufou}}</ref> computing fundamental circuits,<ref>{{книга |заглавие=Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity |ссылка=http://www.sciencedirect.com/science/article/pii/S001044851400030X |язык=en |автор=R.Joan-Arinyo, M.Tarrés-Puertas, S.Vila-Marta}}</ref> body-and-cad structure,<ref>{{книга |заглавие=Body-and-cad geometric constraint systems |ссылка=http://www.sciencedirect.com/science/article/pii/S0925772112000235 |язык=en |автор=Kirk Haller, Audrey Lee-St.John, Meera Sitharam, Ileana Streinu, Neil White }} {{Wayback|url=http://www.sciencedirect.com/science/article/pii/S0925772112000235 |date=20210128233755 }}</ref> и witness configuration method.<ref>{{книга |заглавие=Geometric constraint solving: The witness configuration method |ссылка=http://www.sciencedirect.com/science/article/pii/S001044850600025X |язык=en |автор=Dominique Michelucci, Sebti Foufou}}</ref>


Некоторые другие методы и подходы включают анализ степеней свободы,<ref>{{книга |заглавие=Solving geometric constraint systems : a case study in kinematics |издательство=[[MIT Press]] |место=Cambridge, Mass. |isbn=9780262111645 |издание=1:a upplagan. |ссылка=https://mitpress.mit.edu/books/solving-geometric-constraint-systems |язык=en |автор=Kramer Glenn A. |год=1992}}</ref><ref>{{книга |заглавие=A geometric constraint solver for 3-D assembly modeling |ссылка=https://link.springer.com/article/10.1007%2Fs00170-004-2391-1?LI=true |язык=en |автор=Xiaobo Peng, Kunwoo Lee, Liping Chen}}</ref> [[символьные вычисления]],<ref>{{книга |заглавие=Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility |ссылка=https://pdfs.semanticscholar.org/a1c3/6b6aa83ecc85d28a7cdde258ab1355613926.pdf |язык=en |автор=Xiao-Shan Gao, Shang-Ching Chou}}</ref> применение систем правил,<ref name="purdue">{{книга |заглавие=A Geometric Constraint Solver |ссылка=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=2067&context=cstech |язык=und |автор=William Bouma, Ioannis Fudos, Christoph M. Hoffmann, Jiazhen Cai, Robert Paige |год=1993}}</ref> [[программирование в ограничениях]],<ref name="purdue" /><ref>{{книга |заглавие=Stabilizing 3D modeling with geometric constraints propagation |ссылка=http://www.sciencedirect.com/science/article/pii/S1077314209001003 |язык=en |автор=Michela Farenzena, Andrea Fusiello}}</ref> и [[генетические алгоритмы]].<ref>{{книга |заглавие=Constructive Geometric Constraint Solving: A New Application of Genetic Algorithms |ссылка=https://link.springer.com/chapter/10.1007/3-540-45712-7_73 |язык=en |автор=R. Joan-Arinyo, M.V. Luzón, A. Soto}}</ref>
Некоторые другие методы и подходы включают анализ степеней свободы,<ref>{{книга |заглавие=Solving geometric constraint systems : a case study in kinematics |издательство=[[MIT Press]] |место=Cambridge, Mass. |isbn=9780262111645 |издание=1:a upplagan. |ссылка=https://mitpress.mit.edu/books/solving-geometric-constraint-systems |язык=en |автор=Kramer Glenn A. |год=1992 }} {{Wayback|url=https://mitpress.mit.edu/books/solving-geometric-constraint-systems |date=20180416025511 }}</ref><ref>{{книга |заглавие=A geometric constraint solver for 3-D assembly modeling |ссылка=https://link.springer.com/article/10.1007%2Fs00170-004-2391-1?LI=true |язык=en |автор=Xiaobo Peng, Kunwoo Lee, Liping Chen }} {{Wayback|url=https://link.springer.com/article/10.1007%2Fs00170-004-2391-1?LI=true |date=20180116140159 }}</ref> [[символьные вычисления]],<ref>{{книга |заглавие=Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility |ссылка=https://pdfs.semanticscholar.org/a1c3/6b6aa83ecc85d28a7cdde258ab1355613926.pdf |язык=en |автор=Xiao-Shan Gao, Shang-Ching Chou }} {{Wayback|url=https://pdfs.semanticscholar.org/a1c3/6b6aa83ecc85d28a7cdde258ab1355613926.pdf |date=20180116135939 }}</ref> применение систем правил,<ref name="purdue">{{книга |заглавие=A Geometric Constraint Solver |ссылка=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=2067&context=cstech |язык=und |автор=William Bouma, Ioannis Fudos, Christoph M. Hoffmann, Jiazhen Cai, Robert Paige |год=1993 }} {{Wayback|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=2067&context=cstech |date=20170202004602 }}</ref> [[программирование в ограничениях]],<ref name="purdue" /><ref>{{книга |заглавие=Stabilizing 3D modeling with geometric constraints propagation |ссылка=http://www.sciencedirect.com/science/article/pii/S1077314209001003 |язык=en |автор=Michela Farenzena, Andrea Fusiello}}</ref> и [[генетические алгоритмы]].<ref>{{книга |заглавие=Constructive Geometric Constraint Solving: A New Application of Genetic Algorithms |ссылка=https://link.springer.com/chapter/10.1007/3-540-45712-7_73 |язык=en |автор=R. Joan-Arinyo, M.V. Luzón, A. Soto }} {{Wayback|url=https://link.springer.com/chapter/10.1007/3-540-45712-7_73 |date=20180116140403 }}</ref>


Системы нелинейных уравнений в основном решают с помощью итерационных методов, на каждой итерации решается линейная задача. [[Метод_Ньютона#Метод_Ньютона_—_Рафсона|Метод Ньютона — Рафсона]] является одним из самым известных примеров.<ref name="purdue" />
Системы нелинейных уравнений в основном решают с помощью итерационных методов, на каждой итерации решается линейная задача. [[Метод_Ньютона#Метод_Ньютона_—_Рафсона|Метод Ньютона — Рафсона]] является одним из самым известных примеров.<ref name="purdue" />

Версия от 12:44, 16 декабря 2022

Геометрический решатель (англ. Geometric Constraint Solver), решатель геометрических ограничений, геометрический решатель задач в ограничениях — это программная компонента, которая встраивается в САПР и позволяет инженеру точно позиционировать геометрические элементы друг относительно друга.

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

Методы

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

Для ускорения работы решателей используют различные методы декомпозиции задачи:[1] декомпозиция-рекомбинация,[2][3] древовидная декомпозиция,[4] C-tree decomposition,[5] graph reduction,[6] re-parametrization and reduction,[7] computing fundamental circuits,[8] body-and-cad structure,[9] и witness configuration method.[10]

Некоторые другие методы и подходы включают анализ степеней свободы,[11][12] символьные вычисления,[13] применение систем правил,[14] программирование в ограничениях,[14][15] и генетические алгоритмы.[16]

Системы нелинейных уравнений в основном решают с помощью итерационных методов, на каждой итерации решается линейная задача. Метод Ньютона — Рафсона является одним из самым известных примеров.[14]

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

Приложения и программные реализации

Основной областью применения геометрических решателей являются САПР. Они также используются для решения задач обратной кинеметики, робототехники, архитектурно-конструкторских работ, геометрического моделирования молекул и других прикладных областей.

К геометрическим решателям относятся:

См. также

Примечания

  1. Pascal Mathis, Simon E. B. Thierry. A formalization of geometric constraint systems and their decomposition (англ.). Архивная копия от 18 января 2018 на Wayback Machine
  2. Christoph M.Hoffman, Andrew Lomonosov, Meera Sitharam. Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD (англ.).
  3. Christoph M.Hoffman, Andrew Lomonosov, Meera Sitharam. Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms (англ.).
  4. Marta Hidalgoa, Robert Joan-Arinyo. h-graphs: A new representation for tree decompositions of graphs (англ.).
  5. Xiao-Shan Gao, Qiang Lin, Gui-Fang Zhang. A C-tree decomposition algorithm for 2D and 3D geometric constraint solving (англ.).
  6. Samy Ait-Aoudia, Sebti Foufou. A 2D geometric constraint solver using a graph reduction method (англ.).
  7. Hichem Barki, Lincong Fang, Dominique Michelucci, Sebti Foufou. Re-parameterization reduces irreducible geometric constraint systems (англ.).
  8. R.Joan-Arinyo, M.Tarrés-Puertas, S.Vila-Marta. Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity (англ.).
  9. Kirk Haller, Audrey Lee-St.John, Meera Sitharam, Ileana Streinu, Neil White. Body-and-cad geometric constraint systems (англ.). Архивная копия от 28 января 2021 на Wayback Machine
  10. Dominique Michelucci, Sebti Foufou. Geometric constraint solving: The witness configuration method (англ.).
  11. Kramer Glenn A. Solving geometric constraint systems : a case study in kinematics (англ.). — 1:a upplagan.. — Cambridge, Mass.: MIT Press, 1992. — ISBN 9780262111645. Архивная копия от 16 апреля 2018 на Wayback Machine
  12. Xiaobo Peng, Kunwoo Lee, Liping Chen. A geometric constraint solver for 3-D assembly modeling (англ.). Архивная копия от 16 января 2018 на Wayback Machine
  13. Xiao-Shan Gao, Shang-Ching Chou. Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility (англ.). Архивная копия от 16 января 2018 на Wayback Machine
  14. 1 2 3 William Bouma, Ioannis Fudos, Christoph M. Hoffmann, Jiazhen Cai, Robert Paige. A Geometric Constraint Solver (неопр.). — 1993. Архивная копия от 2 февраля 2017 на Wayback Machine
  15. Michela Farenzena, Andrea Fusiello. Stabilizing 3D modeling with geometric constraints propagation (англ.).
  16. R. Joan-Arinyo, M.V. Luzón, A. Soto. Constructive Geometric Constraint Solving: A New Application of Genetic Algorithms (англ.). Архивная копия от 16 января 2018 на Wayback Machine
  17. D-Cubed Customers. Дата обращения: 17 января 2018. Архивировано 28 декабря 2017 года.
  18. Евгений Ермаков, Сергей Митин, Сергей Ротков, Александр Максименко. Использование C3D Solver для решения кинематических задач узлов механизмов. LEDAS Ltd. (6 января 2017). Дата обращения: 26 апреля 2017. Архивировано 27 апреля 2017 года.
  19. GeoSolver Project Page. Дата обращения: 17 января 2018. Архивировано 11 октября 2017 года.

Ссылки