Calcul de l'enveloppe convexe d'un objet représente sous forme polyédrique. Application à la robotique

Le calcul de l'enveloppe convexe d'un objet est un problème déjà largement traité. Les différents algorithmes se basent sur la liste des sommets et leur complexité minimum est en o(n log n) (n est le nombre de sommets). A partir de la représentation polyédrique de l'objet, il est possible de diminuer cette complexité. Le principe de l'algorithme, écrit en LISP (15000 cellules) est le suivant : * classification des arêtes : convexe ou concave * classification des sommets : éliminé ou pouvant appartenir à l'enveloppe convexe * création de circuits (liste de sommets reliés par des arêtes convexes entourant une région concave de l'objet) * création de l'enveloppe convexe à partir des circuits et des régions convexes de l'objet La "complexité" est fonction de l'objet étudié et est au plus en o(n log n). Plusieurs utilisations de cet algorithme sont intéressantes en robotique : - le calcul des positions de repos d'un objet sur un plan par projection du centre de masse sur chaque face ; il est alors possible de déterminer le contour bidimensionnel correspondant à chaque position et d'extraire les informations nécessaires à son identification et sa saisie par comparaison avec les données fournies par un capteur de vision. Cet exemple est illustré dans l'article ; - dans les recherches de trajectoires sans collision, travailler sur les enveloppes convexes diminue la complexité des algorithmes et les temps de calcul