Un algorithme exact et performant, basé sur les sommets contributeurs, pour le calcul de la somme de Minkowski d’une paire de polyèdres non convexe/convexe

National audienceNous présentons l’algorithme NCC-CVMS : un algorithme exact et efficace, basé sur la notion de sommets contributeurs, pour le calcul de la Somme de Minkowski (SM) d’une paire de polyèdres non convexe/convexe fermés et des 2-variétés, sans décomposition en convexes et sans calcul d’union. Premièrement, nous générons un surensemble réduit (avec un nombre minimum de facettes) des facettes du polyèdre SM en exploitant la notion de sommets contributeurs. Deuxièmement, nous calculons les arrangements 2D induits par les intersections des triangles de ce sur-ensemble. Enfin, nous obtenons la SM par l’utilisation de deux propriétés simples des polyèdres d’entrée et du polyèdre SM lui-même, à savoir la propriété de fermeture et celle de 2-variété. L’algorithme NCCCVMS est performant grâce aux simplifications induites par l’utilisation de la notion de sommets contributeurs, l’utilisation des arrangements et l’utilisation des propriétés simples de fermeture et de 2-variété afin de reconstruire le polyèdre SM. Toutefois, notre algorithme ne reconstruit pas les trous éventuellement présents à l’intérieur du polyèdre SM. Nous avons implanté notre algorithme NCC-CVMS en utilisant la bibliothèque CGAL et les types de nombres exacts