Diagramme de Voronoi


L'applet ci-dessous vous permet de simuler un réseau cellulaire.
 

Qu'est ce qu'un diagramme de Voronoï  ?

En cliquant dans la surface grisée, vous ajoutez un 'germe'. Ce germe va définir une zone d'influence sur la carte. En rajoutant plusieurs germes, on obtient une partition du plan, où chaque zone est définie comme l'ensemble des points les plus proches d'un germe. Ce genre de figure est appelé diagramme de Voronoï, du nom du mathématicien français qui l'a étudié au début du XXème siècle. Elle peut être utilisée pour modéliser des réseaux de cellules végétales, en mécanique ou encore dans les télécommunications.
 
Cliquez ici pour lancer l'applet.

Utilisaton de l'applet :

Le fonctionnement du programme est très simple :

Partition de Delaunay

Une autre possibilité est d'afficher les liens entre les régions voisines. En traçant un segment entre un germe et les germes des régions voisines, on obtient une partition de Delaunay. Cette structure est très utile en mécanique, car c'est celle qui permet de mailler les objets de la manière la plus efficace, en minimisant les aires au carré des triangles.
 

Théorie des graphes

Du point de vue de la théorie des graphes, le diagramme de Voronoï est le dual de la partition de Delaunay. C'est à dire que que l'on passe de l'un à l'autre très facilement, et qu'ils représentent la même chose. C'est la raison pour laquelle ces deux problèmes sont très souvent associés. Tous les deux sont des graphes planaires : on peut les dessiner sur un surface plane sans qu'aucuns de leurs arcs ne se croisent.
 

Téléchargement

Vous pouvez récuperer l'applet pour l'utiliser chez vous. Vous pouvez aussi télécharger les sources (en Java) pour étudier l'algorithme.
 

Liens

Si ces quelques lignes sur les graphes de Voronoï vous ont intéressé, je vous conseille les liens suivants :