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[modifier | modifier le code]
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[modifier | modifier le code]
- Procédure Mergehull(s)
- 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.
- On divise S en S1 et S2 de longueurs égales approximativement.
- Récursivement, on cherche l'enveloppe convexe de S1 et S2.
- 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.
- Procédure Hull of Union of Convex Polygons (P1,P2)
- On cherche p un point interne à P1 (par exemple : le centre de masse de trois points de P1). p est interne à EC(P1UP2)
- On détermine si p est interne à P2. Si p n'est pas interne à P2, on passe à l'étape 4.
- 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.
- 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.
- Le scan de Graham peut être effectué sur la liste obtenue.
Complexité[modifier | modifier le code]
L'algorithme a une complexité en temps de O(n.log(n))[1].
Histoire[modifier | modifier le code]
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[modifier | modifier le code]
- (en) Franco P. Preparata, Michael Ian Shamos, Computational Geometry, An Introduction, Springer, , pages 116, 117
Article connexe[modifier | modifier le code]
Liens externes[modifier | modifier le code]