Algorithme de Fortune
L'algorithme de Fortune est un algorithme pour calculer le diagramme de Voronoï d'un ensemble de points. C'est un algorithme de balayage : une droite balaie l'ensemble de points dans une certaine direction, l'algorithme met à jour la construction, et lorsque tous les points ont été balayés, le diagramme est construit.
Principe modifier
L'idée générale consiste à balayer le plan de gauche à droite avec une ligne verticale ; on construit le diagramme de Voronoï progressivement. Le problème est que le diagramme déjà construit, à gauche de la ligne, dépend de points situés à droite de cette ligne, et donc non encore pris en compte. Fortune résout ce problème en considérant un front parabolique légèrement « en retard » par rapport à la droite de balayage, tel que le diagramme situé à gauche de ce front est le diagramme final.
Description modifier
Une droite (D) balaie le diagramme (sweep line) ; par convention, on prend une droite verticale balayant de gauche à droite. À gauche de cette droite se situe la « berge » ou « plage » (anglais : beach) : il s'agit d'une courbe faite d'arcs de parabole. Lorsque la droite de balayage passe le premier germe rencontré, p1, on peut déterminer la zone qui est plus proche du germe que de la droite ; les points équidistants entre le germe et la droite forment une parabole (notion de foyer et de directrice).
Lorsque la droite de balayage passe un deuxième germe p2, cela définit un deuxième arc de parabole. Le point d'intersection I des deux arcs de parabole vérifie :
- la distance d(I, (D)) = d(I, p1) puisqu'il est sur la première parabole ;
- d(I, (D)) = d(I, p2) puisqu'il est sur la deuxième parabole ;
donc
- d(I, p1) = d(I, p2) donc l'intersection se trouve sur la paroi de la cellule séparant p1 de p2.
Lorsque (D) passe le troisième germe p3, cela ajoute une troisième parabole à la berge. Si les trois points ne sont pas alignés, il existe un cercle de centre C passant par ces points. Lorsque (D) est tangente à ce cercle, alors :
- d(C, p1) = d(C, p2) = d(C, p3) = d(C, (D))
donc les trois paraboles sont concourantes en C, donc on est en présence d'un nœud du diagramme de Voronoï. Par ailleurs, à partir de ce moment-là, la parabole générée par p1 sera toujours plus à gauche que l'intersection des paraboles générées par p2 et p3. On peut donc supprimer de la berge un des arcs de la parabole générée par p1.
La berge a la structure d'un arbre binaire de recherche (combinaison des différentes paraboles), avec un temps de recherche en O(n log n). L'algorithme garde également en file d'attente les événements qui vont modifier la berge :
- apparition d'une nouvelle parabole, lorsque la ligne de balayage rencontre un nouveau germe ;
- disparition d'un arc de parabole, lorsque la ligne de balayage est tangente au cercle passant par trois germes générant des arcs de parabole contigus (nœud du diagramme).
La ligne de balayage peut évidemment être horizontale et balayer le plan de haut en bas[1].
Complexité modifier
L'algorithme a une complexité en O(n log n) en temps[2] et en O(n) en espace mémoire.
Histoire modifier
L'algorithme est dû à Steven Fortune (1987, Laboratoires Bell AT&T)[3].
Autres algorithmes modifier
D'autres algorithmes pour le problème sont l'algorithme de Green et Sibson, un algorithme incrémental de complexité quadratique, et l'algorithme de Shamos et Hoey, un algorithme en O(n log n) de type diviser pour régner[2].
Notes et références modifier
- Cet article est partiellement ou en totalité issu de l'article intitulé « Diagramme de Voronoï » (voir la liste des auteurs).
- http://www.cs.sfu.ca/~binay/813.2011/Fortune.pdf
- Franck Hétroy, « Un peu de géométrie algorithmique, 4.2 Voronoı̈ : construction incrémentale », sur ENSIMAG.
- (en) Steven Fortune, « A Sweepline Algorithm for Voronoi Diagrams », Algorithmica, Springer-Verlag, vol. 1, , p. 153-174
