Génération de diagrammes de Voronoï avec l’algorithme de Fortune

Générer un diagramme de Voronoï

• Qu’est-ce qu’un diagramme de Voronoï ?

  • Un diagramme de Voronoï est une méthode de partition du plan en plusieurs régions, principalement utilisée pour générer procéduralement des cartes.
  • On choisit plusieurs points dans le plan, appelés « sites », et la région correspondant à chaque site contient tous les points les plus proches de ce site.
  • Les frontières de chaque région sont constituées des points équidistants de deux sites. Un point équidistant de trois sites est appelé un « sommet de Voronoï ».

• Algorithme de Fortune

  • L’algorithme de Fortune est une méthode de construction du diagramme à l’aide d’une ligne qui « balaie » le plan de gauche à droite.
  • Lorsque la ligne de balayage rencontre un site, une « bulle » (un arc de parabole) se forme autour de lui, et cette bulle grandit à mesure que la ligne s’éloigne.
  • Quand les arcs de deux sites entrent en collision, leur point de collision devient la frontière entre les cellules.
  • La frontière de toutes les bulles actives est appelée la « beach line ».

• Glossaire

  • Site : point en 2D qui détermine la forme du diagramme de Voronoï.
  • Ligne de balayage : droite verticale qui traverse la zone et traite chaque événement de la file d’événements.
  • Beach line : ligne composée de plusieurs arcs, auxquels on ajoute ou retire des arcs au fil du traitement des événements.
  • Point d’intersection : point où deux arcs de la beach line se rencontrent, équidistant des sites concernés.
  • File d’événements : structure où sont stockés les événements de site et de cercle, triés par ordre croissant de coordonnée x.
  • Événement de site : l’un des deux types d’événements de la file, défini par les coordonnées du site correspondant.
  • Événement de cercle : l’autre type d’événement de la file, défini par trois arcs situés sur la circonférence d’un cercle.
  • Sommet de Voronoï : point équidistant de trois sites, correspondant à un coin de cellule.
  • Frontière d’équidistance : ligne équidistante de deux sites.
  • Frontière incomplète : ligne dont une extrémité est un point fixe, tandis que l’autre est définie par l’intersection de deux foyers paraboliques.

• Tangentes paraboliques

  • Le concept et les propriétés de la parabole sont très importants dans l’algorithme.
  • Une parabole est définie par un point focal et une droite (directrice).
  • En prenant les foyers de deux sites et la ligne de balayage comme directrice, on peut trouver la frontière équidistante des deux sites en calculant le point d’intersection des deux paraboles.

• Retour à la beach line

  • La beach line correspond à la « frontière » de tous les arcs pour une position donnée de la ligne de balayage.
  • Chaque arc peut être représenté par le point focal du site.
  • La beach line peut être représentée comme une simple séquence de points.

• Un nouvel arc est créé lorsque la ligne de balayage rencontre un nouveau site

  • La beach line est une séquence de points, chaque point représentant un site et un arc.
  • Quand la ligne de balayage rencontre un nouveau site, un nouvel arc est créé et inséré dans la séquence.

• Frontières qui se croisent et cercle circonscrit

  • Lorsque trois sites se trouvent sur la circonférence d’un cercle, le centre du cercle est à égale distance des trois points.
  • Le centre du cercle circonscrit devient un sommet de Voronoï.

• Frontières incomplètes

  • Une frontière incomplète a une extrémité fixe, et l’autre est le point d’intersection de deux arcs.
  • Lorsque deux frontières incomplètes entrent en collision, un sommet de Voronoï est créé, et les frontières incomplètes sont converties en demi-frontières.

• Seuls les cercles en sens antihoraire génèrent un événement de cercle

  • Un événement de cercle n’est généré que lorsque trois arcs se lisent dans le sens antihoraire.

• Résumé

  • Étant donné un ensemble de sites, on place tous les points des sites dans la file sous forme d’événements de type « site », puis on les trie selon la valeur de x.
  • Tant que la file n’est pas vide, on récupère l’événement suivant et on le traite.
  • S’il s’agit d’un événement de site, on ajoute un nouvel arc à la beach line et on crée une frontière incomplète.
  • S’il s’agit d’un événement de cercle, on ajoute un sommet de Voronoï et on retire un arc de la beach line.