'''Geometric constraint solving ''' is [[constraint satisfaction]] in a [[computational geometry ]] setting, which has a primary applications in [[computer aided design]].<ref>{{cite book |last1=Roller|first1=edited by Beat Brüderlin, Dieter|title=Geometric Constraint Solving and Applications |date=1998|publisher=Springer Berlin Heidelberg|___location=Berlin, Heidelberg|isbn=978-3-642-58898-3|pages=3–23|url= httphttps://www.springer.com/gp/book/9783642637810 |language=en}}</ref> TheA problem to be solved consists of a given set of geometric elements and a description of geometric [[Constraint (computer-aided design)|constraints]] between the elements, which could be non-parametric (tangency, horizontality, coaxiality, etc) or parametric (like distance, angle, radius). The goal is to find the positions of the geometric elements in 2D or 3D space whichthat satisfy the given constraints,<ref>{{cite book |last1=Christoph M. Hoffmann|last2=Pamela J. Vermeer|s2cid=18272588|title=Geometric constraint solving in R2 and R3| urldoi= https://pdfs.semanticscholar10. org1142/ 5495/673d9bda0ec575a2185ddb890f887328be58.pdf9789812831699_0008}}</ref> which is done by dedicated software components called geometric constraint solvers. ▼
{{Userspace draft|source=ArticleWizard|date=November 2017}}
The geometricGeometric constraint solving became necessaryan integral part of CAD systems in the 80s, when Pro/Engineer firstlyfirst introduced a novel concept of feature-based parametric modeling concept.<ref>{{cite book|last1=Robert Joan-Arinyo|title=Basics on Geometric Constraint Solving| url=http://citeseerx .ist.psu.edu/viewdoc/download?doi=10.1.1.331.9554 &rep=rep1&type=pdf}}</ref><ref>{{cite bookjournal|last1=R. Anderl|last2=R. Mendgen|title=Modelling with constraints: theoretical foundation and application| urljournal= http://wwwComputer-Aided Design|volume=28|issue=3|pages=155–168|doi=10. sciencedirect.com1016/ science/article/pii/00104485950002320010-4485(95)00023-2|year=1996}}</ref> ▼▲Geometric constraint solving is [[constraint satisfaction]] in a computational geometry, which has a primary applications in [[computer aided design]].<ref>{{cite book|title=Geometric Constraint Solving and Applications|url=http://www.springer.com/gp/book/9783642637810}}</ref> The problem to be solved consists of a given set of geometric elements and a description of geometric [[Constraint (computer-aided design)|constraints]] between the elements, which could be non-parametric (tangency, horizontality, coaxiality, etc) or parametric (like distance, angle, radius). The goal is to find positions of the geometric elements in 2D or 3D space which satisfy the given constraints,<ref>{{cite book|title=Geometric constraint solving in R2 and R3|url=https://pdfs.semanticscholar.org/5495/673d9bda0ec575a2185ddb890f887328be58.pdf}}</ref> which is done by dedicated software components called geometric constraint solvers.
There are additional problems of geometric constraint solving that are related to sets of geometric elements and constraints: dynamic moving of given elements keeping all constraints satisfied,<ref>{{cite journal|title=A constraint-based dynamic geometry system|journal=Computer-Aided Design|volume=42|issue=2|pages=151–161|last1=Marc Freixas|last2=Robert Joan-Arinyo|last3=Antoni Soto-Riera|doi=10.1016/j.cad.2009.02.016|year=2010}}</ref> detection of over- and under-constrained sets and subsets,<ref>{{cite book|last1=Rossignac|first1=Jaroslaw|last2=SIGGRAPH|first2=Joshua Turner, editors; sponsored by ACM|title=Proceedings : Symposium on Solid Modeling Foundations and CAD/CAM Applications, Radisson Plaza Hotel, Austin, Texas, June 5-7, 1991|date=1991|publisher=Association for Computing Machinery|___location=New York|isbn=978-0-89791-427-7}}</ref><ref>{{cite journal|title=Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems|journal=Computer-Aided Design|volume=43|issue=10|pages=1234–1249|last1=Simon E.B.Thierry|last2=Pascal Schreck|last3=Dominique Michelucci|last4=Christoph Fünfzig|last5=Jean-David Génevaux|doi=10.1016/j.cad.2011.06.018|year=2011|url=https://hal.archives-ouvertes.fr/hal-00691690/file/cad11.pdf}}</ref> auto-constraining of under-constrained problems, etc.
▲The geometric constraint solving became necessary part of CAD systems in 80s, when Pro/Engineer firstly introduced feature-based parametric modeling concept.<ref>{{cite book|last1=Robert Joan-Arinyo|title=Basics on Geometric Constraint Solving|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.331.9554&rep=rep1&type=pdf}}</ref><ref>{{cite book|title=Modelling with constraints: theoretical foundation and application|url=http://www.sciencedirect.com/science/article/pii/0010448595000232}}</ref>
There are additional problems of geometric constraint solving that are related to sets of geometric elements and constraints: dynamic moving of given element keeping all the constraints satisfied,<ref>{{cite book|title=A constraint-based dynamic geometry system|url=http://www.sciencedirect.com/science/article/pii/S0010448509000876}}</ref> detection of over- and under-constrained sets and subsets,<ref>{{cite book|title=Extensions of the witness method to characterize under-, over- and well-constrained geometric constraint systems|url=http://www.sciencedirect.com/science/article/pii/S0010448511001606}}</ref> auto-constraining of under-constrained problems, etc.
== Methods ==
GeneralA general scheme of geometric constraint solving consistconsists of modeling of 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 systeman ofequation equations to be solvedset:<ref>{{cite bookjournal|title=A formalization of geometric constraint systems and their decomposition|urljournal=https://linkFormal Aspects of Computing|volume=22|issue=2|pages=129–151|last1=Pascal Mathis|last2=Simon E.springer B.com/article/ Thierry|doi=10.1007%2Fs00165/s00165-009-0117-8|year=2010|s2cid=16959899 |url=https://hal.archives-ouvertes.fr/hal-00534926|doi-access=free}}</ref> decomposition-recombination planning algorithms,<ref>{{cite bookjournal|title=Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD|urljournal=http://wwwJournal of Symbolic Computation|volume=31|issue=4|pages=367–408|last1=Christoph M.sciencedirectHoffman|last2=Andrew Lomonosov|last3=Meera Sitharam|doi=10.com1006/science/article/pii/S0747717100904024jsco.2000.0402|year=2001|doi-access=free}}</ref><ref>{{cite bookjournal|title=Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms|urljournal=http://wwwJournal of Symbolic Computation|volume=31|issue=4|pages=409–427|last1=Christoph M.sciencedirectHoffman|last2=Andrew Lomonosov|last3=Meera Sitharam|doi=10.com1006/science/article/pii/S0747717100904036jsco.2000.0403|year=2001|doi-access=free}}</ref> tree decomposition,<ref>{{cite bookjournal|title=h-graphs: A new representation for tree decompositions of graphs|journal=Computer-Aided Design|volume=67-68|pages=38–47|last1=Marta Hidalgoa|last2=Robert Joan-Arinyo|doi=10.1016/j.cad.2015.05.003|year=2015|hdl=2117/78683|url=httphttps://wwwupcommons.sciencedirectupc.comedu/sciencebitstream/article2117/pii78683/S00104485150006888/main.pdf|hdl-access=free}}</ref> C-tree decomposition,<ref>{{cite bookjournal|title=A C-tree decomposition algorithm for 2D and 3D geometric constraint solving|journal=Computer-Aided Design|volume=38|pages=1–13|last1=Xiao-Shan Gao|last2=Qiang Lin|last3=Gui-Fang Zhang|doi=10.1016/j.cad.2005.03.002|year=2006|url=httphttps://wwwhal.sciencedirectinria.comfr/scienceinria-00517706/articlefile/pii/S0010448505000813Xiao-ShanGao2006a.pdf}}</ref> graph reduction,<ref>{{cite bookjournal|title=A 2D geometric constraint solver using a graph reduction method|urljournal=http:Advances in Engineering Software|volume=41|issue=10–11|pages=1187–1194|last1=Samy Ait-Aoudia|last2=Sebti Foufou|doi=10.1016//wwwj.sciencedirectadvengsoft.com/science/article/pii/S09659978100010062010.07.008|year=2010}}</ref> re-parametrization and reduction,<ref>{{cite bookjournal|title=Re-parameterization reduces irreducible geometric constraint systems|journal=Computer-Aided Design|volume=70|pages=182–192|last1=Hichem Barki|last2=Lincong Fang|last3=Dominique Michelucci|last4=Sebti Foufou|doi=10.1016/j.cad.2015.07.011|year=2016|url=httphttps://wwwhal.sciencedirectarchives-ouvertes.comfr/sciencehal-01205755/articlefile/pii/S0010448515001116Re-Parameterization-Barki-etAl-CAD-2016.pdf}}</ref> computing fundamental circuits,<ref>{{cite bookjournal|title=Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity|urljournal=http://wwwComputer-Aided Design|volume=52|pages=1–16|last1=R.sciencedirectJoan-Arinyo|last2=M.com/scienceTarrés-Puertas|last3=S.Vila-Marta|doi=10.1016/article/pii/S001044851400030Xj.cad.2014.02.006|year=2014}}</ref> body-and-cad structure,<ref>{{cite bookjournal|title=Body-and-cad geometric constraint systems|urljournal=http://wwwComputational Geometry|volume=45|issue=8|pages=385–405|last1=Kirk Haller|last2=Audrey Lee-St.sciencedirectJohn|last3=Meera Sitharam|last4=Ileana Streinu|last5=Neil White|doi=10.com/science1016/article/pii/S0925772112000235j.comgeo.2010.06.003|year=2012|arxiv=1006.1126}}</ref> or the witness configuration method.<ref>{{cite bookjournal|title=Geometric constraint solving: The witness configuration method|urljournal=http:Computer-Aided Design|volume=38|issue=4|pages=284–299|last1=Dominique Michelucci|last2=Sebti Foufou|doi=10.1016//wwwj.sciencedirectcad.com/science/article/pii/S001044850600025X2006.01.005|year=2006|citeseerx=10.1.1.579.2143}}</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 bookjournal|title=A geometric constraint solver for 3-D assembly modeling|urljournal=The International Journal of Advanced Manufacturing Technology|volume=28|issue=5–6|pages=561–570|last1=Xiaobo Peng|last2=Kunwoo Lee|last3=Liping Chen|doi=https://link.springer.com/article/10.1007%2Fs00170/s00170-004-2391-1?LI|year=true2006|s2cid=120186972 }}</ref> symbolic computations,<ref>{{cite book|title=Solving Geometric Constraint Systems II. A Symbolic Approach and Decision of Rc-constructibility|urllast1=https://pdfsXiao-Shan Gao|last2=Shang-Ching Chou|s2cid=775489|year=1998|doi=10.semanticscholar.org1016/a1c3/6b6aa83ecc85d28a7cdde258ab1355613926.pdfs0010-4485(97)00055-9}}</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 bookjournal|title=Stabilizing 3D modeling with geometric constraints propagation|urljournal=http:/Computer Vision and Image Understanding|volume=113|issue=11|pages=1147–1157|last1=Michela Farenzena|last2=Andrea Fusiello|doi=10.1016/wwwj.sciencedirectcviu.com/science/article/pii/S10773142090010032009.05.004|year=2009}}</ref> and genetic algorithms.<ref>{{cite book|last1=R. Joan-Arinyo|last2=M.V. Luzón|last3=A. Soto|doi=10.1007/3-540-45712-7_73|title =Constructive GeometricParallel ConstraintProblem Solving: Afrom NewNature Application— ofPPSN GeneticVII|volume Algorithms= 2439|urlpages=https://link.springer.com/chapter/10.1007/759–768|series = Lecture Notes in Computer Science|year = 2002|isbn = 978-3-540-4571244139-7_737}}</ref>
The solving of nonNon-linear systemequation ofsystems equations isare mostly donesolved by iterative methods that resolve the linear problem onat each iteration, the Newton-Raphson method being the most popular example.<ref name="purdue" />
== 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 bookjournal|title=Leading a continuation method by geometry for solving geometric constraints|urljournal=http:/Computer-Aided Design|volume=46|pages=138–147|date=2014|last1=Rémi Imbach|last2=Pascal Schreck|last3=Pascal Mathis|doi=10.1016/wwwj.sciencedirectcad.com/science/article/pii/S00104485130016682013.08.026}}</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 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 ==
The list of geometric constraint solvers includes at least
* [DCM (Dimensional Constraint Manager),<ref>{{cite web|title=2D Dimensional Constraint Manager (D-Cubed 2D DCM)|url=https://www.plm.automation.siemens.com/en/products/open/d-cubed/2ddcm/index.shtml DCM] (Dimensional Constraint Manager),}}</ref> a commercial solver from D-Cubed (subsidiary of [[Siemens PLM Software]]), integrated in [[AutoCAD]], [[SolidWorks]], [[PTC Creo|Creo]], and many other popular CAD systems;<ref>{{cite web|title=D-Cubed Customers|url=https://www.plm.automation.siemens.com/en/products/open/d-cubed/customers/}}</ref>
* [LGS,<ref>{{cite web|title=Bricsys Component Technology for Constraint Management in 2D/3D|url=https://www.bricsys.com/el-gr/applications/developers/components/ LGS],}}</ref> a commercial solver developed by LEDAS and currently owned by Bricsys, integrated in [[Cimatron#CimatronE|Cimatron E]] and [[BricsCAD]];<ref>{{cite news|title=Cimatron to Introduce New Motion Simulator Powered by LEDAS LGS 3D|url=http://www.3dcadinfo.com/news/1794/cimatron-to-introduce-new-motion-simulator-powered-by-ledas-lgs-3d/}}</ref><ref>{{cite web|title=Exclusive Q&A: What it means, now that Bricsys bought IP from Ledas|url=http://worldcadaccess.typepad.com/blog/2011/10/exclusive-qa-what-it-means-now-that-bricsys-bought-ip-from-ledas.html}}</ref>
* C3D Solver,<ref>{{cite web|title=C3D Solver|url=http://c3dlabs.com/en/products/solver/}}</ref> a commercially available solver which is a part of [[C3D Toolkit]], integrated into KOMPAS-3D;<ref>{{cite web|title=C3D Toolkit|url=http://c3dlabs.com/en/products/c3d-kernel/}}</ref>
* [httpGeoSolver,<ref>{{cite web|title=GeoSolver Project Page|url=https://geosolver.sourceforge.net/ GeoSolver],}}</ref> a [[GNU General Public License]] [[Python (programming language)|Python]] package for geometric constraint solving.
* [[SolveSpace]], open-source CAD that ships with its own integrated geometric constraint solver
== See also ==
* [[Geometric modeling kernel]]
== References ==
{{Reflist}}
<!--- Categories --->
[[Category:Constraint programming]]
[[Category:Articles created via the Article Wizard]]
| 