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

Abstract : 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.
Complete list of metadatas

Contributor : Rémi Imbach <>
Submitted on : Thursday, March 26, 2015 - 3:51:53 PM
Last modification on : Saturday, October 20, 2018 - 1:17:44 AM
Long-term archiving on: Monday, April 17, 2017 - 10:02:18 PM


Files produced by the author(s)


  • HAL Id : hal-01135230, version 1
  • ARXIV : 1503.07901


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⟩



Record views


Files downloads