🗺️ Construis ton propre diagramme de Voronoï
Chaque point (germe) règne sur la zone des pixels qui lui sont plus proches qu'à tout autre germe. Clique sur la carte pour ajouter un germe.
Clique n'importe où pour ajouter un germe. Regarde les territoires se redessiner instantanément.
🗺️ Une carte découpée en territoires
Imagine plusieurs hôpitaux dispersés dans une région. Une question naturelle se pose : si tu es victime d'un accident, vers quel hôpital aller ? Le plus proche, évidemment. Mais alors, à chaque endroit de la carte correspond un hôpital « de référence » — le plus proche de cet endroit. En coloriant chaque point de la carte selon son hôpital le plus proche, la région se découpe naturellement en zones. C'est exactement un diagramme de Voronoï.
Les hôpitaux s'appellent les germes (ou sites). Chaque zone est une cellule. Et la magie, c'est que cette construction d'apparence enfantine engendre des motifs d'une beauté saisissante, et résout des problèmes très concrets.
📜 Descartes, Voronoï et le choléra
L'idée est ancienne. Dès 1644, René Descartes dessine, dans ses Principia Philosophiae, des découpages du ciel en régions d'influence autour des étoiles — une intuition très voisine. Mais c'est le mathématicien ukrainien Georgy Voronoï (1868-1908) qui, en 1908, en donne la définition rigoureuse et générale en dimension quelconque. Le diagramme porte aujourd'hui son nom.
Pourtant, l'une des plus belles utilisations historiques est antérieure. En 1854, à Londres, le médecin John Snow traque une épidémie de choléra. Il reporte sur une carte chaque décès, et la position des pompes à eau du quartier. En traçant — sans le savoir — les cellules de Voronoï autour des pompes (la zone des maisons plus proches de chaque pompe), il constate que les morts se concentrent massivement dans la cellule d'une seule pompe, celle de Broad Street. On la ferme : l'épidémie recule. C'est l'acte de naissance de l'épidémiologie moderne.
📐 La définition mathématique
Donnons-nous un ensemble fini de germes p1, p2, …, pn dans le plan. La cellule de Voronoï du germe pi est l'ensemble de tous les points du plan qui sont plus proches de pi que de n'importe quel autre germe :
Cellule de Voronoï
Cell(pi) = ensemble des points x tels que, pour tout autre germe pj :
dist(x, pi) ≤ dist(x, pj)
où dist désigne la distance euclidienne usuelle. Si x = (x1, x2) et p = (a, b), alors :
dist(x, p) = √( (x1 − a)2 + (x2 − b)2 )
Une remarque utile pour les calculs : comparer deux distances revient à comparer leurs carrés. Comme la racine carrée est croissante, dist(x, pi) ≤ dist(x, pj) équivaut à dist(x, pi)2 ≤ dist(x, pj)2. On peut donc se passer du √, ce qui accélère énormément le calcul — c'est exactement ce que fait la simulation ci-dessus pour colorier la carte en temps réel.
✂️ Pourquoi des frontières droites ?
Prends seulement deux germes A et B. Les points plus proches de A que de B sont d'un côté ; les points plus proches de B sont de l'autre. La frontière, c'est l'ensemble des points équidistants de A et B — autrement dit la médiatrice du segment [AB] ! C'est une droite.
Avec n germes, chaque cellule est l'intersection des demi-plans définis par les médiatrices avec tous les autres germes. Une intersection de demi-plans est toujours un polygone convexe. Voilà pourquoi un diagramme de Voronoï ressemble toujours à une mosaïque de polygones aux arêtes rectilignes. Chaque arête est un bout de médiatrice ; chaque sommet est équidistant de trois germes (et donc le centre du cercle passant par ces trois germes).
🔺 Le jumeau caché : la triangulation de Delaunay
À tout diagramme de Voronoï correspond un objet dual : la triangulation de Delaunay. La règle est simple : on relie deux germes par un segment si et seulement si leurs cellules de Voronoï sont voisines (elles partagent une arête). On obtient alors un maillage de triangles.
Ce dual a une propriété remarquable : parmi toutes les façons de trianguler un nuage de points, la triangulation de Delaunay maximise les plus petits angles — elle évite au maximum les triangles « écrasés ». C'est pour cela qu'elle est reine en infographie et en simulation : pour mailler un terrain, modéliser un objet 3D ou résoudre une équation par éléments finis, on veut des triangles bien proportionnés. Voronoï et Delaunay sont deux faces d'une même pièce : l'un découpe l'espace, l'autre le relie.
🌍 Des applications partout
- Épidémiologie : la méthode de John Snow s'utilise toujours pour relier des cas de maladie à leur source la plus probable (puits, antenne, usine).
- Réseaux et télécoms : ton téléphone se connecte à l'antenne la plus proche. La carte de couverture d'un opérateur est un diagramme de Voronoï dont les germes sont les antennes.
- Biologie cellulaire : pour analyser un tissu au microscope, on modélise chaque cellule par son noyau (le germe) et on reconstruit ses contours par Voronoï.
- Robotique et planification de trajet : un robot suit les arêtes du diagramme, car ce sont les chemins qui restent le plus loin possible des obstacles.
- Urbanisme et logistique : où placer une nouvelle école, une caserne, un entrepôt pour minimiser la distance des habitants ? On raisonne sur les cellules de Voronoï.
- Météorologie : pour estimer la pluie tombée sur une zone à partir de quelques stations, la méthode des polygones de Thiessen (un autre nom de Voronoï) attribue à chaque station sa cellule.
- Jeux vidéo et images de synthèse : Voronoï génère procéduralement des textures de pierre, de peau de reptile, de pavés, ou des cartes de territoires et de biomes.
🎓 Le lien avec ton programme
Tu manipules déjà tous les ingrédients de Voronoï au lycée :
- Distance dans le plan (géométrie analytique, 1BAC) : la formule √((x2 − x1)2 + (y2 − y1)2) est le cœur de tout.
- Médiatrice d'un segment : c'est, par définition, le lieu des points équidistants de deux points — donc une frontière de Voronoï.
- Inéquations et demi-plans : chaque cellule est une intersection de demi-plans, le même outil qu'en programmation linéaire.
- Cercle circonscrit : chaque sommet du diagramme est le centre du cercle circonscrit à un triangle de Delaunay.