Décomposition et paramétrisation de systèmes de contraintes géométriques sous-contraint

La résolution de systèmes de contraintes géométriques (GCS) a pour objectif de produire des figures qui respectent une description technique fournie par l'utilisateur sous la forme d'une esquisse cotée. Le GCS donné par l'utilisateur peut être bien contraint (il décrit un nombre fini non nul de figures), sous-contraint (une infinité de figures) ou sur-contraint (aucune solution). Classiquement, les systèmes sous-contraints sont considérés comme des cas d'erreur que l'utilisateur doit corriger en ajoutant des contraintes. Nos travaux proposent une autre approche, qui est celle de chercher à résoudre de manière homogène tous les systèmes de contraintes géométriques qui ne sont pas sur-contraints. Pour cela, nous proposons des algorithmes de paramétrisation, qui indiquent quels éléments du système doivent être fixés pour qu'il y ait un nombre fini de solutions, et des algorithmes de décomposition, qui permettent d'identifier les sous-systèmes bien contraints. Ces outils ouvrent la voie à des logiciels de modélisation par contraintes accessibles à des utilisateurs non-experts: ils permettent des retours visuels intuitifs sur le niveau de constriction du système. Comme nos algorithmes sont incrémentaux, ils permettent une approche par essai/erreur où l'utilisateur corrige l'esquisse au fur et à mesure de la résolution.Solving geometric constraint systems (GCS) aims at yielding figures which respect geometric requirements given by the user under the form of a technical sketch. The GCS given by the user can be wellconstrained (it describes a nonzero finite number of figures), underconstrained (an infinity of figures) or overconstrained (no solutions at all). Classically, underconstrained systems are considered as errors to be corrected by the user. Our work proposes another approach, i.e. try to homogeneously solve all nonoverconstrained systems. For that, we propose parameterization algorithms: they indicate which elements of the system need to be anchored for there to be a finite number of solutions~; and decomposition algorithms, which allow to identify wellconstrained subsystems. These tools open the way to constraintbased modelers which are accessible to nonexpert users: they give intuitive visual feedback about the constrainedness level of the system. Since our algorithms are all incremental, they allow a trial and error approach: the user corrects the sketch as the resolution goes.STRASBOURG-Sc. et Techniques (674822102) / SudocSudocFranceF