Diagrammes de Voronoï

Diagrammes de Voronoï : partitionner le monde selon la proximité

Imaginez une ville dotée de plusieurs casernes de pompiers. Chaque habitant se pose alors la question suivante : « En cas d'incendie, vers quelle caserne dois-je me tourner ? » La réponse la plus simple est : « Vers celle qui est la plus proche de chez vous. »

Par conséquent, nous pouvons diviser toute la ville en zones distinctes : les habitants d'une zone donnée sont plus proches de la caserne A ; ceux d'une autre zone sont plus proches de la caserne B ; et ceux d'une troisième zone sont plus proches de la caserne C. En fin de compte, chaque emplacement est rattaché à la caserne de pompiers la plus proche.

Si l'on cartographie ces zones, on obtient une structure géométrique remarquable appelée diagramme de Voronoï.

Tout commence par quelques points

Le principe de base d'un diagramme de Voronoï est très simple : il s'agit d'un ensemble de points répartis sur un plan. Ces points peuvent représenter n'importe quoi : des casernes de pompiers, des hôpitaux, des commerces, des écoles, des villes ou même des arbres. On appelle ces points des points générateurs ou des sites.

Imaginons trois points : A, B et C. Pour chaque emplacement sur le plan, on détermine quel est le point le plus proche. Par exemple, tous les emplacements situés dans une certaine zone autour du point A sont plus proches de A que de n'importe quel autre point. De même, les points B et C définissent chacun leur propre zone. Le plan est ainsi divisé en trois parties : la zone associée à A, celle associée à B et celle associée à C. Chacune de ces zones est appelée cellule de Voronoï ou région de Voronoï. À chaque point générateur correspond une région de Voronoï ; ainsi, 10 points donneront généralement 10 régions, et 100 points en donneront 100.

Alors, où se situent les frontières ?

C'est l'aspect le plus crucial d'un diagramme de Voronoï.

Imaginons que vous n'ayez que deux points, A et B. La question devient alors : quand un emplacement est-il équidistant de ces deux points ? La réponse : lorsqu'il se situe exactement à mi-chemin entre eux. Par conséquent, la ligne droite passant précisément entre les points A et B sert de ligne de démarcation. Chaque point situé sur cette ligne se trouve à une distance identique de A et de B, tandis que l'espace de part et d'autre de cette ligne appartient soit à A, soit à B. En termes mathématiques, l'ensemble de tous les points équidistants de deux points donnés forme une médiatrice. Ainsi, les frontières dans un diagramme de Voronoï ne sont pas tracées arbitrairement ; elles découlent d'une règle mathématique très simple : identifier tous les emplacements qui sont équidistants de deux points sources donnés.

Que se passe-t-il lorsque vous avez trois points ? Si l'on ajoute un troisième point, C, alors A, B et C commencent tous à rivaliser pour délimiter leurs propres régions. Pour tout emplacement donné, la question posée est : « De quel point suis-je le plus proche ? » Finalement, le plan tout entier se retrouve partitionné en trois régions distinctes, les frontières entre elles étant constituées de lignes équidistantes des points sources correspondants.

À mesure que le nombre de points augmente, le motif formé par ces frontières devient de plus en plus complexe. Que vous partiez de 3 points pour en atteindre 10, 50, voire 100, vous observerez que le plan tout entier se transforme rapidement en un réseau complexe de polygones. Pourtant, en y regardant de plus près, vous constaterez que chaque région reste centrée autour d'un unique point source — la règle fondamentale, elle, n'a jamais changé.

Pourquoi cela ressemble-t-il autant à des cellules ?

Si vous générez un grand nombre de points de manière aléatoire, un diagramme de Voronoï produit souvent un motif visuel très familier : des cellules. Il crée un ensemble de polygones irréguliers étroitement imbriqués, où chaque zone possède son propre point central, et dont les frontières s'articulent parfaitement avec les zones adjacentes.

