Générer un diagramme de Voronoï avec l’algorithme de Fortune

 (redpenguin101.github.io)
2 points par GN⁺ 2025-02-10 | 1 commentaires | Partager sur WhatsApp
  • L’algorithme de Fortune permet de construire un diagramme de Voronoï en O(n log n), mais il est difficile à implémenter ; sauf si vous devez générer à répétition de grands diagrammes, une implémentation en O(n²) ou une bibliothèque sera plus réaliste
  • Un diagramme de Voronoï divise le plan en régions les plus proches de plusieurs sites ; ses frontières sont formées par les points à égale distance de deux sites
  • L’algorithme maintient une sweep line se déplaçant de gauche à droite et une beachline, front constitué d’arcs paraboliques, et ne traite que les site events et les circle events
  • Un site event insère un nouvel arc, scinde un arc existant et crée une incomplete edge ; un circle event supprime l’arc central tout en finalisant un sommet de Voronoï et une half edge
  • Dans une implémentation pratique, il faut gérer ensemble la file d’événements, la beachline, la table des incomplete edges et une DCEL ; l’élimination des circle events invalides et le nettoyage des arêtes restantes augmentent fortement la complexité

Difficulté d’implémentation et champ d’application

  • L’algorithme de Fortune génère un diagramme de Voronoï en O(n log n)
  • Pour un usage réel, il vaut mieux commencer par évaluer l’échelle nécessaire plutôt que de l’implémenter directement
    • Si vous n’avez pas besoin de générer plusieurs grands diagrammes par seconde, une implémentation en O(n²) peut être un choix plus simple
    • L’alternative la plus réaliste consiste à utiliser une bibliothèque existante
  • Le résultat visuel de l’algorithme est intéressant, mais son implémentation est délicate et souvent frustrante

Concepts de base du diagramme de Voronoï

  • Un diagramme de Voronoï est une façon de diviser le plan en plusieurs régions, souvent utilisée pour la génération procédurale de cartes
  • Les points choisis en entrée sont appelés sites ou seeds
  • La cell correspondant à chaque site est l’ensemble des points du plan les plus proches de ce site
  • Les frontières des cellules sont constituées des points situés à égale distance de deux sites
  • Un sommet de Voronoï, où les arêtes des cellules se rencontrent, est un point situé à égale distance de trois sites

sweep line, beachline, event

  • L’algorithme de Fortune utilise une ligne verticale se déplaçant de gauche à droite, appelée sweep line
  • Lorsque la sweep line rencontre un site, un arc de parabole ayant ce site pour foyer est créé ; plus la sweep line s’en éloigne, plus l’arc grandit
  • Le point de rencontre entre deux arcs de sites différents est à égale distance des deux sites, et devient donc une frontière de cellule
  • Lorsque deux frontières se rencontrent, un sommet du diagramme est créé
  • Le front des arcs actifs est appelé beachline
  • En pratique, l’implémentation ne déplace pas la sweep line pixel par pixel : elle ne traite que certains points calculables, les events
    • site event : défini par les coordonnées connues d’un site ; lors de son traitement, un nouvel arc est ajouté à la beachline
    • circle event : défini par trois arcs de la beachline ; lors de son traitement, un arc est supprimé et un sommet de Voronoï ainsi qu’une half edge sont créés

Trouver les frontières avec des paraboles

  • Dans l’algorithme, les paraboles ne sont pas manipulées sous la forme habituelle y = ax^2 + bx + c, mais via leur définition comme lieu géométrique
  • Une parabole est définie par un focus point et une directrix
    • le focus point est le site
    • la directrix est la sweep line
  • Le point d’intersection de deux paraboles utilisant la même sweep line comme directrix est à égale distance des deux sites
  • Trouver l’intersection de deux paraboles permet donc de trouver l’equiedge entre deux sites
  • L’article utilise un pseudo-code pour calculer la coordonnée x de la parabole, ainsi qu’un exemple montrant comment l’intersection de deux paraboles se déplace le long de la frontière lorsque la position de la sweep line change

Représentation de la beachline et traitement des site events

  • Chaque arc de la beachline peut être représenté uniquement par les coordonnées de son site
    • la sweep line s’applique en commun à tous les arcs
    • dans l’implémentation, un arc est manipulé comme une coordonnée 2D, et non comme un objet séparé
  • La beachline peut être représentée comme une simple suite de points
    • exemple : [arc1, arc2], [arc1, arc2, arc3]
    • l’arc d’un même site peut apparaître plusieurs fois dans la beachline
    • exemple : [arc1, arc3, arc1, arc2]
  • Lorsqu’un site event se produit, on cherche l’arc de la beachline rencontré en traçant une ligne vers la gauche depuis le nouveau site, puis le nouvel arc scinde cet arc
  • Si le nouveau site L scinde j dans la beachline existante [.., i, j, k, ..], la structure devient [.., i, j, L, j, k, ..]
  • Les sites sont placés dans une file par ordre de coordonnée x ; à chaque traitement, la beachline et les candidats événements sont mis à jour

