A Robust and Efficient Method for Solving Geometrical Constraint Problems by Homotopy - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2015

A Robust and Efficient Method for Solving Geometrical Constraint Problems by Homotopy

Résumé

The goal of Geometric Constraint Solving is to find 2D or 3D placements of some geometric primitives fulfilling some geometric constraints. The common guideline is to solve them by a numerical iterative method (e.g. Newton-Raphson method). A sole solution is obtained whereas many exist. But the number of solutions can be exponential and methods should provide solutions close to a sketch drawn by the user. Assuming that a decomposition-recombination planner is used, we consider irreducible problems. Geometric reasoning can help to simplify the underlying system of equations by changing a few equations and triangularizing it. This triangularization is a geometric construction of solutions, called construction plan. We aim at finding several solutions close to the sketch on a one-dimensional path defined by a global parameter-homotopy using the construction plan. Some numerical instabilities may be encountered due to specific geometric configurations. We address this problem by changing on-the-fly the construction plan. Numerical results show that this hybrid method is efficient and robust.
Fichier principal
Vignette du fichier
RR-8705.pdf (929.02 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01135230 , version 1 (26-03-2015)
hal-01135230 , version 2 (29-01-2016)
hal-01135230 , version 3 (25-07-2016)

Identifiants

Citer

Rémi Imbach, Pascal Mathis, Pascal Schreck. A Robust and Efficient Method for Solving Geometrical Constraint Problems by Homotopy. [Research Report] RR-8705, INRIA. 2015. ⟨hal-01135230v1⟩
271 Consultations
588 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More