En analyse de tolérances géométriques, une approche consiste à manipuler des polyèdres de R' issus d’ensembles de contraintes linéaires. La position relative entre deux surfaces quelconques d'un mécanisme est déterminée par des opérations (somme de Minkowski et intersection) sur ces polyèdres. Ces polyèdres ne sont pas bornés selon les déplacements illimités dus aux degrés d’invariance des surfaces et aux degrés de liberté des liaisons.Dans une première partie sont introduits des demi-espaces "bouchons" destinés à limiter ces déplacements afin de transformer les polyèdres en polytopes. Cette méthode implique de maîtriser l’influence des demi-espaces bouchons sur la topologie des polytopes résultants. Ceci est primordial pour garantir la traçabilité de ces demi-espaces dans le processus d’analyse de tolérances.Une seconde partie dresse un inventaire des problématiques de mise en oeuvre numérique des polytopes. L’une d’entre elles repose sur le choix d’une configuration de calcul (point et base d’expression, coefficients d’homogénéisation) pour définir un polytope. Après avoir montré que le changement de configuration de calcul est une transformation affine, plusieurs stratégies de simulations sont déclinées afin d’appréhender les problèmes de précision numérique et de temps de calculs. / In geometric tolerancing analysis area, a classical approach consists in handling polyhedrons coming from sets of linear constraints. The relative position between any two surfaces of a mechanism is determined by operations (Minkowski sum and intersection) on these polyhedrons. The polyhedrons are generally unbounded due to the inclusion of degrees of invariance for surfaces and degrees of freedom for joints defining theoretically unlimited displacements.In a first part are introduced the cap half-spaces to limit these displacements in order to transform the polyhedron into polytopes. This method requires controlling the influence of these additional half-spaces on the topology of calculated polytopes. This is necessary to ensure the traceability of these half-spaces through the tolerancing analysis process.A second part provides an inventory of the issues related to the numerical implementation of polytopes. One of them depends on the choice of a computation configuration (expression point and base, homogenization coefficients) to define a polytope. After proving that the modification of a computation configuration is an affine transformation, several simulation strategies are listed in order to understand the problems of numerical precision and computation time.

La modélisation géométrique d'un problème de gestion de la fabrication des mélanges (faisabilité simultanée de deux mélanges) fait apparaître des polytopes nouveaux résultant de la somme de triangles particuliers qui dans ce contexte sont appelés convexes de 2-mélanges. De façon plus générale, la somme de triangles peut être considérée comme la généralisation des zonotopes (somme de segments). De ce point de vue, l'étude menée ici fait apparaître que la propriété de zone associée à un segment du zonotope se généralise à trois demi-zones associées à chaque triangle; et que la complexité combinatoire (nombre de faces du polytope), par rapport au nombre de sommandes, est du même ordre de grandeur que celle des zonotopes. On traite également le problème de la construction de tels polytopes, des algorithmes optimaux en temps sont proposés. Concernant le problème particulier des mélanges, le premier cas non trivial est celui de mélanges à trois composantes qui nous place en dimension 6. L'appartenance d'un point au convexe de 2-mélanges détermine la faisabilité simultanée des mélanges. Les facettes de ce polytope sont décrites, en détail, dans le cas de la dimension 6, dans le but d'obtenir des conditions de faisabilité des deux mélanges. Le problème de la décomposition de polytopes en somme de Minkowski de polytopes plus simples est exposé, ainsi que les principaux résultats existant.