circle event et circumcircle

  • Dans trois arcs de la beachline [.., i, j, k, ..], lorsque deux frontières se rencontrent, l’arc central j disparaît
  • Il existe alors un circumcircle passant par les trois sites, dont le centre est à égale distance des trois sites
  • Le centre du circumcircle devient un sommet de Voronoï
  • Le circle event est placé dans la file d’événements selon le circle point, c’est-à-dire le point le plus à droite du cercle
  • Si un nouveau site est découvert à l’intérieur du cercle avant que la sweep line n’atteigne le circle point, le circle event existant devient invalide
    • le nouveau site scinde d’abord l’arc central, si bien que la combinaison des trois arcs n’est plus conservée
    • l’ancien triplet i, j, k disparaît, et il faut examiner de nouveaux triplets comme i, j, L et L, j, k

incomplete edge et half edge

  • Une incomplete edge est une ligne dont une extrémité est fixe, tandis que l’autre est définie par l’intersection de deux arcs paraboliques
  • Lorsqu’un nouvel arc est inséré par un site event, deux incomplete edges sont créées
    • le point fixe est la coordonnée à laquelle le nouvel arc rencontre la beachline existante
    • si le nouvel arc j scinde l’arc existant i, des arêtes correspondant aux intersections [i, j] et [j, i] sont créées
  • Lors d’un circle event, lorsque deux incomplete edges entrent en collision, le point de collision devient un sommet de Voronoï
  • Les incomplete edges existantes sont finalisées en half edges à cet endroit, et une nouvelle incomplete edge est créée entre les deux arcs qui deviennent adjacents

Seuls les cercles en sens antihoraire deviennent des circle events

  • Lorsque la beachline contient [i, j, k, j, i], ijk et kji peuvent tous deux former un cercle, mais ils ne sont pas tous deux des circle events valides
  • Le cas où l’arc central disparaît est uniquement celui où les frontières convergent réellement
  • Le programme détermine l’orientation des trois points à l’aide d’un déterminant
    • si le déterminant est négatif, l’orientation est antihoraire et il s’agit d’un circle event
    • si le déterminant est positif, l’orientation est horaire et il ne s’agit pas d’un circle event
    • si le déterminant est nul, les trois points sont alignés et il n’y a pas de cercle

Déroulement complet de l’algorithme

  • Les sites d’entrée sont triés par coordonnée x et placés dans la file comme site events
  • Tant que la file n’est pas vide, l’événement suivant est extrait et traité
  • Traitement d’un site event :
    • supprimer, parmi les circle events restants, ceux pour lesquels le nouveau site entre à l’intérieur du cercle
    • trouver l’arc de la beachline que le nouveau site va scinder
    • insérer le nouvel arc et scinder l’arc existant
    • ajouter deux incomplete edges
    • vérifier si les nouveaux triplets peuvent former des circle events
  • Traitement d’un circle event :
    • ajouter le centre du circumcircle comme sommet de Voronoï
    • supprimer l’arc central de la beachline
    • supprimer les futurs circle events rendus invalides par l’arc supprimé
    • examiner les triplets des arcs devenus adjacents et ajouter des circle events
  • Lorsque la file est vide, les incomplete edges restantes sont prolongées jusqu’à la frontière du diagramme, et des sommets de Voronoï sont créés aux points de rencontre avec cette frontière

Structures de données de l’implémentation en Odin

  • L’implémentation d’exemple est écrite en Odin, un langage alternatif au C
  • Le code complet se trouve dans le dépôt RedPenguin101/voronoi
  • Types de base :
    • V2 : point 2D de la forme [2]int
    • PointPair : paire de deux V2
    • Event : structure {site: bool, a, b, c: V2}
  • La signification de Event varie selon son type
    • dans un site event, a correspond aux coordonnées du site, tandis que b et c ne sont pas utilisés
    • dans un circle event, a, b et c sont les trois arcs de la beachline qui ont créé l’événement
  • La structure Fortune gère les états suivants
    • beachline : tableau de V2
    • queue : tableau d’Event
    • incomplete_edges : map PointPair -> V2
    • vd : DCEL stockant le diagramme de Voronoï

Parties omises ou simplifiées dans l’implémentation

  • La beachline est représentée par un vecteur, mais un binary tree serait plus adapté pour améliorer l’efficacité
  • L’event queue est elle aussi conceptuellement une priority queue, mais l’implémentation d’exemple la gère avec des insertions triées dans un tableau
  • L’invalidation des circle events consiste à parcourir les événements futurs pour les vérifier ; un TODO indique qu’une méthode plus rapide est nécessaire
  • clean_beachline_edges est une procédure qui coupe les arcs inutiles aux deux extrémités de la beachline
  • L’implémentation inclut le traitement de cas particuliers comme des sites ayant la même coordonnée x, un circle point identique à un site, ou des collisions de points de référence
  • Après que la file est vide, l’étape finale de nettoyage des incomplete edges restantes, des half edges sans twin et des vertices est traitée uniquement par des calculs mathématiques simples

