|
Algorithme de FortuneL'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 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 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 :
donc
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 :
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 :
La ligne de balayage peut évidemment être horizontale et balayer le plan de haut en bas[1]. ComplexitéL'algorithme a une complexité en O(n log n) en temps[2] et en O(n) en espace mémoire. HistoireL'algorithme est dû à Steven Fortune (1987, Laboratoires Bell AT&T)[3]. Autres algorithmesD'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
|
