DM 2 -- Dessin de polygones

Mars 2004

Versions imprimables : sujet.ps, sujet.pdf.

Ce devoir consiste à manier les transformations affines du plan. Il s'agit d'écrire un programme capable de lire en entrée un texte décrivant des opérations sur des points du plan par de telles transformations, de calculer les résultats de ses opérations pour visualiser des polygones.

Par exemple, en exécutant
java Polygones < deuxTrigs.txt
avec le fichier deuxTrigs.txt contenant :

    triangle  o  i  ((/ 2) k) ;
    triangle  j  k  ((/ 2) k) ;

votre programme Polygones doit produire le dessin :

Explications :

Les points O=(0, 0), I=(1,0), J=(0,1) et K=(1,1) sont prédéfinis et sont dénotés par : o, i, j, et k respectivement.

(/ 2) désigne la transformation qui consiste à diviser par 2 (p --> 1/2 p). Il s'agit donc de l'homothétie de centre O et de rapport 1/2.

((/ 2) k) indique d'appliquer la transformation (/ 2) au point k. On obtient donc un point : le milieu 1/2 K de O et de K.

triangle o i ((/ 2) k) ; indique de peindre en noir l'intérieur du triangle de sommets O, I, 1/2 K.

triangle j k ((/ 2) k) ; indique de peindre en noir l'intérieur du triangle de sommets J, K, 1/2 K.

1 Le format d'entrée

La base du langage lu par votre programme en entrée concerne la description de points et de transformations.

1.1 Description des transformations et des points

On pourra définir un point ou une transformation ainsi :

    setp centre = ((/ 2) k) ;
    setm transl = (+ j) ;

Cela définit centre comme le point C de coordonnées C=(0.5, 0.5)=1/2 K et transl comme la transformation qui consiste à ajouter le point j, c'est à dire la translation de vecteur (0,1).

Les points o, i, j, k sont supposés prédéfinis.

Ainsi, en exécutant

setp j2 = ((/ 2) j) ;
setm t = (+ j2) ;

setp centre = ((/ 2) k) ;
triangle o i centre ;
triangle (t o) (t i) (t centre) ;

votre programme doit produire le dessin :

Ce programme définit t comme la translation de vecteur (0,0.5)=1/2 J. Le premier appel à triangle dessine donc le triangle du bas (O,I,C). Le deuxième dessine le triangle obtenu en translatant les points O,I,C de 1/2 vers le haut.

Des constructeurs similaires permettent de définir quelques transformations affines élémentaires (homothéties de rapport un entier ou l'inverse d'un entier, les rotations d'un nombre entier de degrés et les translations d'un vecteur donné par un point ou son opposé) :

* 4 définit l'homothétie de centre O et de rapport 4 (p --> 4 p).
/ 4 définit l'homothétie de centre O et de rapport 1/4 (p --> 1/4 p).
rot 20 définit la rotation de centre O d'un angle de 20 degrés.
+ v définit la la translation de vecteur v (p --> p + v).
- v définit la la translation de vecteur -v (p --> p - v).

On pourra de plus utiliser le produit pour exprimer la composition de plusieurs transformations. Par exemple, on pourra définir l'homothétie de centre O et de rapport 3/4 ainsi :

    setm hom3quart = (* 3) . (/ 4) ;

ou encore la rotation de 30 degrés autour de centre ainsi :

    setm rotc30 = (+ centre) . (rot 30) . (- centre) ;

Si les parenthèses sont nécessaires pour indiquer d'appliquer une transformation à un point comme dans (rotc30 a), elles ne le sont pas pour définir une transformation élémentaire, on pourra aussi bien écrire :

    setm hom3quart = *3 . /4 ;
    setp centre = (/2 k) ;
    setm rotc30 = +centre . rot 30 . -centre ;

Examinons maintenant comment produire un dessin plus complexe sur la base de rotations.

1.2 Un exemple plus complet

Une construction repeat 12 { ... } permettra de plus de répéter 12 fois les instructions entre accolades. (On pourra spécifier tout autre entier positif à la place de 12.) Ainsi, en exécutant

setp centre = (/2 k) ;                     # centre du carr'e
setm rotc30 = +centre . rot 30 . -centre ; # rotation de 30 degr'es autour du centre
setm rotc20 = +centre . rot 20 . -centre ; # rotation de 20 degr'es autour du centre

