Note ABES Résolution de contraintes géométriques en guidant une méthode homotopique par la géométrie Solving geometric constraints by a continuation method led by geometry Résolution de contraintes géométriques Méthodes par continuation Homotopie Méthodes Hybrides Modélisation géométrique Geometric constraints solving Continuation methods Homotopy Hybrid methods Geometric modeling 514.2 Homotopie Contraintes (intelligence artificielle) Modèles géométriques Modélisation tridimensionnelle Suivant le domaine où on les sollicite, les solutions d’un système de contraintes géométriques (SCG) peuvent être : – formelles et exactes : elles prennent par exemple la forme d’un plan de construction produisant toutes les solutions, obtenu en appliquant des règles dérivées de lemmes de géométrie. Beaucoup de SCG, surtout en 3D, résistent à cette approche ; – numériques et approchées : elles sont les solutions d’un système d’équations construit à partir des contraintes et trouvées grâce à des méthodes numériques efficaces quand elles ne recherchent qu’une solution. De par la nature des problèmes traités, chercher toutes les solutions conduit à une complexité exponentielle. Les méthodes par continuation, ou homotopie, permettent d’obtenir toutes les solutions d’un système d’équations polynomiales. Leur application à des SCG est coûteuse et difficilement sujette aux raisonnements permis par l’origine géométrique du problème car elles opèrent hors de l’espace des figures géométriques. Notre travail a pour objet la spécialisation d’une méthode par continuation à des SCG. La géométrie simplifie et justifie sa mise en œuvre dans l’espace des figures, ou des raisonnements géométriques sont possibles. On aborde également les cas ou l’ensemble de solutions d’un problème contient des éléments isolés et des continuums. Des solutions proches d’une esquisse fournie par un utilisateur sont d’abord trouvées. La recherche d’autres solutions, malgré sa complexité exponentielle, est rendue envisageable par une approche itérative. Une nouvelle méthode de décomposition est proposée pour maîtriser le coût de la résolution. Depending on the required application field, the solutions of a geometric constraints system (GCS) are either : – symbolic and exact such as construction plans, providing all the solutions, obtained by applying geometric rules. Many problems, mostly in a 3D context, resist to this approach ; – or numerical and approximated : they are the solutions of a system of equations built from the constraints, provided by generical numerical methods that are efficient when only one solution is sought. However, searching all the solutions leads to an exponential computation cost, due to the nature of problems. Continuation methods, also called homotopic methods, find all the solutions of a polynomial system. Using them to solve systems of equations associated to systems of constraints is nevertheless costly. Moreover, combining them with geometric reasoning is a challenge, because they act in a projective complex space and not in the realizations space. The aim of this work is to specialize a continuation method to GCS. Geometry is exploited to simplify and justify its adaptation in the space of realizations, so allowing geometric reasoning. Cases where the connected components of the solution space of a problem have heterogeneous dimensions are addressed. The method discussed here provides in a first step solutions that are similar to a sketch drawn by the user. Then a procedure is proposed to search new solutions. Its iterative nature seems to make the exponential complexity of this task bearable. A new decomposition method is proposed, that restrains the resolution cost. Electronic Thesis or Dissertation Text fr PDF 2435782 Université de Strasbourg Strasbourg 2014-12-31 https://theses.hal.science/tel-01124176 application/pdf 2244143 https://publication-theses.unistra.fr/public/theses_doctorat/2013/imbach_remi_2013_ED269.pdf http://www.theses.fr/2013STRAD033/abes https://theses.hal.science/tel-01124176 https://theses.hal.science/tel-01124176 https://theses.hal.science/tel-01124176 Imbach Rémi 1985-12-07 FR 176716556 40201599 https://theses.fr/2013STRAD033 2013STRAD033 https://doi.org/10.70675/d477773ezb91cz4990z9283zc561a0a6758d 2013-10-08 Informatique Strasbourg 131056549 Doctorat Docteur es non oui Schreck Pascal MADS_DIRECTEUR_DE_THESE_1 115931589 Tajine Mohamed MADS_PRESIDENT_DU_JURY 12850210X Mathis Pascal MADS_MEMBRE_DU_JURY_1 182451313 Serré Philippe MADS_MEMBRE_DU_JURY_2 182451305 Michelucci Dominique MADS_RAPPORTEUR_1 032984189 Mourrain Bernard MADS_RAPPORTEUR_2 050178725 École doctorale Mathématiques, sciences de l'information et de l'ingénieur (Strasbourg ; 1997-....) MADS_ECOLE_DOCTORALE_1 MA 156504863 Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (Strasbourg ; 2013-....) MADS_PARTENAIRE_DE_RECHERCHE_1 UMR7357 176969721 217648 ddc:510 Schreck Pascal Tajine Mohamed Mathis Pascal Serré Philippe Michelucci Dominique Mourrain Bernard École doctorale Mathématiques, sciences de l'information et de l'ingénieur (Strasbourg) Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (Strasbourg) PDF 2435782