Contributing Vertices-based Minkowski sum of a non-convex polyhedron without fold and a convex polyhedron

International audienceNous présentons une approche originale pour le calcul de la somme de Minkowski d'un polyèdre non convexe sans repli et d'un polyèdre convexe, sans décomposition et sans union (étapes qui constituent l'inconvénient des approches basées sur la décomposition). Un polyèdre non convexe est un polyèdre sans repli si sa surface extérieure est complètement reconstructible à partir de trois projections orthographiques, définies par trois vecteurs orthogonaux de base dans R3. Tout d'abord, nous générons un sur-ensemble des facettes de la somme Minkowski en utilisant le concept des sommets contributeurs que nous adaptons pour une paire de polyèdres non-convexe/convexe. Le sur-ensemble généré garantit que son enveloppe est la surface extérieure du polyèdre somme de Minkowski. Deuxièmement, nous extrayons les facettes de la somme de Minkowski et gérons les intersections entre les facettes du sur-ensemble en utilisant des enveloppes de surfaces 3D. Notre approche est limitée à des polyèdres non convexes sans repli en raison de l'utilisation des enveloppes de surface pour la reconstruction de la surface extérieure de la somme de Minkowski. Les polyèdres avec trous ne sont pas gérés par notre méthode. L'implantation de notre algorithme utilise des types de nombres exacts, produit des résultats exacts, et est basée sur CGAL, la "Computational Geometry Algorithms Library"