Dans ce TD, il s'agit de gérer une file de priorité d'évènements de dessin. À tout instant, on peut ajouter des évènements dans la file ou retirer l'évènement dont la date est minimale. Les évènements seront des objets capables de produire un dessin ainsi que de nouveaux évènements. Ils seront représentés par l'interface Evenement suivante :
interface Evenement
{
int getDate () ; /* Renvoie la date `a laquelle effectuer
* l''ev'enement. */
void effectuer (Fenetre fen, FilePrio fp) ;
/* Appel'ee au moment d'effectuer l''ev'enement
* qui peut dessiner dans fen et rajouter
* de nouveaux 'ev'enements dans fp. */
}
Les dessins seront composés de rectangles définis selon l'interface Fenetre :
interface Fenetre
{
/* Peint un rectangle de coin sup'erieur gauche (xa, ya) inclus
* et de coin inf'erieur droit (xb, yb) exclus
* avec la couleur coul.
*/
void rectangle (int xa, int ya, int xb, int yb, int coul) ;
/* Couleurs :
* 0 pour blanc, 1 pour noir,
* 2-255 pour une teinte pure :
* 2-85 rouge au vert, 86-170 du vert au bleu,
* 171-255 du bleu au rouge.
*/
}
En plus des interfaces ci-dessus, les fichiers
Evenement.java et
Fenetre.java contiennent
des exemples d'implémentation de ces classes :
EvCarre (décrite un peu loin) et
FenEcran qui permet d'ouvrir une fenêtre à l'écran
et dessiner des rectangles dedans.
(La lecture du code de FenEcran est inutile
pour la compréhension du sujet.)
Il s'agit tout d'abord de programmer une file
de priorité pour gérer les évènements à effectuer.
On verra ensuite comment gérer les opérations de dessin au
moyen d'un quad-tree pour construire sa propre implémentation
de Fenetre.
Programmer une classe FilePrio qui permet
de représenter une file de priorité d'évènements.
Votre classe reposera sur la structure de tas
décrite un peu plus loin en 1.1.
On pourra ainsi utiliser votre file avec la méthode main suivante :
public static void main (String[] args) {
Fenetre fen = new FenEcran (256) ;
FilePrio fp = new FilePrio (100) ; // Capacit'e du tas
fp.ajouter (new EvCarre (0, 0, 12)) ;
while (fp.nonVide ()) {
Evenement e = fp.retirerMin () ;
e.effectuer (fen, fp) ;
}
}
La classe EvCarre (fournie dans
Evenement.java)
est un exemple d'implémentation
de l'interface Evenement.
Chaque appel e.effectuer (fen, fp)
dessine un carre dans fen par un appel
à fen.rectangle(...),
puis génère un nouveau EvCarre e2
de date postérieure et
décalé de 20 en x et en y qui est ajouté dans fp
par un appel à fp.ajouter (e2).
On doit ainsi obtenir un empilement de carres donnant
le dessin :
Notez que votre classe FilePrio doit fournir
deux méthodes non statiques nonVide
et ajouter.
Pour retrouver par vous même le code des transparents d'amphi, vous pouvez vous contenter des indications ci-dessous :
FilePrio.
Pour faire mieux : si jamais le
tableau est plein et qu'il faut ajouter un élément,
on créé un tableau de capacité double,
et on recopie l'ancien tableau dans le nouveau.
En insérant initialement un deuxième évènement
EvCarre avec une date légèrement postérieure par
fp.ajouter (new EvCarre (100, 28, 0)),
on obtient :
Récupérez ExEvts.java qui contient
des définitions d'évènements : Pyramide
qui produit une pyramide ou encore Pluie
qui produit des petits carrés aléatoires.
En insérant deux pyramides et une pluie par :
fp.ajouter (new Pyramide (0, 40, 50,50, 150, 150)) ;
fp.ajouter (new Pyramide (100, 150, 60,40, 200, 140)) ;
fp.ajouter (new Pluie (-50, 240, 256, 9)) ;
On obtient :
Le dessin en haut du sujet est obtenu par un
Entrelas (voir la définition de
Point dans la partie 2.) :
fp.ajouter (new Entrelas (0, 2, new Point (60, 80),
new Point (30, 200), new Point (130, 300))) ;
Des appels à Thread.sleep() permettent de
mettre le programme en pause durant un nombre donné de
milli-secondes. On peut ainsi utiliser l'évènement
Gravite qui simule le mouvement d'un carré
soumis à la gravité et qui rebondit.
Entre deux dessins successifs, le
déplacement est constant mais l'intervalle de temps dépend
de la vitesse. Pour en ressentir les effets sur trois
carrés en chute libre, vous pouvez utiliser la boucle
temporisée suivante :
fp.ajouter (new Gravite (0, 170, 10.f, 30.f, 40.f, 0.f, 250.f, 250.f)) ;
fp.ajouter (new Gravite (500, 90, 70.f, 120.f, 60.f, -80.f, 250.f, 250.f)) ;
fp.ajouter (new Gravite (1000, 230, 200.f, 40.f, 0.f, 0.f, 250.f, 250.f)) ;
long tpsDep = java.lang.System.currentTimeMillis() ;
while (fp.nonVide ()) {
Evenement e = fp.retirerMin () ;
while (java.lang.System.currentTimeMillis() + 5
< tpsDep + e.getDate ())
try { // Dormir un peu jusqu'`a e.getDate()
Thread.sleep (5) ;
} catch (InterruptedException exc) {}
e.effectuer (fen, fp) ;
}
Il s'agit maintenant de construire une implémentation
de Fenetre au moyen d'un quad-tree. On pourra
ensuite dessiner ce quad-tree dans une FenEcran
ou encore enregistrer le quad-tree sur disque pour pouvoir
sauver une image.
Programmer une classe Quad permettant de représenter
un noeud d'un quadtree. En résumé, un noeud est soit une feuille
dont il faut retenir la couleur, soit un noeud interne avec
quatre fils : sud-ouest, sud-est, nord-est et nord-ouest.
Le noeud nord-ouest est en haut à gauche et le noeud sud-ouest
en bas à droite.
Pour se simplifier la vie, on peut supposer qu'un noeud représentera toujours un carré de l x l pixels où l est une puissance de 2. Cette largeur peut-être stockée dans le noeud ou omise comme dans la version vue en amphi (voir à partir du Slide 37). Quitte à stocker la largeur, on stockera aussi la position (x,y) du pixel le plus en haut à gauche (le plus nord-ouest). Le noeud représentera donc les pixel (i,j) avec x ≤ i < x+l et y ≤ j < y+l. (Le coin nord-ouest a les coordonnées les plus petites puisque la convention traditionnelle veut que l'origine des écrans d'ordinateur soit en haut à gauche.)
Écrire une classe FenQuad qui implémente
l'interface fenêtre Fenetre.
L'image initialement blanche et de largeur prise en argument
du constructeur sera représentée par un quad-tree.
Écrire une méthode qui permet de peindre d'une couleur donnée un rectangle donné par deux points (xnw, ynw) (nord-ouest)et (xse, yse) (sud-est). On considère qu'un tel rectangle contient tous les pixels (x,y) avec xnw ≤ x < xse et ynw ≤ y < yse. On utilisera par exemple la classe suivante pour représenter les points :
class Point
{
int x, y ;
Point (int xx, int yy) {
x = xx ; y = yy ;
}
}
Écrire une méthode pour copier l'image vers un autre objet
de type Fenetre (un FenEcran
par exemple).
Vous pouvez ainsi tester votre classe en dessinant quelques
rectangles puis en visualisant à l'écran l'image obtenue.
Écrire une méthode permettant de sauver le quad-tree dans un fichier.
On utilisera pour cela la classe
java.io.OutputStream dont la méthode write(int) permet d'écrire
un octet (entier codé sur 8 bits) sur disque.
Un appel à new java.io.FileOutputStream ("fen.quad")
fournit un tel java.io.OutputStream qui
écrira dans un fichier de nom fen.quad.
Attention, un nombre plus grand que 256 ne tient pas sur 8 bits.
Écrire de même une méthode permettant de lire un quad-tree
ainsi sauvé sur disque. On utilisera la classe
java.io.InputStream dont la méthode read() lit un octet
d'un fichier et le renvoie.
Si la fin du fichier est atteinte, cette méthode renvoie -1.
Un appel à new java.io.FileInputStream ("fen.quad")
fournit un tel java.io.InputStream qui lira
les octets contenus dans le fichier de nom fen.quad.
Le dessin de lignes obliques et de triangles faisant appel à des problèmes de géométrie algorithmique non triviaux sont proposés en supplément.
Une solution avec compactage des bits, traçage de lignes et de triangles et taille de fenêtre quelconque.
Quelques exercices de plus pour faire plus :
