Calcul de l'enveloppe convexe — Wikipédia
En algorithmique géométrique, le calcul de l'enveloppe convexe est un problème algorithmique. Il consiste, étant donné un ensemble de points, à calculer leur enveloppe convexe.
Définition
[modifier | modifier le code]![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/bc/ConvexHull.png/220px-ConvexHull.png)
L'enveloppe convexe d'un ensemble de points est le plus petit ensemble convexe qui les contient tous[1]. C'est un polyèdre dont les sommets sont des points de l'ensemble. Le calcul de l'enveloppe convexe consiste à calculer une représentation compacte de l'enveloppe, le plus souvent les sommets de celle-ci.
C'est un problème ayant de nombreuses applications, par exemple en analyse de forme et reconnaissance de formes, et qui est central en géométrie algorithmique[1].
Algorithmes pour le cas planaire
[modifier | modifier le code]Le cas planaire est le cas où les points sont disposés dans le plan. On mesure la complexité en temps en fonction du nombre de points de l'entrée n, et du nombre de points sur l'enveloppe h. Il existe de nombreux algorithmes pour ce cas.
Marche de Jarvis
[modifier | modifier le code]L'idée de la marche de Jarvis (ou gift wrapping algorithm) est d' « envelopper » l'ensemble de points dans un « papier cadeau » : on accroche ce papier à l'un des points, on le tend, puis on tourne autour du nuage de points. La complexité de l'algorithme est O(nh).
Parcours de Graham
[modifier | modifier le code]Le parcours de Graham (aussi appelé Graham scan[2]) consiste à trouver le point de plus petite abscisse, à trier tous les autres points par rapport à l'angle qu'ils font avec ce dernier (et l'axe des abscisses), puis à considérer les triplets de points successifs, pour déterminer lesquels sont dans l'enveloppe. Sa complexité est celle du tri, c'est-à-dire O(n log(n)).
Algorithme de Chan
[modifier | modifier le code]L'algorithme de Chan procède en plusieurs étapes. D'abord un partitionnement des points en plusieurs groupes, puis le calcul des enveloppes convexes de ces groupes avec un algorithme en O(n log(n)) (comme le parcours de Graham), et enfin une marche de Jarvis utilisant ces enveloppes déjà calculées. Sa complexité est en O(n log(h)).
Quickhull
[modifier | modifier le code]Quickhull est un algorithme de type diviser pour régner. Sa complexité moyenne est O(n.log(n)). Sa complexité dans le pire des cas est O(n²).
Algorithme de Shamos
[modifier | modifier le code]L'algorithme de Shamos est un algorithme de type diviser pour régner. Sa complexité est O(n log(n)).
Algorithme de Preparata-Hong
[modifier | modifier le code]L'Algorithme de Preparata-Hong est un algorithme de type diviser pour régner.
Algorithme de Kirkpatrick et Seidel
[modifier | modifier le code]L'algorithme de Kirkpatrick et Seidel (en) a une complexité en O(n log(h)).
Autres algorithmes
[modifier | modifier le code]D'autres algorithmes existent, comme l'algorithme d'Andrew.
Algorithmes pour les dimensions supérieures
[modifier | modifier le code]L'algorithme de Preparata-Hong fonctionne pour les dimensions 2 et 3.
Pour des dimensions supérieures à 2, l'algorithme quickhull et l'algorithme de Chan fonctionnent.
Approximation
[modifier | modifier le code]Il existe aussi des algorithmes pour donner une approximation de l'enveloppe convexe[1].
Notes et références
[modifier | modifier le code]- Franco P. Preparata et Michael Ian Shamos, « Convex hulls: Basic algorithms », dans Computational Geometry, Sringer, (présentation en ligne)
- Arnaud Jehanne, « Calculer une enveloppe convexe », sur Université de Bordeaux.
Liens externes
[modifier | modifier le code]- Dan Sunday, « The convex hull of a planar point set », sur Geomalgorithms.com
- Olivier Devillers, « Un joli algorithme géométrique et ses vilains problèmes numériques », sur Interstices,