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.

En chirurgie mini-invasive guidée par l’image, une planification préopératoire précise des trajectoires des outils chirurgicaux est un facteur clé pour une intervention réussie. Cependant, une planification efficace est une tâche difficile, qui peut être considérablement améliorée en considérant différents facteurs contributifs tels que les déformations biomécaniques intra-opératoires, ou en introduisant de nouvelles techniques d'optimisation. Dans ce travail, nous nous concentrons sur deux aspects. Le premier aspect porte sur l'intégration de la déformation intra-opératoire dans le processus de planification de trajectoire. Nos méthodes combinent des techniques d'optimisation géométrique à base de simulations biomécaniques. Elles sont caractérisées par un certain niveau de généralité, et ont été expérimentées sur deux types d’interventions chirurgicales: les procédures percutanées pour l'ablation de tumeurs hépatiques, et la stimulation cérébrale profonde en neurochirurgie. Deuxièmement, nous étudions, mettons en œuvre, et comparons plusieurs approches d'optimisation en utilisant des méthodes qualitatives et quantitatives, et nous présentons une méthode efficace d'optimisation évolutionnaire multicritères à base de Pareto qui permet de trouver des solutions optimales qui ne sont pas accessibles par les méthodes existantes. / In image-guided minimally invasive surgery, a precise preoperative planning of the surgical tools trajectory is a key factor to a successful intervention. However, an efficient planning is a challenging task, which can be significantly improved when considering different contributing factors such as biomechanical intra-operative deformations, or novel optimization techniques. In this work, we focus on two aspects. The first aspect addresses integrating intra-operative deformation to the path planning process. Our methods combine geometric-based optimization techniques with physics-based simulations. They are characterized with a certain level of generality, and are experimented on two different surgical procedures: percutaneous procedures for hepatic tumor ablation, and in neurosurgery for Deep Brain Stimulation (DBS). Secondly, we investigate, implement, and compare many optimization approaches using qualitative and quantitative methods, and present an efficient evolutionary Pareto-based multi-criteria optimization method which can find optimal solutions that are not reachable via the current state of the art methods.