Domaines de Voronoï de réseaux de points et pavages

jeudi 11 septembre 2014
par  Alain BUSSER

Les domaines de Voronoï sont associés à des nuages de points (chaque cellule est définie comme l’ensemble des points du plan qui sont plus proches d’un point donné que de tous les autres points du nuage). Donc, toute symétrie du nuage de points devrait se retrouver dans son diagramme de Voronoï. alcoffeethmique permet d’expérimenter avec les domaines de Voronoï associés à des nuages de points définis algorithmiquement.

Voici l’outil qui a servi à tracer ces domaines de Voronoï :

Zip - 363.1 ko
alcoffeethmique
pour programmer en CoffeeScript

Dans les scripts ci-dessous, l’objet nuage est une liste de points, eux-mêmes représentés comme tableaux de deux nombres. L’instruction dessineVoronoi accepte trois arguments en entrée :

  1. le nom du nuage de points ;
  2. la couleur de tracé des cellules (une chaîne de caractères)
  3. le rayon des points du nuage, en effet ceux-ci sont automatiquement dessinés aussi, en marron.

Les dessins se font dans une fenêtre de dimensions 640 pixels et 480 pixels, et le point de coordonnées (320,240) est pris comme origine du repère parce qu’il est placé au centre de la fenêtre.

Réseaux de points

Un réseau (géométrie) du plan est un nuage de points (théoriquement infini) de la forme mu+nv, où u et v ne sont pas colinéaires et m et n prennent toutes les valeurs entières possibles. En dimension 3, les réseaux sont utilisés en cristallographie, mais en dimension 2, ils engendrent des pavages, les pavés étant ici les domaines de Voronoï des points du réseau. La classification des réseau de Bravais donne les trois domaines de Voronoï possibles pavant le plan :

1) Famille cristalline monoclinique

Un cas typique est celui où u=(40,0) et v=(-10,30). Les entiers m et n bouclent d’un nombre négatif à son opposé pour couvrir toute la fenêtre.

Voici le script :

nuage = []
for m in [-20..20]
    for n in [-10..10]
        nuage.push [320+m*40-n*10,240+n*30]
dessineVoronoi nuage, 'magenta', 0.5

En général, le domaine de Voronoï d’un réseau plan est donc formé d’hexagones :

voronoi1 {PNG}

On ne peut s’empêcher de trouver une certaine ressemblance avec une pelure d’oignon vue au microscope :

Ceci n’a rien de surprenant si on pense que pour grandir, les cellules d’oignon cherchent à occuper tout l’espace qui leur est disponible. Des cellules de Voronoï devraient donc apparaître si les cellules d’oignon poussent en même temps.

L’azurite cristallise dans ce système.

2) Famille cristalline orthorhombique

Dans le cas particulier où l’angle est droit, les cellules sont des rectangles. Voici le script :

nuage = []
for m in [-20..20]
    for n in [-10..10]
        nuage.push [320+m*40,240+n*30]
dessineVoronoi nuage, 'blue', 0.5

Les hexagones sont devenus des rectangles :

Le soufre cristallise dans ce système.

3) Famille cristalline tétragonale

Ce cas particulier du précédent est celui des entiers de Gauss : Les cellules sont carrées. Le script est le suivant :

nuage = []
for m in [-20..20]
    for n in [-10..10]
        nuage.push [320+m*40,240+n*40]
dessineVoronoi nuage, 'blue', 0.5

Tiens, on dirait le pavage de ma cuisine :

La pyrite cristallise dans ce système.

4) Famille cristalline hexagonale

Un cas particulier important du premier cas (général) est celui où les vecteurs u et v font un angle de 60° et ont la même norme. Dans ce cas les cellules sont des hexagones.

Voici la recette du nid d’abeilles en CoffeeScript :

nuage = []
for m in [-20..20]
    for n in [-10..10]
        nuage.push [320+m*40+n*20,240+n*20*racine(3)]
dessineVoronoi nuage, 'brown', 0.5

Le résultat :

voronoi2 {PNG}

La couleur de miel a été choisie pour montrer la ressemblance avec les insectes les plus voronoïdiens qui soient :

Le béryl cristallise dans le système hexagonal.

Hasard

On peut ajouter des variables aléatoires à l’abscisse et à l’ordonnée pour donner un aspect plus naturel au diagramme de Voronoï. Par exemple, avec la structure en nid d’abeilles perturbée :

nuage = []
for m in [-20..20]
    for n in [-10..10]
        nuage.push [320+m*40+n*20-10*alea()+10*alea(),240+n*20*racine(3)-10*alea()+10*alea()]