Stocker un diagramme de Voronoï avec une DCEL

  • Un diagramme de Voronoï est généralement stocké dans une Doubly Connected Edge List (DCEL)
  • Une DCEL est une structure de données qui facilite la manipulation d’un cell-complex composé de vertices et d’edges
  • Elle est centrée sur les edges, mais stocke aussi les informations de vertices et de faces
  • Une edge classique n’a pas de direction, mais dans une DCEL chaque edge est stockée sous forme de deux half edges orientées en sens opposés
  • Dans un diagramme de Voronoï, les vertices stockés dans la DCEL ne sont pas les sites, mais les sommets de Voronoï
  • La destination de l’edge E s’obtient avec E.twin.origin, et la face de droite avec E.twin.left

À lire aussi

1 commentaires

 
GN⁺ 2025-02-10
Commentaires sur Hacker News

  • J’avais déjà réalisé en ClojureScript une implémentation qui montre en animation le déroulement de l’algorithme de Fortune : https://voronoi.ajwerner.net/#/app-diagrams
    C’est vraiment un algorithme magnifique.
    Cela dit, depuis ce projet, j’ai fini par ne plus trop aimer l’algorithme de Fortune, car sa stabilité numérique en virgule flottante n’est pas très bonne.
    Si les points sont alignés ou presque alignés selon les flottants, ça peut casser.
    Si je me souviens bien, sur ce point delaunator est meilleur : https://github.com/mapbox/delaunator

    • C’est la meilleure animation que j’aie vue jusqu’à présent.
      Je vois un lien vers une implémentation « old » sur la page de référence ; je me demande si la version animée actuelle pourrait aussi être publiée en open source.

  • J’avais fait il y a quelques années une visualisation 3D de ce genre : https://x.com/KangarooPhysics/status/1253336959755251716

  • Il existe une implémentation JavaScript de Raymond Hill, connu pour uBlock Origin : https://github.com/gorhill/Javascript-Voronoi
    Je l’ai un peu bricolée ici pour la mettre en mouvement : https://animations.adgent.com/voronoi.html

    • Cette animation me rappelle le style de A Scanner Darkly (2006).
      Je me demande s’il serait possible de la faire entrer dans un algorithme qui prend une vidéo en entrée et l’affiche à la manière d’un Voronoi.
      À ce stade, ce ne serait peut-être plus strictement un diagramme de Voronoi, mais ça aurait l’air assez sympa.

  • D3.js a une nouvelle implémentation : https://github.com/d3/d3-delaunay
    En bas de cette page, il y a une explication de l’algorithme de balayage utilisé ainsi qu’une liste d’implémentations dans d’autres langages que JavaScript.
    L’ancien d3-voronoi est en voie d’abandon, mais on peut encore le voir ici : https://github.com/d3/d3-voronoi

  • Si les arêtes ne vous intéressent pas et que vous voulez seulement colorier chaque région avec une couleur différente, vous pouvez utiliser une variante de flood fill à partir des points germes.
    Il suffit d’empiler un pixel seulement si la distance de cette couleur est plus courte que celle de la couleur déjà appliquée à ce pixel.

    • On peut construire une scène 3D avec des cônes droits de couleurs différentes, dont les sommets sont placés sur chaque point du plan 2D, avec leur axe perpendiculaire au plan.
      Si on fait le rendu en projection orthographique 2D depuis au-dessus des sommets, le z-buffer conserve les pixels du sommet le plus proche.
      Il y a sans doute une façon de le faire avec des shaders, mais la démo classique en cônes 3D est extrêmement simple à comprendre et à implémenter.

  • Je trouve intéressant que D3 soit passé de l’algorithme de Fortune à https://mapbox.github.io/delaunator/
    La raison invoquée est que « pour construire des triangulations de Delaunay ou des diagrammes de Voronoi, c’est 5 à 10 fois plus rapide que d3-voronoi, plus robuste numériquement, avec un rendu Canvas intégré, la possibilité de parcourir le graphe de Delaunay et diverses autres améliorations ».

    • Si D3 considère que delaunator est la meilleure option pour ce type d’effet, alors il ne me reste plus comme excuse pour ne pas l’ajouter à ma bibliothèque canvas que ma tendance naturelle à procrastiner.
      Le code actuel qui calcule les tuiles est douloureusement naïf.
      Nouvelle discussion : https://github.com/KaliedaRik/Scrawl-canvas/discussions/120

  • Cet article m’a donné envie de chercher où se trouve Steve ces jours-ci.
    On se connaissait il y a plusieurs décennies.

  • Un article connexe intéressant à voir : https://news.ycombinator.com/item?id=37998923 - Construire des diagrammes de Voronoi et des triangulations de Delaunay en O(n log n) avec l’algorithme de Fortune (2020)
    L’article précédent et la discussion contiennent aussi un court résumé d’autres algorithmes.
    Personnellement, Jump Flooding Algorithm reste mon préféré : https://en.wikipedia.org/wiki/Jump_flooding_algorithm