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 :

  1. on parcourt l’image, pixel par pixel, dans une double boucle (sur x et y) ;
  2. pour chaque pixel, on calcule les distances qui le séparent de A, B et C.
  3. on compare ces distances, et selon les résultats des tests, on choisit la couleur.
  4. 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 :

PDF - 152.3 ko
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) :

CarMetal - 4.7 ko
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 :

PDF - 20.8 ko

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).

4 points

La plupart des copies donnaient cette construction :

Certains élèves semblent convaincus que la médiatrice s’arrête aux traits de compas :

Un autre cas où les médiatrices sont perçues comme incomplètes :

Idem, mais d’une autre manière :

Idem mais avec un autre triangle :

Avec deux triangles :

5 points

La figure la plus répandue dans la classe :

Avec les médiatrices incomplètes :

Idem mais avec un autre carré :

Avec un cercle en plus :

Une figure plus chargée (il semble que cet élève ait décidé de mettre un maximum de traits pour être certain d’avoir les bons) :

7 points

La figure de tout le monde (ou presque) :

La version avec les médiatrices incomplètes :

Idem mais avec un autre hexagone :

Avec deux triangles et un cercle :

Une autre figure mystérieuse :

Encore une autre :

Et encore une :

8 points

La figure la plus répandue :

Celle avec les médiatrices incomplètes :

Idem mais deux autres carrés :

La même chose mais avec les traits de construction :

Tracé de traits plus ou moins au hasard :

Tracé du plus grand nombre de traits possible :

Mais là le record est battu !

Le corrigé du DM a été fait avec Voroglide (en accompagnement personnalisé).

Pour en savoir plus, voir la fin de ce film, où on montre une application esthétique des diagrammes de Voronoï.


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- 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

dimanche 26 mars 2017

Publication

735 Articles
Aucun album photo
128 Brèves
11 Sites Web
126 Auteurs

Visites

677 aujourd'hui
853 hier
1963096 depuis le début
48 visiteurs actuellement connectés