Accueil🇫🇷Chercher

Algorithme de Shamos

En géométrie algorithmique, l'algorithme de Shamos ou mergehull est un algorithme pour le calcul de l'enveloppe convexe. C'est un algorithme de type diviser pour régner.

Principe

Le principe de l'algorithme est le suivant pour un ensemble de points E. On décompose notre ensemble E en deux ensembles E1 et E2. On calcule ensuite par récursivité l'enveloppe convexe de E1 et E2. Finalement, on construit l'enveloppe convexe de E à partir de celles de E1 et E2 où EC(E) = EC(EC(E1) U EC(E2)).

L'algorithme

 Procedure MERGEHULL(S)
   1. Si |S| ≤ k (k petit entier), on construit l'enveloppe convexe directement à partir d'une méthode et on s'arrête. Sinon, on passe à la deuxième 
   étape.
   2. On divise S en S1 et S2 de longueurs égales approximativement.
   3. Récursivement, on cherche l'enveloppe convexe de S1 et S2.
   4. On fusionne les deux enveloppes pour former l'enveloppe convexe de S.

La quatrième étape repose sur l'utilisation d'un algorithme de fusion.

 Procedure HULL OF UNION OF CONVEX POLYGONS(P1,P2)
   1. On cherche p un point interne à P1 (par exemple : le centre de masse de trois points de P1). p est interne à EC(P1UP2)
   2. On détermine si p est interne à P2. Si p n'est pas interne à P2, on passe à l'étape 4.
   3. p est interne à P2. Les points de P1 et P2 sont dans un ordre angulaire croissant. 
      On fusionne en temps linéaire les deux listes pour obtenir une liste des points de P1 et P2. On passe à l'étape 5.
   4. p n'est pas interne à P2. Vu à partir de p, P2 se trouve dans un coin angulaire d'angle < pi. 
      Ce coin est défini à partir de deux points u et v que l'on retrouve en temps linéaire. 
      Ces points divisent P2 en deux chaînes de points. On ne s'intéresse pas à la chaîne convexe vers p. 
      L'autre chaîne de P2 et P1 (privé des points à l'intérieur de P2) forment deux listes triés qui contiennent au plus N points. 
      Elles peuvent être fusionnées en temps linéaire pour former une liste de points de P1UP2, triés en P2.
   5. Le scan de Graham peut être effectué sur la liste obtenue.

Complexité

L'algorithme a une complexité en temps de O(n.log(n))[1].

Histoire

L'algorithme apparaît dans le livre Computational Geometry - An Introduction en 1985, de Michael Ian Shamos et Franco P.Preparata[1].

Notes et références

  1. (en) Franco P.Preparata, Michael Ian Shamos, Computational Geometry, An Introduction, Springer, , pages 116, 117

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.