Algorithme de Shamos

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)).

 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.

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

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

• Quickhull