Geometric constraint solving: Difference between revisions

Revision as of 15:32, 4 December 2022

Revision as of 08:38, 30 January 2023

Line 7:

== Methods ==

A general scheme of geometric constraint solving consists 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 journal|title=A formalization of geometric constraint systems and their decomposition|journal=Formal Aspects of Computing|volume=22|issue=2|pages=129–151|last1=Pascal Mathis|last2=Simon E. B. Thierry|doi=10.1007/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 journal|title=Decomposition Plans for Geometric Constraint Systems, Part I: Performance Measures for CAD|journal=Journal of Symbolic Computation|volume=31|issue=4|pages=367–408|last1=Christoph M.Hoffman|last2=Andrew Lomonosov|last3=Meera Sitharam|doi=10.1006/jsco.2000.0402|year=2001|doi-access=free}}</ref><ref>{{cite journal|title=Decomposition Plans for Geometric Constraint Problems, Part II: New Algorithms|journal=Journal of Symbolic Computation|volume=31|issue=4|pages=409–427|last1=Christoph M.Hoffman|last2=Andrew Lomonosov|last3=Meera Sitharam|doi=10.1006/jsco.2000.0403|year=2001|doi-access=free}}</ref> tree decomposition,<ref>{{cite journal|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=https://upcommons.upc.edu/bitstream/2117/78683/8/main.pdf|hdl-access=free}}</ref> C-tree decomposition,<ref>{{cite journal|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=https://hal.inria.fr/inria-00517706/file/Xiao-ShanGao2006a.pdf}}</ref> graph reduction,<ref>{{cite journal|title=A 2D geometric constraint solver using a graph reduction method|journal=Advances in Engineering Software|volume=41|issue=10–11|pages=1187–1194|last1=Samy Ait-Aoudia|last2=Sebti Foufou|doi=10.1016/j.advengsoft.2010.07.008|year=2010}}</ref> re-parametrization and reduction,<ref>{{cite journal|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=https://hal.archives-ouvertes.fr/hal-01205755/file/Re-Parameterization-Barki-etAl-CAD-2016.pdf}}</ref> computing fundamental circuits,<ref>{{cite journal|title=Decomposition of geometric constraint graphs based on computing fundamental circuits. Correctness and complexity|journal=Computer-Aided Design|volume=52|pages=1–16|last1=R.Joan-Arinyo|last2=M.Tarrés-Puertas|last3=S.Vila-Marta|doi=10.1016/j.cad.2014.02.006|year=2014}}</ref> body-and-cad structure,<ref>{{cite journal|title=Body-and-cad geometric constraint systems|journal=Computational Geometry|volume=45|issue=8|pages=385–405|last1=Kirk Haller|last2=Audrey Lee-St.John|last3=Meera Sitharam|last4=Ileana Streinu|last5=Neil White|doi=10.1016/j.comgeo.2010.06.003|year=2012|arxiv=1006.1126}}</ref> or the witness configuration method.<ref>{{cite journal|title=Geometric constraint solving: The witness configuration method|journal=Computer-Aided Design|volume=38|issue=4|pages=284–299|last1=Dominique Michelucci|last2=Sebti Foufou|doi=10.1016/j.cad.2006.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 journal|title=A geometric constraint solver for 3-D assembly modeling|journal=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=10.1007/s00170-004-2391-1|year=2006|s2cid=120186972 }}</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|s2cid=775489|year=1998|doi=10.1016/s0010-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 journal|title=Stabilizing 3D modeling with geometric constraints propagation|journal=Computer Vision and Image Understanding|volume=113|issue=11|pages=1147–1157|last1=Michela Farenzena|last2=Andrea Fusiello|doi=10.1016/j.cviu.2009.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 = Parallel Problem Solving from Nature — PPSN VII|volume = 2439|pages=759–768|series = Lecture Notes in Computer Science|year = 2002|isbn = 978-3-540-44139-7}}</ref>