Geometric constraint solving: Difference between revisions

Revision as of 06:23, 23 November 2017

Revision as of 06:30, 23 November 2017

Line 12:

A general scheme of geometric constraint solving comprises of modeling a set of geometric elements and constraints by a system of equations, and then solving this system by non-linear algebraic solver. For the sake of performance, a number of [[Decomposition method (constraint satisfaction)|decomposition techniques]] could be used in order to decrease the size of an equation set:<ref>{{cite book|title=A formalization of geometric constraint systems and their decomposition|last1=Pascal Mathis|last2=Simon E. B. Thierry|url=https://link.springer.com/article/10.1007%2Fs00165-009-0117-8}}</ref> decomposition-recombination planning algorithms,<ref>{{cite book|title=Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD|url=http://www.sciencedirect.com/science/article/pii/S0747717100904024|last1=Christoph M.Hoffman|last2=Andrew Lomonosov|last3=Meera Sitharam}}</ref><ref>{{cite book|title=Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms|url=http://www.sciencedirect.com/science/article/pii/S0747717100904036|last1=Christoph M.Hoffman|last2=Andrew Lomonosov|last3=Meera Sitharam}}</ref> tree decomposition,<ref>{{cite book|title=h-graphs: A new representation for tree decompositions of graphs|url=http://www.sciencedirect.com/science/article/pii/S0010448515000688|last1=Marta Hidalgoa|last2=Robert Joan-Arinyo}}</ref> C-tree decomposition,<ref>{{cite book|title=A C-tree decomposition algorithm for 2D and 3D geometric constraint solving|url=http://www.sciencedirect.com/science/article/pii/S0010448505000813|last1=Xiao-Shan Gao|last2=Qiang Lin|last3=Gui-Fang Zhang}}</ref> graph reduction,<ref>{{cite book|title=A 2D geometric constraint solver using a graph reduction method|url=http://www.sciencedirect.com/science/article/pii/S0965997810001006|last1=Samy Ait-Aoudia|last2=Sebti Foufou}}</ref> re-parametrization and reduction,<ref>{{cite book|title=Re-parameterization reduces irreducible geometric constraint systems|url=http://www.sciencedirect.com/science/article/pii/S0010448515001116|last1=Hichem Barki|last2=Lincong Fang|last3=Dominique Michelucci|last4=Sebti Foufou}}</ref> computing fundamental circuits,<ref>{{cite book|title=Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity|url=http://www.sciencedirect.com/science/article/pii/S001044851400030X|last1=R.Joan-Arinyo|last2=M.Tarrés-Puertas|last3=S.Vila-Marta}}</ref> body-and-cad structure,<ref>{{cite book|title=Body-and-cad geometric constraint systems|url=http://www.sciencedirect.com/science/article/pii/S0925772112000235|last1=Kirk Haller|last2=Audrey Lee-St.John|last3=Meera Sitharam|last4=Ileana Streinu|last5=Neil White}}</ref> or the witness configuration method.<ref>{{cite book|title=Geometric constraint solving: The witness configuration method|url=http://www.sciencedirect.com/science/article/pii/S001044850600025X|last1=Dominique Michelucci|last2=Sebti Foufou}}</ref>

Some other methods and approaches include the degrees of freedom analysis,<ref>{{cite book|last1=Kramer|first1=Glenn A.|title=Solving geometric constraint systems : a case study in kinematics|date=1992|publisher=MIT Press|___location=Cambridge, Mass.|isbn=9780262111645|edition=1:a upplagan.|url=https://mitpress.mit.edu/books/solving-geometric-constraint-systems}}</ref><ref>{{cite book|title=A geometric constraint solver for 3-D assembly modeling|url=https://link.springer.com/article/10.1007%2Fs00170-004-2391-1?LI=true|last1=Xiaobo Peng|last2=Kunwoo Lee|last3=Liping Chen}}</ref> symbolic computations,<ref>{{cite book|title=Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility|last1=Xiao-Shan Gao|last2=Shang-Ching Chou|url=https://pdfs.semanticscholar.org/a1c3/6b6aa83ecc85d28a7cdde258ab1355613926.pdf}}</ref> rule-based computations,<ref name="purdue">{{cite book|title=A Geometric Constraint Solver|date=1993|url=http://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=2067&context=cstech|last1=William Bouma|last2=Ioannis Fudos|last3=Christoph M. Hoffmann|last4=Jiazhen Cai|last5=Robert Paige}}</ref> constraint programming and constraint propagation,<ref name="purdue" /><ref>{{cite book|title=Stabilizing 3D modeling with geometric constraints propagation|url=http://www.sciencedirect.com/science/article/pii/S1077314209001003|last1=Michela Farenzena|last2=Andrea Fusiello}}</ref> and genetic algorithms.<ref>{{cite book|title=Constructive Geometric Constraint Solving: A New Application of Genetic Algorithms|url=https://link.springer.com/chapter/10.1007/3-540-45712-7_73|last1=R. Joan-Arinyo|last2=M.V. Luzón|last3=A. Soto}}</ref>

Non-linear equation systems are mostly solved by iterative methods that resolve the linear problem at each iteration, Newton-Raphson method being the most popular example.<ref name="purdue" />

Line 18:

== Applications ==

Geometric constraint solving has applications in a wide variety of fields, such as computer aided design, mechanical engineering, [[inverse kinematics]] and [[robotics]],<ref>{{cite web|title=Geometric constraint solver|url=http://www.coppeliarobotics.com/helpFiles/en/geometricConstraintSolverModule.htm}}</ref> architecture and construction, molecular chemistry,<ref>{{cite book|title=Leading a continuation method by geometry for solving geometric constraints|date=2014|last1=Rémi Imbach|last2=Pascal Schreck|last3=Pascal Mathis|url=http://www.sciencedirect.com/science/article/pii/S0010448513001668}}</ref> and geometric theorem proving. The primary application area is computer aided design, where geometric constraint solving is used in both parametric history-based modeling and direct variational direct modeling.<ref>{{cite book|title=Variational Direct Modeling: How to Keep Design Intent in History-Free CAD|date=2008|url=http://www.ledas.com/pdf/VariationalDirectModeling.pdf|last1=Dmitry Ushakov}}</ref>

== Software implementations ==