L’analyse de tolérances par des ensembles de contraintes repose sur la détermination de l’accumulation de variations géométriques par des sommes et intersections d’ensembles opérandes 6d. Les degrés de liberté des liaisons et les degrés d’invariance des surfaces génèrent des opérandes non-bornés (polyèdres), posant des problèmes de simulation. En 2014, L. Homria proposé une méthode pour résoudre ce problème, consistant à ajouter des limites artificielles(contraintes bouchon) sur les déplacements non-bornés. Même si cette méthode permet la manipulation d’objets bornés (polytopes), les contraintes bouchon augmentent la complexité des simulations. En réponse à cette difficulté, une méthode dérivée est proposée dans cette thèse.Cette méthode consiste à tracer et simplifier les contraintes bouchon au travers des opérations.Puis une seconde stratégie basée sur la décomposition d’un polyèdre en une somme d’un polytope et de lignes droites (associées aux déplacements non-bornés). Cette stratégie consiste à simuler d’une part les sommes de droites, et d’autre part, à déterminer la somme de polytopes dans un sous-espace de dimension inférieur à 6. Ces trois stratégies sont comparées au travers d’une application industrielle. Cela montre que la traçabilité des contraintes bouchons est un aspect fondamental pour contrôler leur propagation et pour réduire le temps de calcul des simulations. Toutefois, cette méthode exige encore de déterminer les limites des déplacements non-bornés. La deuxième méthode, adaptant systématiquement la dimension de l’espace de calcul, elle permet de diminuer davantage le temps de calcul. Ce travail permet d’envisager la mise en oeuvre de cette méthode selon des formulations statistiques avec la prise en compte des défauts de forme des surfaces. / The cumulative stack-up of geometric variations in mechanical systems can be modelled summing and intersecting sets of constraints. These constraints derive from tolerance zones or from contact restrictions between parts. The degrees of freedom (DOF) of jointsgenerate unbounded sets (i.e. polyhedra) which are difficult to deal with. L. Homri presented in 2014 a solution based on the setting of fictitious limits (called cap constraints) to each DOFto obtain bounded 6D sets (i.e. polytopes). These additional constraints, however, increase the complexity of the models, and therefore, of the computations. In response to this situation,we defined a derived strategy to control the effects of the propagation of the fictitious limits by tracing and simplifying the generated, new cap constraints. We proposed a second strategy based on the decomposition of polyhedra into the sum of a polytope and a set of straight lines.The strategy consists in isolating the straight lines (associated to the DOF) and summing the polytopes in the smallest sub-space. After solving an industrial case, we concluded that tracing caps constraints during the operations allows reducing the models complexity and,consequently, the computational time; however, it still involves working in 6d even in caseswhere this is not necessary. In contrast, the strategy based on the operands decompositionis more efficient due to the dimension reduction. This study allowed us to conclude that the management of mechanisms’ mobility is a crucial aspect in tolerance simulations. The gain on efficiency resulting from the developed strategies opens up the possibility for doing statistical treatment of tolerances and tolerance synthesis.

