Geometric constraint solving: Difference between revisions

Revision as of 04:21, 28 December 2017

Revision as of 04:21, 28 December 2017

Line 1:

{{AFC submission|t||ts=20171103112212|u=Ilya.lichman|ns=118|demo=}}

{{Userspace draft|source=ArticleWizard|date=November 2017}}

Geometric constraint solving is [[constraint satisfaction]] in a computational geometry, 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=http://www.springer.com/gp/book/9783642637810|language=en}}</ref> A 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 geometric elements in 2D or 3D space that satisfy the given constraints,<ref>{{cite book|last1=Christoph M. Hoffmann|last2=Pamela J. Vermeer|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.

Line 10 ⟶ 7:

== Methods ==

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>

Line 28 ⟶ 25:

* [http://c3dlabs.com/en/products/solver/ C3D Solver], 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>

* [http://geosolver.sourceforge.net/ GeoSolver], a [[GNU Public License]] [[Python (programming language)|Python]] package for geometric constraint solving.

== References ==

Line 36 ⟶ 32:

<!--- Categories --->

[[:Category:Constraint programming]]

[[:Category:Articles created via the Article Wizard]]

{{AFC submission|||ts=20171103051517|u=Ilya.lichman|ns=2}}