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
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
- 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
L'algorithme a une complexité en temps de O(n.log(n))[1].
Histoire modifier
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
- (en) Franco P. Preparata, Michael Ian Shamos, Computational Geometry, An Introduction, Springer, , pages 116, 117
Article connexe modifier
Liens externes modifier