La morphologie mathématique est une théorie puissante pour l’analyse d’images 2 D. Elle se base sur la dilatation et l’érosion, qui correspondent à l’addition et la soustraction de Minkowski. Afin d’analyser des maillages 3D par morphologie mathématique, on doit disposer d’algorithmes performants et robustes pour le calcul exact de l’addition et de la soustraction pour ces maillages. Malheureusement, les travaux existants sont, soit approximés, soit non robustes ou limités par des contraintes. Aucun travail n’a traité la différence. Ces difficultés sont dues au fait qu’un maillage représente une surface linéaire par morceaux englobant un ensemble contenu et non dénombrable. Nous avons introduit la notion de sommets contributeurs et nous avons développé un algorithme efficace et robuste pour le calcul de la somme de polyèdres convexes. Nous l’avons par la suite adapté et proposé deux algorithmes performants pour la somme d’une paire de polyèdres non convexe/convexe, tout en gérant correctement les polyèdres complexes, les situations de non-variété ainsi que les changements topologiques. Nous avons également démontré la dualité des sommets contributeurs et nous l’avons exploité pour développer la première approche du calcul exact et efficace de la différence de polyèdres convexes. La dualité des sommets contributeurs ainsi que la robustesse et l’efficacité de nos approches motivent le développement d’une approche unifiée pour l’addition et la soustraction de polyèdres quelconques, ce qui permettra d’appliquer des traitements morphologiques à des maillages 3D. D’autres domaines tels que l’imagerie médicale, la robotique, la géométrie ou la chimie pourront en tirer profit / Mathematical morphology is a powerful theory for the analysis of 2D digital images. It is based on dilation and erosion, which correspond to Minkowski addition and subtraction. To be able to analyze 3D meshes using mathematical morphology, we must use efficient and robust algorithms for the exact computation of the addition and subtraction of meshes. Unfortunately, existing approaches are approximated, non-robust or limited by some constraints. No work has addressed the difference. These difficulties come from the the fact that a mesh represents a piecewise linear surface bounding a continuous and uncountable set. We introduced the concept of contributing vertices and developed an efficient and robust algorithm for the computation of the Minkowski sum of convex polyhedra. After that, we adapted and proposed two efficient algorithms for the computation of the Minkowski sum of a non-convex/convex pair of polyhedra, while properly handling complex polyhedra, non-manifold situations and topological changes. We also demonstrated the duality of the contributing vertices concept and exploited it to develop the first approach for the efficient and exact computation of the Minkowski difference of convex polyhedra. The duality of the contributing vertices concept as well as the robustness and efficiency of our approaches motivate the development of a unified approach for the Minkowski addition and subtraction of arbitrary polyhedral, which will permit the morphological analysis of 3D meshes. Other areas such as medical imaging, robotics, geometry or chemistry may benefit from our approaches

Un problème courant en logistique, gestion d’entrepôt, industrie manufacturière ou gestion d’énergie dans les centres de données est de placer des objets dans un espace limité, ou conteneur. Ce problème est appelé problème de placement. De nombreux travaux dans la littérature gèrent le problème de placement en considérant des objets de formes particulières ou en effectuant des approximations polygonales. L’objectif de cette thèse est d’autoriser toute forme qui admet une définition mathématique (que ce soit avec des inégalités algébriques ou des fonctions paramétrées). Les objets peuvent notamment être courbes et non-convexes. C’est ce que nous appelons le problème de placement générique. Nous proposons un cadre de résolution pour résoudre ce problème de placement générique, basé sur les techniques d’intervalles. Ce cadre possède trois ingrédients essentiels : un algorithme évolutionnaire plaçant les objets, une fonction de chevauchement minimisée par cet algorithme évolutionnaire (coût de violation), et une région de chevauchement qui représente un ensemble pré-calculé des configurations relatives d’un objet (par rapport à un autre) qui créent un chevauchement. Cette région de chevauchement est calculée de façon numérique et distinctement pour chaque paire d’objets. L’algorithme sous-jacent dépend également du fait qu’un objet soit représenté par des inégalités ou des fonctions paramétrées. Des expérimentations préliminaires permettent de valider l’approche et d’en montrer le potentiel. / A common problem in logistic, warehousing, industrial manufacture, newspaper paging or energy management in data centers is to allocate items in a given enclosing space or container. This is called a packing problem. Many works in the literature handle the packing problem by considering specific shapes or using polygonal approximations. The goal of this thesis is to allow arbitrary shapes, as long as they can be described mathematically (by an algebraic equation or a parametric function). In particular, the shapes can be curved and non-convex. This is what we call the generic packing problem. We propose a framework for solving this generic packing problem, based on interval techniques. The main ingredients of this framework are: An evolutionary algorithm to place the objects, an over lapping function to be minimized by the evolutionary algorithm (violation cost), and an overlapping region that represents a pre-calculated set of all the relative configurations of one object (with respect to the other one) that creates an overlapping. This overlapping region is calculated numerically and distinctly for each pair of objects. The underlying algorithm also depends whether objects are described by inequalities or parametric curves. Preliminary experiments validate the approach and show the potential of this framework.