Domaines de Voronoï en Seconde et en JavaScript

vendredi 1er avril 2011
par Alain BUSSER

Pour trois points A, B et C donnés, le domaine de Voronoï de A est formé des points du plan qui sont plus près de A que de B et C. On le colorie en rouge dans le TP ci-dessous. Les domaines de Voronoï de B et C sont définis de façon analogue, et coloriés respectivement en bleu et en vert. Le but du TP est de les dessiner.

Pour dessiner les domaines de Voronoï, un algorithme qui marche bien est le suivant :

on parcourt l’image, pixel par pixel, dans une double boucle (sur x et y) ;
pour chaque pixel, on calcule les distances qui le séparent de A, B et C.
on compare ces distances, et selon les résultats des tests, on choisit la couleur.
On colorie le pixel.

Mais d’abord, quelques rappels du collège avec les domaines de Voronoï de deux points, qui sont des demi-plans. En fait les points de la médiatrice de [AB] ne peuvent être coloriés ni en rouge ni en bleu, et constituent le diagramme de Voronoï de A et B.

Pour réaliser le TP, il faut un logiciel doté d’un langage de programmation et de possibilités de manipulation de pixels. Bref, un logiciel de traitement d’image. C’est le logiciel ImageJ qui a été choisi, parce qu’il est à la fois libre et multiplateforme, et parce qu’il permet de programmer en JavaScript.

Voici le sujet du TP au format pdf :

le sujet du TP

La première partie consiste pour les élèves à recopier du JavaScript dans la console, ce qu’ils adorent faire. Mais c’est dès cette étape que le gros blocage est survenu : Plusieurs postes étaient munis de la version 1.6.0_22 de la machine Java, sous laquelle ImageJ n’arrivait pas à exécuter les scripts. Les postes munis de la version 1.6.0_17 ou antérieure marchaient très bien, ainsi que les postes munis de la version 1.6.0_23. Mais pas ceux munis de la version 1.6.0_22, sous Windows. Des problèmes similaires avaient déjà été signalés...

Dans ces conditions, impossible d’évaluer le TP (la première heure ayant été passée à tenter un débogage, sans succès parce que les droits d’utilisateur sont trop restreints sur les postes du lycée). Ceci dit, l’étape 2 a été intéressante puisque quelques élèves (que des filles) ont réussi à étendre le test de distance à ceci :

if(dA<dB&dA<dC){
c=256*256*255;
}

qui donne le domaine de Voronoï correct pour le point A :

avec un bug intéressant

Au début, deux des élèves avaient tapé

if(dA<dB&dA<dC&dA){
c=256*256*255;
}

ce qui a produit le dessin suivant :

suffisamment artistique pour qu’on ait envie de l’agrandir :

Le script complet donne, avec le rajout suivant :

ip.moveTo(A[0],A[1]);
ip.lineTo(B[0],B[1]);
ip.lineTo(C[0],C[1]);
ip.lineTo(A[0],A[1]);

le dessin avec le triangle ABC :

ou comment utiliser le centre du cercle circonscrit sans le cercle lui-même !

Ce que permet aussi ImageJ

Puisque ImageJ peut calculer la transformée de Fourier bidimensionnelle d’une image, autant en profiter ! Sur l’image précédente, on obtient ceci :

On peut créer des pixels noirs dans une figure blanche avec ce script :

var N=400;
dessin=IJ.createImage("voronoi3p", "RGB", N, N, 1);
ip=dessin.getProcessor();
var A=[N/2,N/4];
var B=[N/8,4*N/5];
var C=[3*N/4,N/2];
ip.putPixel(A[0],A[1],0);
ip.putPixel(B[0],B[1],0);
ip.putPixel(C[0],C[1],0);
dessin.show();

Le dessin est presque invisible (les pixels sont tout petits) mais le filtre Voronoi d’ImageJ la transforme en ceci :

qui a tout de même un air de ressemblance avec la solution du TP !

Figure animée

La version dynamique est très intéressante algorithmiquement, parce qu’elle utilise des tests dans un domaine purement graphique : Le centre du cercle circonscrit découpe chaque médiatrice en deux demi-droites, dont une seule fait partie du diagramme de Voronoï. Pour afficher la bonne demi-droite, on doit effectuer un test !

Voici le résultat (fait sans JavaScript) :

**figure CaRMetal**

à télécharger et ouvrir avec CaRMetal

Au moment du corrigé, un devoir maison a été soumis aux élèves, sous la forme de diagrammes de Voronoï à construire au crayon sur papier (ça change de l’ordinaire !). En voici le sujet :

Quelques copies d’élèves

Dans chacun des onglets ci-dessous, la première copie était la plus répandue dans la classe. Pour chaque figure, une seule copie comportait une figure correcte (chaque fois le même élève).