Diagrammes de Voronoï

L'objectif de ce tutoriel est de réaliser un diagramme de Voronoï sous Grasshopper sans utiliser la commande toute faite "Voronoï 2D/3D". L'image en vignette (ci-dessous) est la robe de la Girafe Réticulée et provient de ce site.

PARTIE 1 - LES DIAGRAMMES DE VORONOI

On les voit partout. En retouche d'image, en médecine (traque des cellules cancéreuses), en structure (le dual du diagramme de Voronoï est la triangularisation de Delaunay qu'on utilise pour les calculs aux éléments finis), dans l'organisation territoriale (la distance à vol d'oiseau à partir d'un ensemble de villes du territoire) et, de plus en plus, en design.

 En effet, leur forme aléatoirement organisée inspire de plus en plus les designers. Pour preuve, voyez ici, ici, là ou encore ici. En architecture, un exemple archi-connu est le Water Cube, la piscine olympique de Pékin.

 Grasshopper propose un composant Voronoï 2D, et même un Voronoï 3D qui permet de tracer immédiatement ces diagrammes à partir d'une collection de points. Je vous propose ici de réfléchir à leur construction géométrique et de les réaliser sans utiliser ces méthodes toute faites.

Certaines images de cet article proviennent de Wikipédia.
L'image de la map monde ci-contre vient de ce site.

 Une solution plus efficace ? Proposez-là en commentaire, la solution optimale sera publiée !

I-1 - Un diagramme de Voronoï c'est quoi ?

Devant son nom au mathématicien russe Georgi Fedoseevich Voronoï (1868 - 1908), il s'agit d'une partition de l'espace déterminée selon les distances à un ensemble discret de points, appelés germes.

Pour faire simple disons que ce sont des cellules qui regroupent l'ensemble des points qui sont plus proches d'un germe que de tout autre germe. La frontière des cellules est donc équidistante à deux points (ligne), voire plus (point intersection de deux lignes ou plus).

Dans l'image ci-contre, chaque cellule de couleur contient en son sein un point noir. Il s'agit de son germe. Tous les points de la cellule sont alors plus proches de ce germe que des autres germes. Les frontières peuvent s'intuiter via des lignes médianes entre des couples de points.

I-2 - Comment réaliser un diagramme de Voronoï en 2D ?

Les algorithmes qui permettent de tracer ces diagrammes de la façon la plus rapide (voire pour cela cette section de l'article Wikipédia) utilisent des raisonnements par récurrence.

Dans Grasshopper, qui n'a pas été pensé à la base comme un logiciel permettant des raisonnement récursif, il serait donc possible de coder ces algorithmes en Basic dans un composant ou d'utiliser le plug-in HoopSnake qui permet d'introduire des boucles dans Grasshopper.

Je ne veux pas ici présenter une solution codée, je le ferai peut-être dans le futur si cela s'avérait intéressant. Nous allons tenter de comprendre comment tracer un diagramme de Voronoï en n'utilisant que des composants de base de Grasshopper.

Un petit mot sur la vitesse d'une telle opération : la frontière entre chaque couple point devra être étudiée, ce qui n'est pas le plus efficace puisque deux points lointains ont une frontière qui serait probablement non déterminante (coupée par des couples de points plus proches). Mais sans raisonnement récursif, il n'y a pas d'autre moyen de faire (en tout cas je le crois, si vous pensez le contraire, commentez l'article !). La rapidité du calcul sera donc en n², proportionnelle au nombre de couples de points dans un ensemble de n points.

Pour le tracé du diagramme de Voronoï en 2D, je ne vais pas vous présenter une solution personnelle mais la solution de Sanghoon Yoon, consultable ici, car je n'ai pas trouvé de meilleure moyen de le faire.

Dans Grasshopper, voici les étapes qui mènent à la réalisation d'un diagramme de Voronoï 2D :

• Création de l'ensemble des germes :
  • On crée un Rectangle qui constituera notre frontière extérieure. X et Y sont réglés par des Number Slider
  • Populate 2D permet de remplir ce rectangle (input Region) par une collection de points aléatoires dont le nombre (input Count) est réglé par un Number Slider : ce sont les germes.

• Mise en place de plans alignés sur les médianes de chaque couple de germes :
  • La première étape est de tracer des lignes entre chaque couple de points.
  • Il faut donc dresser pour chaque point la liste des points différents de lui-même. Pour ce faire, on crée une Series de nombres entiers (1, 2, 3, ... ect) de la longueur (input Count) du nombre de points.
  • Avec l'opérateur Equality, la série en input A et la série en mode graft en input B, on obtient dans l'output ≠ un arbre qui associe à chaque germe une liste de Boolean True avec un unique False correspondant à la position du germe dans la liste. Cela permettra de ne pas tracer des lignes entre deux germes identiques.
  • En effet, un Cull Pattern appliqué sur la liste des germes avec l'output ≠ en input Pattern permet de créer un arbre de de liste de points correspondant, pour chaque germe, à l'ensemble des autres germes de l'espace.
  • Nous pouvons donc tracer les lignes (avec Line) entre les germes (mode Graft) et les autres germes organisés dans le précédent Cull Pattern
  • On aligne des plans (Plane) sur les milieux de ces lignes (obtenus avec Point On Curve évalué à midpoint) et avec les lignes comme X-Axis

• Partition de l'espace :
  • Le but est de partitionner l'espace en cellules de Voronoï, la solution étant pour chaque germe de soustraire de l'espace  la partie extérieure de chacune des médianes qu'il partage avec chaque autre germe. On s'assure ainsi qu'après toutes ces soustractions, il ne restera que les points qui sont plus proches de ce germe que de tous les autres.
  • On va créer un carré qui englobera tout l'espace extérieur à la médiane une fois celui-ci aligné sur elle. Pour cela il doit être assez grand par rapport à la frontière de l'espace. Avec Box Corners sur la frontière, on extrait les points de la frontière et on mesure la Distance en A et C qui forment une diagonale.
  • Après une Multiplication par 2, cette distance sera la largeur (input X et Y) d'un carré (utiliser Rectangle) dont l'origine est le point X = 0, Z = 0 Y valant l'opposé (Negative) de la longueur de la diagonale de la frontière.
  • On oriente avec Orient ces carrés sur les plans médians (input Target B) entre chaque couple de germes créés précédemment. Le plan de base est donc le Plan XY.
  • Enfin on duplique la frontière avec Duplicate Data autant de fois qu'il y a de points et on soustrait avec Region Difference les carrés à ces frontières (input en mode graft)

Ci-dessous le logigramme du diagramme de Voronoï 2D et la vue du résultat final (cliquez pour voir en grand) :

I-3 - Comment réaliser un diagramme de Voronoï en 3D ?

Pour réaliser un diagramme de Voronoï en 3D, j'ai adapté la même méthode qu'en 2D. Je ne la ré-explique pas étant donné qu'il ne s'agit que d'une simple transposition à la dimension supérieure. Je donne donc directement la définition.

Ci-dessous le logigramme du diagramme de Voronoï 3D et la vue du résultat final (cliquez pour voir en grand) :