dessineVoronoi nuage, 'brown', 0.5

La couleur marron évoque plus des plaques de boue séchées :

PNG

Ceci n’a rien d’étonnant, puisque la forme que prennent les croûtes de boue ou de peinture en séchant est la conséquence de cellules de Benard :

Avec le réseau carré perturbé, on obtient des écailles de serpent :

nuage = []
for m in [-20..20]
    for n in [-10..10]
        nuage.push [320+m*40-10*alea()+10*alea(),240+n*40-10*alea()+10*alea()]
dessineVoronoi nuage, 'blue', 0.5

PNG

Une vraie peau de serpent pour comparer :

Finalement, autant rendre les coordonnées des points complètement aléatoires, pour commencer uniformes dans la fenêtre :

nuage = []
for n in [1..200]
    nuage.push [640*alea(),480*alea()]
dessineVoronoi nuage, 'red', 1

PNG

Pour continuer, gaussiens centrés sur (320,240) :

nuage = []
for n in [1..50]
    T = alea()*2*pi
    R = -80*ln(alea())
    nuage.push [320+R*cos(T),240+R*sin(T)]
dessineVoronoi nuage, 'orange', 1

Enfin, on dispose des points aléatoirement dans un anneau de rayon intérieur 160 et de rayon extérieur 200 :

nuage = []
for n in [1..80]
    T = alea()*2*pi
    R = 160+40*alea()
    nuage.push [320+R*cos(T),240+R*sin(T)]
dessineVoronoi nuage, 'cyan', 1

Le résultat :

PNG

La ressemblance avec une coupe de minéral vue au microscope, est intéressante :

Spirales

Un bon moyen pour avoir des diagrammes de Voronoï équilibrés, c’est de s’arranger pour que près de chaque point, se trouvent d’autres points. Ce qui se passe lorsque les points sont sur une spirale.

Un premier exemple est ce script :

nuage = []
R = 20
for n in [1..50]
    T = n*1.2
    R *=1.05
    nuage.push [320+R*cos(T),240+R*sin(T)]
dessineVoronoi nuage, 'darkGreen', 0.5

Le résultat :

Un autre exemple (spirale logarithmique) :

nuage = []
R = 20
for n in [1..200]
    T = n*0.4
    R *=1.025
    nuage.push [320+R*cos(T),240+R*sin(T)]
dessineVoronoi nuage, 'darkGreen', 0.5

Le résultat :

PNG

Il ressemble à la texture du fruit à pain :

Et bien entendu, le tournesol, bien connu des lecteurs de ce site :

nuage = []
for n in [1..500]
    T = 137.5*n
    R = racine(n)*10
    nuage.push [320+R*cosinus(T),240+R*sinus(T)]
dessineVoronoi nuage, 'darkGreen', 0.5

PNG

Et le vrai, pour comparer :

Systèmes dynamiques

Les ensembles de Julia donnent parfois aussi des diagrammes de Voronoï intéressants :

Avec 0,285+0,013i

c=new Complexe 0.285,0.013
z = new Complexe 0
nuage = []
for n in [1..100]
    z = (z.fois z).plus c
    nuage.push [320+100*z.Re,240+100*z.Im]
dessineVoronoi nuage

On itère la fonction z²+c avec c=0,285+0,013i, et à chaque fois, on ajoute au nuage le point d’affixe z, correctement redimensionné.

Le résultat :

PNG

Le petit bonhomme de pain d’épices

Le script :

nuage = []
P=[0.1,-0.2]
for n in [1..200]
    P = [1-P[1]+abs(P[0]),P[0]]
    nuage.push [200+100*P[0],100+100*P[1]]
dessineVoronoi nuage, 'darkOrange', 0.5

Le dessin obtenu :

PNG

L’attracteur de Hénon

Le script produisant ce célèbre attracteur :

nuage = []
P=[0.1,-0.2]
for n in [1..200]
    P = [1-1.4*carré(P[0])+P[1],0.3*P[0]]
    nuage.push [320+200*P[0],240+300*P[1]]
dessineVoronoi nuage, 'darkMagenta', 0.5

Et son diagramme de Voronoï :

PNG

Rorschach

Suite aux travaux de Michel Mendès France en théorie des nombres, Pierre-Marc Mazat a dessiné dans mathemaTICE des suites de points groupés en spirale. Voici la suite de ses travaux, avec les diagrammes de Voronoï de ces nuages de points, sans les segments qui les joignaient pour montrer l’ordre de leur construction.

