TD 9 - Tas et quad-trees

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.

1.  Tas et file de priorité

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.

1.1  Rappels sur les tas

Pour retrouver par vous même le code des transparents d'amphi, vous pouvez vous contenter des indications ci-dessous :

1.2  Jouons un peu

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) ;
        }

Une solution.

2.  Dessin dans un quad-tree

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.

2.1.  Le quad-tree

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

2.2.  La fenêtre et le dessin

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

Une solution avec compactage des bits, traçage de lignes et de triangles et taille de fenêtre quelconque.

3.  Supplément

Quelques exercices de plus pour faire plus :




INF421a énoncé par Laurent Viennot. Last modified: Sat Oct 16 11:16:17 CEST 2004