C'est pourquoi les diagrammes de Voronoï évoquent souvent des cellules biologiques, des rayons de ruche, de la terre craquelée, la texture d'une peau animale, de la mousse, ou même des îlots urbains.

Il convient toutefois d'apporter une nuance importante : une ressemblance visuelle ne signifie pas pour autant que tous ces éléments sont générés par des diagrammes de Voronoï. Un diagramme de Voronoï est, avant tout, une règle mathématique permettant de partitionner l'espace. Si certaines structures naturelles peuvent être liées à ce principe géométrique, d'autres résultent de processus physiques totalement différents.

Pourquoi les frontières sont-elles toujours aussi nettes ? C'est là toute la beauté d'un diagramme de Voronoï. Prenons deux points, A et B ; la frontière entre eux est constituée de tous les points situés à égale distance de A et de B — ce qui fait de cette frontière, par définition, la médiatrice du segment AB. Lorsque l'on ajoute davantage de points, ces médiatrices se croisent, formant ainsi un réseau de polygones délimités par des lignes droites. Ainsi, bien qu'un diagramme de Voronoï puisse paraître aléatoire, il est en réalité régi par une structure géométrique très précise.

Bien plus que de simples casernes de pompiers

Revenons à notre exemple initial : les casernes de pompiers. Imaginons qu’une ville dispose de plusieurs casernes — A, B, C, D, etc. Si l’on représente chaque caserne par un point et que l’on génère un diagramme de Voronoï, chaque région obtenue peut être interprétée comme la zone dont une caserne donnée est principalement « responsable ». Si un habitant réside dans la région associée à la caserne A, alors A est la caserne la plus proche de chez lui ; s’il vit dans la région associée à la caserne B, alors B est la plus proche. Ainsi, ce qui ressemble à un élégant diagramme géométrique est, en réalité, la représentation directe d’un problème bien concret.

Les diagrammes de Voronoï ne se limitent pas aux casernes de pompiers ; le même principe s’applique à bien d’autres situations. Quel est l’hôpital le plus proche ? Quel magasin dessert une zone donnée ? Quelle école est la plus proche d’un élève ? Quel centre de distribution est responsable d’un secteur précis ? Quelle antenne-relais est la plus proche d’un téléphone mobile ? Loin d’être un simple motif mathématique esthétique, le diagramme de Voronoï constitue un outil de partitionnement spatial extrêmement pratique.

Au cœur du diagramme de Voronoï se trouve un concept unique : la proximité (ou la notion de « plus proche »). Pour un ensemble de points donné, si l’on considère n’importe quel emplacement dans un plan, on peut se demander : « Quel est le point le plus proche de cet endroit ? » La réponse à cette question détermine la région à laquelle appartient cet emplacement. En cartographiant ces réponses pour chaque point possible, on obtient un diagramme de Voronoï.

On peut même concevoir le diagramme de Voronoï comme une sorte de mécanisme mathématique. Il prend en entrée un ensemble de points et, pour chaque emplacement à l’écran, pose la question : « De quel point cet emplacement est-il le plus proche ? » Si la réponse est A, alors cet emplacement est attribué à A ; si c’est B, il est attribué à B ; si c’est C, il est attribué à C, et ainsi de suite. Au final, l’espace tout entier se retrouve automatiquement partitionné.

L'ordre peut émerger de points aléatoires

Si nous dispersons un certain nombre de points de manière aléatoire — sans suivre de schéma particulier —, une structure géométrique hautement organisée émerge dès lors que l'on applique une règle simple : chaque emplacement est attribué au point le plus proche. En d'autres termes, des données d'entrée aléatoires peuvent donner lieu à un découpage ordonné de l'espace.

Il ne s'agit pas d'une fractale. Un diagramme de Voronoï n'est pas une fractale ; il ne présente ni récursion infinie, ni autosimilarité infinie, ni ces structures répétitives qui apparaissent à mesure que l'on zoome. Il s'agit, par essence, d'une méthode de partitionnement spatial.

