Combination of symbolic and numeric methods

The core technology of LGS 3D consists of a combination of symbolic and numerical methods for solving systems of geometric constraints.

One of the most significant classes of symbolic methods used in LGS 3D is a set of methods of geometric decomposition. The strong point of these methods is their ability to decompose a complex geometric problem (with hundreds of constraints) into a sequence of simpler ones. Solving them one by one, LGS 3D finds a solution for the initial problem. Some of the methods are rapid heuristics and some are efficient universal methods.

After decomposition of input problems LGS 3D processes the detected subproblems by mapping their geometric specification into a system of polynomial or trigonometric equations. Resolution of such a system allows solving the initial geometric problem. Different mappings can be used in order to convert geometric problems into systems of equations. LGS 3D uses Ñartesian mapping since it allows choosing from set of possible solutions the solution that has minimal quantity of rotations and translations of geometric objects.

LGS 3D contains powerful processor for solving systems of equations numerically. This processor also uses some symbolic methods for rewriting of system of equations, most efficient of them being algebraic decomposition method that permits to divide system of equations into smaller subsystems. The set of numerical methods implemented in the processor includes modified Newton method, Newton-Lagrange and gradient methods. Newton method is greatly tuned for the class of system of equations generated from geometric specifications. It uses also efficient adaptive strategy of Newton step choosing.

LGS 3D uses special know-how technique in order to obtain a so called natural solution for geometric problems, i.e. a solution that is expected by user. It permits us to not use time-consuming homotopy continuation method that is common used routine for computation of natural solutions. LGS 3D supports on all levels of its code priorities of parameters that allow obtaining solutions as naturally as it is possible.

LGS 3D Architecture

Geometric solver has a fine-grained modular architecture that makes it possible to efficiently process and resolve geometric problems. Through LGS 3D API one can create a model, add geometric objects and rigid sets into it and specify constraints between objects. After computations user can obtain solution as a set of transformations of rigid sets.

Main parts of LGS 3D are decomposition, mapping and resolution modules.

Geometric decomposition using constraint graph analysis is used to reduce the size of computational models and hence achieve better performance. This module is fully extensible and a number of decomposition methods will be implemented in this module before LGS 3D 1.0 release.

Mapping module uses Cartesian mapping as main technique of converting of a geometric specification into a system of equations. This module can also be extended by different mappings routines.

LGS 3D uses powerful processor for solving of system of equations numerically - this processor is used also in our LGS 2D solver, so it is properly tuned and tested during the LGS 2D development and maintenance.