Avec la suite ln(n)4

Le cadrage adéquat est celui-ci :

f = (n) -> puissance(ln(n),4)
nuage = []
P = [50,50]
for n in [1..400]
    t=2*pi*f(n)
    P = [P[0]+20*cos(t),P[1]+20*sin(t)]
    nuage.push P
dessineVoronoi nuage, "blue", 0.5

Le diagramme de Voronoï obtenu :

PNG

Avec la suite n1,5

Le script :

f = (n) -> puissance(n,1.5)
nuage = []
P = [100,100]
for n in [1..200]
    t=2*pi*f(n)
    P = [P[0]+20*cos(t),P[1]+20*sin(t)]
    nuage.push P
dessineVoronoi nuage, "blue", 0.5

Le diagramme de Voronoï obtenu :

PNG

Avec la suite n3/1013

Le script :

f = (n) -> n*n*n/1013
nuage = []
P = [320,100]
for n in [1..400]
    t=2*pi*f(n)
    P = [P[0]+20*cos(t),P[1]+20*sin(t)]
    nuage.push P
dessineVoronoi nuage, "blue", 0.5

Le diagramme obtenu :

PNG

Avec la suite n²/321

Le script :

f = (n) -> n*n/321
nuage = []
P = [0,240]
for n in [1..600]
    t=2*pi*f(n)
    P = [P[0]+20*cos(t),P[1]+20*sin(t)]
    nuage.push P
dessineVoronoi nuage, "blue", 0.5

Le diagramme obtenu est périodique :

PNG

Avec la suite n3/1002

Le script montre le cadrage optimal :

f = (n) -> n*n*n/1002
nuage = []
P = [320,160]
for n in [1..1000]
    t=2*pi*f(n)
    P = [P[0]+10*cos(t),P[1]+10*sin(t)]
    nuage.push P
dessineVoronoi nuage, "blue", 0.5

Le diagramme est étonnamment symétrique :

PNG

ImageJ

Le logiciel de retouche d’image ImageJ possède un filtre « Voronoï ». Par exemple, en appliquant sur une image blanche le filtre « salt and pepper » qui engendre un nuage de points uniformément distribués (points noirs, d’un pixel chacun), le filtre Voronoï, on obtient quelque chose comme ceci :

Ce filtre sert à améliorer des images de cellules prises au microscope, pour les isoler et les compter.

Blender 3d

Pour Blender, Voronoï est une texture. Par exemple, voici une « icosphère » bleutée, mais non texturée :

Pour lui donner un aspect moins uniforme, on modifie selon un diagramme de Voronoï, l’emplacement des points la composant. Pour texturer un objet, cliquer sur l’icône en forme de damier (en haut à gauche) puis, à l’aide du double triangle à droite, dérouler un menu dans lequel on peut choisir la texture « Voronoï » (par défaut c’est « nuage ») :

L’effet choisi a consisté ici à

  • choisir une couleur magenta foncée (en bas) pour les creux
  • appliquer la texture au rayon local de la sphère (« displacement », légèrement négatif)
  • appliquer aussi la texture au vecteur normal (« normal », là aussi légèrement négatif) :

L’effet obtenu est un peu extraterrestre :

Ce n’est plus Voronoï, c’est plutôt verrue-noï !

Voir aussi ce TP fait en Seconde, où des élèves avaient construit des diagrammes de Voronoï à la règle et au compas !


Portfolio


Commentaires

Navigation

Articles de la rubrique

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 8 février 2017, 14h-18h, campus du Tampon, amphi 120 B
- Mercredi 8 mars 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 12 avril 2017, 14h-18h, campus du Tampon
- Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mardi 13 juin 2017, 14h-18h, campus du Tampon
- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6

Semaine des mathématiques

Du 23 mars au 4 avril 2017 dans l’académie de la Réunion.


Brèves

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

L’algorithmique à l’IREM de Lille

vendredi 26 juin 2009

Le groupe AMECMI de l’IREM de Lille vient de mettre en ligne des ressources importantes au service des professeurs de Seconde :

- Algorithmique et programmation (Emmanuel Ostenne)
- Bibliographie amoureuse de l’algorithmique (Alain Juhel)

Statistiques

Dernière mise à jour

lundi 27 février 2017

Publication

732 Articles
Aucun album photo
125 Brèves
11 Sites Web
126 Auteurs

Visites

72 aujourd'hui
1186 hier
1933135 depuis le début
6 visiteurs actuellement connectés