Chaque point agit comme un « centre »

On peut concevoir un diagramme de Voronoï comme un ensemble de points en compétition pour l'espace. Chaque point revendique : « Cette zone est plus proche de moi », tandis qu'un autre rétorque : « Non, elle est plus proche de moi ! ». Finalement, des frontières se forment entre eux, et le plan tout entier se retrouve divisé en une multitude de régions, fondées sur cette compétition pour la « plus grande proximité ».

Ce qui est encore plus fascinant, c'est que modifier les règles transforme le monde lui-même. Un diagramme de Voronoï classique repose sur la distance euclidienne — la distance en ligne droite, telle que nous la connaissons. Par exemple, si un point se trouve à 3 mètres de vous et un autre à 5 mètres, le premier est manifestement le plus proche.

Cependant, le monde réel est rarement aussi simple. Prenons l'exemple d'une ville : l'hôpital le plus proche « à vol d'oiseau » (en ligne droite) n'est peut-être pas celui que vous pouvez atteindre le plus rapidement en voiture, car des facteurs tels que le réseau routier, les cours d'eau, le relief ou la circulation entrent en ligne de compte. Dans ce contexte, la « distance » ne se limite pas à la distance euclidienne. Si vous redéfinissez la notion de « distance », le diagramme de Voronoï qui en résulte change en conséquence. C'est là toute la beauté des mathématiques : il suffit de modifier une seule règle pour remodeler un monde entier.

Une question simple qui génère une carte complète

Lorsque vous observez un magnifique diagramme de Voronoï, ne le voyez pas simplement comme un assemblage de polygones colorés générés de manière aléatoire. Ce que vous avez sous les yeux, c’est en réalité la réponse à la question « Quel est le point le plus proche ? » pour chaque emplacement dans tout l’espace. Chaque région répond à la question : « À quel point cette zone est-elle rattachée ? » Chaque frontière délimite la zone où un point donné devient le plus proche. Et chaque sommet représente une relation géométrique unique entre plusieurs régions.

L’essence d’un diagramme de Voronoï peut se résumer en une seule phrase : Donnez-moi un ensemble de points, et je peux diviser l’espace entier en fonction du point le plus proche de chaque emplacement. Pas de récursivité complexe, pas de formule mystérieuse, pas de conception artificielle : uniquement des points, des distances et des notions de proximité. Pourtant, lorsque ces règles simples sont appliquées à l’ensemble d’un plan, il en émerge un univers géométrique à la fois complexe et magnifique.

Explorer le monde des mathématiques à travers la notion de « proximité »

Les diagrammes de Voronoï illustrent comment la distance façonne l'espace.

Vous pouvez également explorer le triangle de Sierpinski, où un triangle simple est transformé par le retrait répété de parties, créant ainsi un motif récursif à l'infini.

Ou encore, découvrez le flocon de neige de Koch, qui montre comment une simple ligne droite peut évoluer en une forme infiniment complexe par la modification continue de ses bords.

Vous pourriez aussi vous pencher sur la courbe de Hilbert — une courbe qui, grâce à une récursion infinie, finit par remplir progressivement tout un espace bidimensionnel.

Ou peut-être la courbe du dragon, qui démontre comment une ligne simple peut être pliée à maintes reprises pour former une structure mystérieuse, évoquant un dragon.

Les diagrammes de Voronoï, en revanche, fonctionnent tout autrement. Ils ne reposent pas sur une récursion infinie ; ils posent simplement la question suivante : « Qu'est-ce qui est le plus proche de ce point ? » Cette question unique et directe suffit à transformer tout un espace en une carte mathématique fascinante.

N'hésitez pas à découvrir d'autres motifs mathématiques captivants, ou consultez la page Wikipédia consacrée aux diagrammes de Voronoï pour en savoir plus.