Algorithme de Fortune

Animation de l'algorithme de Fortune.

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.

Dans l'image du milieu, la berge contient deux arcs de parabole verts. Lorsque la droite de balayage est tangente au cercle passant par les trois germes (image de droite), l'arc de parabole vert du bas est supprimé de la berge.

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é, p₁, 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 p₂, 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, p₁) puisqu'il est sur la première parabole ;
• d(I, (D)) = d(I, p₂) puisqu'il est sur la deuxième parabole ;

donc

d(I, p₁) = d(I, p₂) donc l'intersection se trouve sur la paroi de la cellule séparant p₁ de p₂.

Lorsque (D) passe le troisième germe p₃, 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, p₁) = d(C, p₂) = d(C, p₃) = 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 p₁ sera toujours plus à gauche que l'intersection des paraboles générées par p₂ et p₃. On peut donc supprimer de la berge un des arcs de la parabole générée par p₁.

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].

L'algorithme a une complexité en O(n log n) en temps[2] et en O(n) en espace mémoire.

L'algorithme est dû à Steven Fortune (1987, Laboratoires Bell AT&T)[3].

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].

• Cet article est partiellement ou en totalité issu de l'article intitulé « Diagramme de Voronoï » (voir la liste des auteurs).