setp a = (/2 i) ;        # milieu de oi
setp b = (rotc20 a) ;

repeat 12 {
  triangle centre a b ;
  # passer au secteur suivant :
  setp a = (rotc30 a) ;
  setp b = (rotc30 b) ;
} ;

votre programme doit produire le dessin :

Chaque itération du repeat 12 { ... } produit un des triangles de la roue, obtenu par rotation autour du centre du carré à partir du précédent.

2 Modalités

Le travail minimal demandé consiste à programmer la lecture et l'interprétation de telles instructions, ce qui correspond aux paragraphes 3, 4 et 5.

Le paragraphe 3 décrit la syntaxe du langage. Le paragraphe 4 décrit comment interpréter le langage (un programme est fournit pour les graphismes), et les bases algorithmiques pour manier des transformations affines sont données au paragraphe 5.

Quelques extensions facultatives (comme l'utilisation de couleur ou la définition de procédures) sont proposées au paragraphe 6.

La remise des travaux se fera par la commande :

/users/profs/info/Depot/INF_431/deposer documents DM_2 groupe

avant la date limite du 28 avril. documents désigne un ou plusieurs fichiers sources (terminaison en .java) et des fichiers d'exemple. Un fichier, avec un nom comme lisez_moi.txt, contenant des explications synthétiques sur votre travail, comment utiliser le programme, ..., est également souhaité. groupe doit être remplacé par le numéro de groupe de TD, de 1 à 10.

Pour faciliter la correction, il est demandé que la classe principale s'appelle Polygones et que l'exécution se fasse par :
java Polygones < mon_dessin.txt

3 Syntaxe du langage

Un programme de dessin sera donc une suite d'instructions. Les instructions sont des définitions de points ou de transformations, des repeat ou des dessins de triangles par triangle .... Chaque instruction est suivie d'un point-virgule ;. Un point est soit obtenu en rappelant la valeur associée à un identificateur, soit en appliquant une transformation à un point. Une transformation est obtenue soit en composant deux transformations, soit en rappelant la valeur associée à un identificateur, soit à partir des constructeurs élémentaires définis ci-dessus.

Formellement, le langage à reconnaître peut se définir par la grammaire suivante. Les non-terminaux sont écrits en lettres capitales et | sert à séparer plusieurs choix possibles pour la dérivation d'un même non-terminal. ( A )* indique une suite éventuellement vide de A.

PROGRAMME	::=	( INSTRUCTION ; )*

INSTRUCTION	::=	triangle POINT POINT POINT
	\|	setp IDENTIFICATEUR = POINT
	\|	setm IDENTIFICATEUR = TRANSFORMATION
	\|	repeat ENTIER { PROGRAMME }

POINT	::=	IDENTIFICATEUR
	\|	( TRANSFORMATION POINT )

TRANSFORMATION	::=	TRANSFORMATION . TRANSFORMATION
	\|	IDENTIFICATEUR
	\|	+ POINT
	\|	- POINT
	\|	* ENTIER
	\|	/ ENTIER
	\|	rot ENTIER
	\|	( TRANSFORMATION )

ENTIER désigne une constante numérique entière (i.e. une suite de chiffres), positive ou nulle. IDENTIFICATEUR désigne un nom autre qu'un mot clé. Plus précisément, un nom sera constitué d'une lettre éventuellement suivie d'une suite de lettres ou de chiffres ou de _ (caractère souligné).

4 Exécution des dessins

4.1 Librairie graphique

La partie graphique du programme reposant sur une partie du cours (awt) non encore traitée, le programme Fenetre.java vous est donné pour visualiser la partie [0,1]×[0,1] du plan. Il est inutile d'essayer de comprendre le programme, son utilisation se réduit aux appels suivants :

    Fenetre f = new Fenetre (300) ;
    f.clear () ;
    f.triangle (.5, .7, 0., 0., 1., 0.) ;
    f.ligne (.1, 0., .1, 1.) ;

Fenetre f = new Fenetre (300) ; créé une fenêtre de taille 300x300 ((0,0) est en bas à gauche et (1,1) en haut à droite).
f.clear () ; efface la fenêtre.
f.triangle (.5, .7, 0., 0., 1., 0.) ; indique de peindre l'intérieur du triangle (.5, .7), (0., 0.), (1., 0.) en noir.
f.ligne (.1, 0., .1, 1.) ; indique de dessiner en noir un segment (.1, 0), (.1, 1).

4.2 Interprétation des instructions

Une fois une instruction lue en entrée, votre programme doit l'interpréter. Une classe Environnement permettra d'associer dynamiquement une valeur à une variable. On stockera les associations nom, point et les associations nom, matrice de transformation (voir au paragraphe 5 la représentation des transformations) dans une table.

Le plus rapide consiste certainement à utiliser la classe java.util.Hashtable et à stocker toutes les associations dans la même table. Une solution simple (si l'on veut programmer sa propre structure de table) consiste à utiliser deux listes d'associations, une pour les variables points et une autre pour les variables matrices.

Le point (respectivement la matrice) sera calculé au moment de l'exécution de l'instruction setp (respectivement setm). L'environnement permettra de retrouver la dernière valeur associée à un nom. Remarquons que la grammaire utilisée permet de savoir lors de l'utilisation de la valeur associée à un nom si l'on attend un point ou une matrice. On pourra ainsi écrire :

    setp a = ((+ i) a) ;

Cela associera à a la valeur précédente de a (qui est supposée être un point) translatée de (1, 0).

On n'oubliera pas de prédéfinir dans l'environnement les points de noms o, i, j, k et de coordonnées respectives (0,0), (1,0), (0,1), (1,1)¹ .

5 Représentation interne des transformations

Pour manipuler plus facilement les transformations affines, on les maniera sous forme de matrices 3× 3. Pour cela, un point (x, y) sera représenté par le vecteur :

æ
ç
ç
è

ö
÷
÷
ø

Une rotation d'angle theta autour de O sera codée par la matrice :

æ
ç
ç
è

cos theta	-sin theta	0
sin theta	cos theta	0
0	0	1

ö
÷
÷
ø

Une translation de vecteur (dx, dy) sera codée par la matrice :

æ
ç
ç
è

1	0	dx
0	1	dy
0	0	1

ö
÷
÷
ø

Une homothétie de rapport r et de centre O sera codée par la matrice :

æ
ç
ç
è

r	0	0
0	r	0
0	0	1

ö
÷
÷
ø

Outre le fait que l'image d'un point par une transformation s'obtient par le produit matrice par vecteur, l'avantage de cette représentation réside dans le fait que la matrice associée à la composition de deux transformations s'obtient comme le produit matriciel de leurs deux matrices.

6 Extensions

Les quatre extensions proposées sont indépendantes et peuvent être traitées dans un ordre quelconque. On remarquera cependant que les extensions 6.1 et 6.2 demandent beaucoup moins d'efforts que les deux suivantes.

6.1 Les couleurs

On utilisera le codage hsb qui code une couleur par trois nombres rééls h, s, b entre 0 et 1 où h désigne la teinte (« hue » en anglais), s la saturation, b l'intensité (« brightness » en anglais). La teinte peut varier du rouge au vert (h=0 à 0.33333), du vert au bleu (h=0.33333 à 0.66666) et du bleu au rouge (h=0.66666 à 1). 0 et 1 représentent la même teinte.

La couleur varie de plus du gris à la couleur pure quand la saturation augmente (s=0 à 1), du noir à la couleur la plus lumineuse possible quand l'intensité augmente (b=0 à 1).

On peut de plus inclure un paramètre a (pour « alpha ») qui code l'opacité de l'objet qu'on dessine (a=0 pour un objet transparent et a=1 pour objet opaque). La couleur de chaque point est alors obtenue par combinaison linéaire entre la couleur voulue et la couleur du point avant dessin. On codera les couleurs sous forme de quatre points : H=(h,0), S=(s,0), B=(b,0), A=(a,0). Seule l'abscisse de ces points sera prise en compte.

Par exemple, en exécutant

couleur   o i i i ;                 # rouge, satur'e, lumineux, opaque
triangle  o  i  ((/ 2) k) ;         #  ((/ 2) k) est le milieu de ok
couleur   ((* 2).(/ 3) i) i i i ;   # bleu, satur'e, lumineux, opaque
triangle  j  k  ((/ 2) k) ;   
couleur ((/ 3) i) i i ((/ 3) i) ;   # vert, satur'e, lumineux,  tr`es transparent
triangle  o j ((rot 300) j) ;       # rotation de -60 degr'es

votre programme doit produire le dessin :

Pour cela, la classe fenêtre fournie au paragraphe 4.1 contient de plus une méthode couleur() :

   Fenetre f = new Fenetre (440) ;
   f.couleur (.33333333, 1.0, 1.0, 0.6) ;

Ainsi f.couleur (.33333333, 1.0, 1.0, 0.6) ; indique que la couleur des prochains dessins dans une Fenetre f sera : h=0.33333333, s=1, b=1, a=0.6. (Tous les appels consécutifs à f.triangle () ou f.ligne () seront affectés.)

Votre programme pourra maintenant reconnaître le jeu suivant plus complet d'instructions de graphisme :

triangle a b c pour dessiner un triangle abc,
ligne a b pour dessiner un trait ab,
clear pour effacer toute la fenêtre,
couleur h s b a pour indiquer la couleur du prochain dessin.

L'exemple suivant roueCoul.txt (qui est similaire à la roue du paragraphe 1.2) doit produire :

6.2 Définition de transformations quelconques

Toute transformation affine peut-être définie par l'image qu'elle donne des points O,I,J. En effet, les équations M O=P₁, M I=P₂, et M J=P₃ donnent presque directement la matrice M de la transformation à partir des images P₁, P₂, P₃ des points O,I,J.

Inclure une construction transf POINT POINT POINT supplémentaire de transformation dans votre langage.

6.3 Définition de procédures

Augmenter la syntaxe du langage reconnu par votre programme pour définir des procédures grâce au mot-clé proc.

proc essai v1 v2 { ... } définira une procédure de nom essai qui prend en argument deux points associés aux noms v1 et v2.
L'instruction d'appel essai i (/2 i) évaluera les deux arguments qui seront associés à v1 et v2 dans un contexte local avant d'effectuer le bloc d'instructions associé à la procédure essai. Si une variable n'est pas définie dans le contexte local, on la cherchera dans le contexte plus global dans lequel l'appel à la procédure a été fait. Si le nombre d'arguments ne correspond pas au nombre de variables dans la définition de la fonction, une erreur se produira.

Ainsi, en lisant en entrée triangleVide.txt votre programme doit produire :

L'exemple suivant triangleGlob.txt utilise à la fois des variables globales et locales, ce qui doit produire :

Une instruction ifpos permettra de plus de tester si un point a ses deux coordonnées strictement positives et d'effectuer un bloc d'instructions si c'est le cas. Il sera ainsi possible de définir des procédures récursives comme dans sierpinski.txt qui doit produire :

La grammaire s'enrichit donc de trois nouvelles dérivations pour une instruction :

INSTRUCTION	::=
	\|	proc IDENTIFICATEUR LISTEVARS { PROGRAMME }
	\|	IDENTIFICATEUR LISTEARGS
	\|	ifpos POINT { PROGRAMME }
LISTEVARS	::=	( IDENTIFICATEUR )*
LISTEARGS	::=	( POINT )*

Remarquons que l'extension 6.2 permet de passer une transformation m en argument, il suffit pour cela de passer (m o), (m i) et (m j). La transformation peut alors être reconstruite à partir de ces trois points.

6.4 Les réels

Il serait plus approprié que les constructeurs *, /, rot prennent en argument un réel plutôt qu'un entier. Augmenter votre langage pour lire des nombres en virgule flottante. On pourra de plus rajouter la définition de variables réelles au moyen d'un mot clé setr. On définira aussi des expressions sur les réels :

EXPRESSION	::=	EXPRESSION + EXPRESSION
	\|	EXPRESSION - EXPRESSION
	\|	EXPRESSION * EXPRESSION
	\|	EXPRESSION / EXPRESSION
	\|	( EXPRESSION )
	\|	FLOTTANT
	\|	IDENTIFICATEUR

L'utilisation de points pour couleur et ifpos était un peu artificiel, il serait plus approprié d'utiliser des expressions réelles. Pour cela, on utilisera de nouvelles instructions coul et ifp de significations similaires mais prenant des expressions réélles en arguments. Cela permettra de toujours faire marcher les exemples précédents qui utilisent couleur et ifpos.