Précédent Remonter Suivant
Chapitre 8 Graphique

L es interfaces graphiques entre les utilisateurs et les ordinateurs sont très importantes. Depuis la première station de travail, l'Alto de Xerox en 1974, ces interfaces n'ont cessé de s'améliorer. En fait, une bonne partie de la programmation consiste à réaliser une interface agréable avec l'utilisateur. Dans ce chapitre, nous allons considérer les fonctions graphiques de base pour réaliser les tracés de vecteurs, de cercles, de coniques, ou de cubiques. Nous regarderons également les interactions possibles que l'utilisateur peut avoir pour entrer des données avec le clavier ou la souris. Depuis l'Alto, l'écran d'un ordinateur est assimilé à un bureau virtuel, sur lequel on peut empiler des feuilles de papier, encore appelées les fenêtres. On écrit en sortie dans une fenêtre; on envoie des événements en entrée à une fenêtre. L'interaction du système de fenêtre avec les fonctions graphiques est important. Malheureusement le système de fenêtres dépend souvent du langage de programmation utilisé; peu de standards existent. Ici, nous prendrons l'exemple de la bibliothèque AWT (Abstract Window Toolkit) de Sun Microsystems, et en soulignerons son style de programmation par objets. Enfin, nous survolerons quelques problèmes géométriques classiques.

8.1 Graphique ``bitmap``

Depuis les années 1970-80, l'écran d'un ordinateur est assimilé à une mémoire (vidéo) directement accessible par les processeurs de calcul; c'est une matrice de pixels (picture elements). Sa dimension vaut typiquement 1152 × 768. En noir et blanc, chaque pixel est représenté par un bit (0 pour blanc, 1 pour noir, ou le contraire); en couleur chaque pixel est représenté par un entier, qui tient par exemple sur 32 bits si on dispose de 232 couleurs. On dit aussi que 32 est la profondeur. Au total, l'écran est représenté par un tableau à trois dimensions, par exemple 1152 × 768 × 32. On dit aussi que la résolution de l'écran est 1152 × 768.


Figure 8.1 : Tracés de vecteur


Chaque pixel peut être assimilé à un disque de diamètre unité, repéré par les coordonnées entières de son centre (x,y). Pour dessiner une courbe sur l'écran, il faut positionner les pixels les plus proches de la courbe souhaitée, et donc discrétiser son tracé. Sur la figure 8.1, on voit les tracés de deux vecteurs de coordonnées (11, 8) et (11, 4). A basse résolution, ils ne ressemblent pas trop à des vecteurs, mais ils semblent parfaits aux résolutions habituelles des écrans.

Supposons les segments de droite donnés par les coordonnées de leurs extrémités. Soit donc un segment de droite P0P1 entre les deux points P0 et P1 de coordonnées (x0,y0) et (x1, y1). Posons dx = x1 - x0 et dy = y1 - y0. Soit m la pente du segment de droite, m=dy/dx. Pour simplifier, nous supposerons que l'on a 0 < m £ 1, dx > 0 et dy > 0. Comme la pente est plus petite que 1, on itère sur la coordonnée x à partir de x0 jusqu'à x1 en calculant l'ordonnée y donnée par l'équation y=y0 + m(x-x0) de la droite support. A chaque itération, on positionne le point (x, Math.round(y)) où la fonction Math.round calcule l'entier le plus proche de son argument flottant. Ce qui donne la fonction suivante, qui utilise une fonction tracerPixel qui est supposée positionner sur l'écran le pixel dont les coordonnées sont passées en arguments.


Figure 8.2 : Tracé de vecteur



static void tracerVecteur (int x0, int y0, int x1, int y1) {
  int dx = x1 - x0, dy = y1 - y0;
  float m = ((float)dy) / dx;
  for (int x = x0, float y = y0; x <= x1; ++x) {
    tracerPixel(x, Math.round(y));
    y = y + m;
  }
}

Cette fonction utilise des opérations flottantes, elle fait un calcul d'arrondi pour chaque pixel, elle est un peu lente. En fait, on peut la transformer en une fonction ne manipulant que des entiers. En effet, l'équation de la droite passant par (x0, y0) et (x1, y1) est
x dy - y dx - x0 dy + y0 dx = 0
dy = y1 - y0 et dx = x1 - x0. Si on maintient une erreur e entre le point (x, y) et la droite donnée par la formule suivante
e = x dy - y dx - x0 dy + y0 dx
(en supposant toujours la pente 0 £ dy/dx £ 1). Pour savoir si le pixel suivant sur la droite y = x+1 est à l'est ou au nord-est du point (x,y), on regarde le signe de l'erreur pour le point (x+1, y+0.5)
em = (x+1) dy - (y+0.5) dx - x0 dy + y0 dx
Soit
em = e + dy - dx/2
En multipliant par 2, on obtient
2 em = 2 e + 2 dy - dx
Si 2 em ³ 0, on positionne le pixel au nord-est et l'erreur devient 2 e' = 2em - dx. Sinon on positionne le pixel à l'est et l'erreur devient 2 e'' = 2em + dx. On en déduit la fonction suivante pour tracer un vecteur de pente positive inférieure à 1.
static void tracerVecteur (int x0, int y0, int x1, int y1) {
  int dx = x1 - x0, dy = y1 - y0;
  int e = 0;
  for (int x = x0, y = y0; x <= x1; ++x) {
    tracerPixel(x,y);
    int em = e + 2*dy - dx;
    if (em >= 0) {
      ++y;
      e = em - dx;
    } else
      e = em + dx;
  }
}

Comme x0, y0, x1, y1 sont entiers, toutes les opérations sont des additions entières de constantes. Cette fonction est souvent attribuée à Bresenham. Ce nom est passé dans le langage courant, et, de manière rapide, on dit que le tracé de vecteur est obtenu par un Bresenham.
Exercice 62   Compléter par symétrie le programme pour qu'il trace un vecteur de pente arbitraire.

Exercice 63   Ecrire une fonction à la Bresenham pour les tracés de cercles et d'ellipses.

Souvent on doit tracer un segment de droite à l'intérieur d'un rectangle donné. On peut remplacer l'appel à tracerPixel dans la fonction précédente par un appel à une fonction tracerPixelDansRectangle qui prendrait en troisième argument le rectangle en question. Mais une telle solution est lente, et ferait perdre beaucoup de temps si la majorité du segment est à l'extérieur du rectangle. Une meilleure solution consiste donc à calculer l'intersection du segment de droite avec le rectangle, et calculer le point le plus proche en conservant l'erreur introduite par le choix de ce point. Par exemple supposons que le bord gauche est de coordonnée xmin d'un rectangle. On calcule
y = y0 + ë (x-x0)
dy
dx
+ 0.5 û
et on démarre le tracé avec une erreur non nulle
2e = 2x dy - 2y dx - 2x0 dy + 2y0 dx

Ainsi si on trace un même segment à l'intérieur de deux rectangles contigus, le segment aura toujours l'air d'un segment de droite, plutôt qu'une ligne brisée si on avait oublié l'erreur pour lancer la fonction de tracé à la Bresenham. Ce point importe quand les rectangles correspondent à des parties de fenêtres cachées.

Un autre exemple de courbe classique est celui des cubiques de Bézier (Bézier spline). Ces courbes interviennent dans les dessins de carrosseries (Pierre Bézier était ingénieur chez Renault) ou dans les tracés de lettres. Une cubique de Bézier est donné par quatre points A, B, C, D, elle passe par les deux points A et B, et la valeur de ses tangentes en A sont les vecteurs AC en A et DB en B comme indiqué sur la figure 8.3. On peut montrer que la le segment de cubique entre A et B est toujours inscrit dans le quadrilatère ACDB. Ces cubiques ont la belle loi de décomposition suivante. Soient E, F, I, G, H, J, les milieux respectifs des segments AC, BD, CD, EI, FI, GH. Alors, la cubique de Bézier pour les points A, B, C, D est la courbe obtenue pour les points A, J, E, G suivie de celle pour les points J, B, H, F comme indiqué sur la figure 8.4. On peut donc tracer cette courbe récursivement en recalculant les points de contrôle de la cubique à chaque appel récursif. Quand le quadrilatère est très plat, on peut approximer le tracé par le segment de droite AB. D'où la fonction suivante:




    

Figure 8.3 : Cubiques de Bézier




Figure 8.4 : Décomposition d'une cubique de Bézier



static Point milieu (Point a, Point b) {
  return new Point ((a.x + b.x)/2, (a.y + b.y)/2);
}

static void tracerBezier (Point a, Point b, Point c, Point d) {
  if (estPlat (a, c, d, b) )
    tracerVecteur (a.x, a.y, b.x, b.y);
  else {
    Point e = milieu (a, c);
    Point f = milieu (b, d);
    Point i = milieu (c, d);
    Point g = milieu (e, i);
    Point h = milieu (f, i);
    Point j = milieu (g, h);
    tracerBezier (a, j, e, g);
    tracerBezier (j, b, h, f);
  }
}

estPlat est une fonction testant si les hauteurs CH et DH' du quadrilatère ACDB sont petites. En utilisant le produit vectoriel de AC et de CD, on a CH < e si et seulement si
|AC Ù AB|2 < 4 e2 × AB2
En prenant e=1, puisqu'il est inutile de descendre en dessous du pixel comme précision, on écrit la fonction estPlat.
static int produitVect (Point a, Point b, Point c, Point d) {
  return (b.x - a.x) * (d.y - c.y) - (b.y - a.y) * (d.x - c.x);
}

static int norme2 (Point a, Point b) {
  return (b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y);
}

static boolean estPlat (Point a, Point c, Point d, Point b) {
  int v = produitVect(a, c, a, b);
  int w = produitVect(b, d, b, a);
  int l2 = 4 * norme2(a, b);
  return v*v < l2 && w*w < l2;
}


Figure 8.5 : La définition de la lettre (a) en Metafont dans la police cmr8


Remarquons qu'on peut éviter d'allouer de la mémoire pour les nouveaux points dans la fonction tracerBezier en calculant directement les coordonnées des points J, E, F, G et H.

Les tracés de cubiques interviennent dans les dessins des lettres en imprimerie. Par exemple, le tracé du caractère (a) en police de caractères romane est grossi sur la figure 8.5. Les contours arrondis de la lettre sont des cubiques. Les coordonnées de leurs points de contrôle sont données sur la partie droite de la figure. Le programme Metafont qui permet de définir les polices de caractères minimisee le nombre de points contrôle à donner. Ce programme, dû à Knuth, est très astucieux. Il génère des caractères compatibles avec TeX et Latex. Les cubiques sont aussi à la base du fonctionnement de PostScript, le langage de programmation de la majorité des imprimantes, et de sa version simplifiée PDF.

Sur une imprimante, il y a typiquement 600 à 1200 points par pouce. Sur un écran d'ordinateur, la résolution est plus faible puisqu'il y a moins de 100 points par pouce. Du coup, les cubiques sont moins utilisées dans les tracés sur un écran. Elles apparaissent dans des systèmes comme MacOS X (avec Display PDF), ou autrefois NeXT-Step et NeWS (avec Display PostScript). Souvent, on se contente de tracés de vecteurs et de rectangles. En effet, les lettres digitalisées sont stockées comme des tableaux rectangulaires de pixels monocolores. Par exemple, la lettre (a) devient le rectangle de dimension 6 × 6 pixels représenté sur la figure 8.6, ou encore le tableau de 6 entiers {30, 1, 31, 33, 35, 29} en représentation binaire. Pour afficher la lettre (a) sur l'écran, il faut copier rapidement ce tableau rectangulaire de bits dans la mémoire vidéo de l'écran à l'endroit désiré pour l'afficher.


Figure 8.6 : Le ``bitmap `` de la lettre (a) dans une police fixe 8 × 13


Une autre opération fréquente sur les écrans est le défilement de texte dans une fenêtre. Il s'agit encore de copier la partie rectangulaire R de la fenêtre (la fenêtre sans la première ligne de texte) vers une autre partie rectangulaire R' (le haut de la fenêtre) pour libérer l'espace rectangulaire S (la dernière ligne de texte) qu'il faut mettre à blanc avant d'y afficher des lettres, comme indiqué sur la figure 8.7. Pour faire défiler le texte dans la fenêtre, on doit donc faire R' ¬ R et S ¬ 0. La fenêtre peut avoir une dimension proche de l'écran. Alors les rectangles R et R' peuvent contenir 1000 × 800 pixels, soit 800000 pixels à recopier rapidement. Remarquons aussi que R et R' se recouvrent et que la recopie doit se faire de haut vers le bas pour ne pas écraser les pixels à recopier. Le rectangle S est en général plus petit, il contient de l'ordre de 20000 pixels. Une opération de base du graphique ``bitmap ``est donc la copie d'une zone rectangulaire dans une autre (bit block transfert ou encore bitblt). La forme générale de cette opération est R ¬ R Ä S, où R, S sont deux rectangles de même taille et Ä est une opération booléenne sur les pixels. Pendant longtemps, l'optimisation de ces instructions a été un signe de qualité pour les stations de travail, avec des techniques sophistiquées comme le dépliage des boucles, ou la compilation au vol de code. Actuellement, ces opérations sont faites par le matériel, puisque les circuits graphiques ne sont plus compliqués à concevoir avec le développement foudroyant du matériel.


Figure 8.7 : Défilement de texte dans une fenêtre


Considérons le dépliage de boucle, comme exemple d'optimisation. Supposons que x1, y1, x2, y2 sont les champs désignant les abcisses et ordonnées des extrémités sud-ouest et nord-est d'un rectangle. Alors la fonction suivante recopie les pixels d'un rectangle source s dans un rectangle destination d.
static void bitblt (Rect d, Rect s) {
  for (int j = 0; j < d.y2 - d.y1; ++j)
    for (int i = 0; i < d.x2 - d.x1; ++i)
      copierPixel(d.x1+i, d.y1+j, s.x1+i, s.x2+j);
}

copierPixel(dx,dy,sx,sy) copie le pixel de coordonnées (sx,sy) dans le pixel (dx,dy). Souvent cette fonction peut être réalisée par une seule instruction machine. Comme on l'itère plusieurs centaines de fois, on exécute autant de fois le test de fin de boucle sur i. On obtient un facteur 2 en vitesse si on déplie la boucle un certain nombre de fois. Ici pour simplifier, nous ne la déplions que 4 fois; ce qui donne la fonction suivante:
static void bitblt (Rect d, Rect s) {
  for (int j = 0; j < d.y2 - d.y1; ++i) {
    int i = 0;
    switch ((d.y2-d.y1) % 4) {
      case 3: copierPixel(d.x1+i, d.y1+j, s.x1+i, s.x2+j); ++i;
      case 2: copierPixel(d.x1+i, d.y1+j, s.x1+i, s.x2+j); ++i;
      case 1: copierPixel(d.x1+i, d.y1+j, s.x1+i, s.x2+j); ++i;
      case 0:
    }
    while (i < d.x2 - d.x1) {
      copierPixel(d.x1+i, d.y1+j, s.x1+i, s.x2+j); ++i;
      copierPixel(d.x1+i, d.y1+j, s.x1+i, s.x2+j); ++i;
      copierPixel(d.x1+i, d.y1+j, s.x1+i, s.x2+j); ++i;
      copierPixel(d.x1+i, d.y1+j, s.x1+i, s.x2+j); ++i;
    }
  }
}

8.2 Entrées graphiques

Les dispositifs de pointage (souris, trackpad, tablettes) permettent de désigner des parties de l'écran. Les entrées graphiques se font en combinant la position du curseur et l'utilisation des boutons de la souris ou des touches du clavier. Supposons qu'il existe deux fonctions: button qui retourne un booléen qui ne vaut vrai que si un des boutons de la souris est enfoncé, et getMouse qui retourne un point donnant les valeurs des coordonnnées courantes du curseur.

Une entrée graphique peut se faire sur un front descendant d'un bouton de la souris. Cela correspond à la fonction suivante:
static Point lirePoint () {
  while (!button())
    ;
  Point p = getMouse ();
  while (button())
    ;
  return p;
}

On attend que le bouton soit enfoncé, on note alors les coordonnées du curseur, et on attend que le bouton soit relâché. Si on ne fait pas cette dernière attente, on peut relire deux fois de suite le même point si on itère sur la fonction lirePoint. Une technique plus sûre consiste à lire les coordonnées du curseur sur un front montant. On attend qu'un bouton de la souris soit relâché avant de faire la lecture des coordonnées du curseur.
static Point lirePoint () {
  while (!button())
    ;
  while (button())
    ;
  return getMouse ();
}

Ces deux dernières fonctions font des attentes actives. Par ailleurs, elles posent un problème quand on veut à la fois faire des entrées à la souris et au clavier. Il faut alors attendre un événement sur la souris ou un événement sur le clavier. La fonction lirePoint est blocante; sur le clavier, la lecture de caractères se fait aussi par une fonction blocante read(). On doit donc soit créer deux processus pour faire concurremment la lecture à la souris et au clavier, soit multiplexer les deux événements possibles à la souris et au clavier. La première solution est lourde. En général, on adopte la deuxième solution. Les bibliothèques de fonctions graphiques fournissent une structure d'événements multiplexés entre le clavier et la souris, générés dans une file d'attente. On peut lire ces événements dans cette file d'attente comme on lit les caractères sur un terminal. Un événement est émis quand on appuie sur un bouton de la souris, quand on le relâche, quand la souris se déplace, quand une touche du clavier est enfoncé, ou relâché. Pour chacun d'entre eux, la position courante du curseur est fournie, ainsi que le temps. Alors, la programmation avec les événements suit le schéma suivant:
for (;;) {
  Event e = nextEvent();
  switch (e.type) {
  case keyPressed: ... break;
  case keyReleased: ... break;
  case mousePressed: ... break;
  case mouseReleased: ... break;
  ...
  }
}

On peut remarquer qu'on ne fait plus d'attente active, car tout le problème est reporté sur la fonction de bibliothèque nextEvent.

La programmation avec les événements n'est pas très modulaire, puisqu'elle consiste à faire une grande boucle réagissant à tous les événements possibles. Si on veut détecter un double-clic à la souris, par rapport à la suite de deux événements souris, puis clavier, ou simplement deux clics simples consécutifs, il est plus facile de représenter la gestion des événements clavier-souris par un petit automate fini déterministe. En fait, la logique de ces interactions peuvent être incroyablement compliquée, et plusieurs systèmes ont été proposés pour en simplifier la programmation (Squeak, Esterel, Statecharts). En fait, ces systèmes permettent de traiter plus généralement de la programmation réactive dont la gestion des événements clavier-souris est un cas particulier. Souvent, cela revient à traiter les entrées graphiques par des automates indépendants, et la déterminisation de l'automate non-déterministe correspondant à leur réunion est assuré par le système proposé.

Une autre manière de gérer l'interaction avec le clavier et la souris se fait souvent par des fonctions de rappel (callbacks) dans les systèmes orientés vers la programmation par objets. Dans chaque classe graphique, on définit la fonction de rappel, c'est-à-dire la fonction à appeler lorsqu'un événement dû à une entrée graphique se produit. C'est la hiérarchie des classes qui permet d'appeler la bonne fonction. Nous allons voir cela dans le cas particulier de la bibliothèque AWT.

8.3 La bibliothèque AWT

Un système de fenêtres sur l'écran d'une station de travail est censé représenter les différentes feuilles de papier que l'on peut avoir sur un bureau. Certaines sont cachées par d'autres; certaines sont côte à côte; on écrit ou on dessine dans la majorité des fenêtres. Cette analogie a résisté à trente années d'évolution de l'informatique. Le modèle utilisé dans la bibliothèque AWT de Java provient de Smalltalk, un des premiers langages de programmation par objets inventé à Xerox. Il tend à séparer les parties modèle, présentation, et contrôle de chaque élément graphique. En effet, une interface graphique permet de représenter graphiquement un certains nombre de données du modèle sous-jacent. Il y a souvent plusieurs présentations possibles pour les mêmes données: par exemple des pourcentages peuvent être représentés par des barres colorées, ou par diagrammes en forme de camembert; un booléen peut être représenté par l'affichage textuelle de sa valeur, ou par l'état d'un bouton (enfoncé ou pas), ou par la couleur d'une fenêtre; etc. Pour le corps du programme, l'important est la valeur des données du modèle, et non leur représentation graphique. Pour l'interface graphique, au contraire, la présentation constituera l'essentiel de la programmation. La partie contrôle d'une interface consiste à définir l'interaction avec l'utilisateur, et la répercussion sur le modèle. Il repose aussi fortement sur la représentation hiérarchique des classes. Il est impossible d'exposer ici de manière didactique toute la bibliothèque AWT. Nous ne ferons ici qu'en présenter quelques exemples idiomatiques.

La classe Component est la classe abstraite de base du paquetage AWT. Un objet de cette classe, un composant, peut être spécialisé en un bouton, une étiquette, un canevas, un checkbox, un choix, un conteneur, une liste de textes, une barre de défilement, un texte, comme indiqué sur la figure 8.8. Le composant le plus simple est une étiquette (classe Label) qui permet de placer un texte dans un conteneur. Un conteneur (classe Container) est une liste de composants, affichés de devant vers l'arrière. Une fenêtre (classe Window) est un conteneur correspondant à une fenêtre dans le système de fenêtres du système sous-jacent. Un cadre (classe Frame) est une fenêtre avec un titre et un bord. Un exemple simple d'interface graphique est le suivant:


Figure 8.8 : La hiérarchie des composants graphiques en AWT



import java.awt.*;
class Frame1 {
  public static void main (String[ ] args) {
    Frame f = new Frame ("Une étiquette");
    f.add ("Center"new Label ("Bonjour les élèves!", Label.CENTER));
    f.setSize (300, 100);
    f.show();
} }


Figure 8.9 : Un cadre en AWT


Une cadre de taille 300 × 100 pixels est allouée avec le titre ``Une étiquette ``. Ce cadre peut contenir plusieurs composants comme tout conteneur; ici il ne contient qu'une étiquette avec le texte "Bonjour les élèves!" centré. La méthode add permet de rajouter des composants dans le cadre, initialement vide. Son premier argument est un attribut de placement de son second argument dans le cadre. Ici, l'étiquette est centrée. Le deuxième argument du constructeur Label indique la justification du texte dans l'étiquette. Enfin, la méthode show affiche ce cadre en le plaçant devant les autres fenêtres.

Le programme précédent peut aussi s'écrire dans un style plus orienté objet:
class Frame2 extends Frame {
  Frame2 (String s) {
    super(s);
    add ("Center"new Label ("Bonjour les élèves!", Label.CENTER));
    setSize (300, 400);
    show();
  }

  public static void main (String[ ] args) {
    Frame2 f = new Frame2 ("Une étiquette");
} }

La méthode paint est la méthode appelée dès que le système veut afficher le cadre. Par défaut, elle a une action standard dans tous les composants. On peut toutefois la redéfinir. Ici au bas du cadre, on dessine deux rectangles adjacents. L'argument de paint est un contexte graphique, qui donne l'état courant de dessin pour l'objet à dessiner. C'est le système qui appelle paint avec le bon état. Celui-ci contient des informations sur l'origine du rectangle contenant le cadre, sur sa taille, sur la couleur courante de dessin, sur la police de caractères courante, etc. La fonction getSize donne la taille du cadre. L'appel à super.paint passe l'ordre d'affichage à la méthode paint du conteneur qui la redispatche à tous les éléments du cadre.
class Frame3 extends Frame {
  Frame3 (String s) {
    super(s);
    add ("North"new Label ("Deux couleurs", Label.CENTER));
    setSize (300, 400);
    show();
  }

  public void paint (Graphics g) {
    super.paint(g);
    int w = getSize().width;
    int h = getSize().height;
    int x = w/2; int y = h/2;
    g.setColor(Color.red);
    g.fillRect(x-w/4, y-w/4, w/4, w/2);
    g.setColor(Color.yellow);
    g.fillRect(x, y-w/4, w/4, w/2);
  }

  public static void main (String[ ] args) {
    Frame3 f = new Frame3 ("Un contexte graphique");
  }
}

Des détecteurs d'événements peuvent être attachés à certains composants par la méthode addActionListener. Le paramètre est un objet implémentant une ActionListener, c'est-à-dire ayant un champ actionPerformed. Ce sera la fonction déclenchée quand l'action se produira. Dans l'exemple de base suivant, un bouton est créé dans un cadre, avec la fonction System.exit attachée. Le code de sortie est 0, indiquant une sortie sans erreur. Le bouton porte l'inscription ``Quitter ``:
import java.awt.*;
import java.awt.event.*;

public class Frame4 extends Frame {

  public Frame4 (String title) {
    super (title);
    setLayout (new FlowLayout());
    Button q = new Button ("Quitter");
    add(q);
    setSize (300, 100);
    q.addActionListener (new Quit());
    show();
  }

  public static void main (String[ ] args) {
    Frame4 f = new Frame4 ("Un bouton");
} }

class Quit implements ActionListener {
  public void actionPerformed (ActionEvent e) {
    System.exit(0);
} }


Figure 8.10 : Un bouton en AWT


On peut compliquer l'exemple en mettant cote à cote deux boutons ``Quitter `` et ``A `` et une zone de texte modifiable. Au premier bouton, on attache le même détecteur qu'auparavant. Le deuxième est associé à une fonction de la classe ActionA qui remplit la zone de texte avec la chaîne ``Bouton a! ``. Remarquons que la politique de disposition des composants dans le cadre est le mode FlowLayout, indiquant que les boutons doivent être mis cote à cote.
public class Frame5 extends Frame {

  public  Frame5 (String title) {
    super (title);
    setSize (300, 100);
    setLayout (new FlowLayout());
    Button q = new Button ("Quitter");
    Button a = new Button ("A");
    TextField t = new TextField (20);
    add(q); add(a); add(t);
    q.addActionListener (new Quit());
    a.addActionListener (new ActionA(t, "Bouton a!"));
    show();
  }

  public static void main (String[ ] args) {
    Frame5 f = new Frame5 ("Deux boutons et un texte");
} }

class ActionA implements ActionListener {
  TextField t; String s;
  ActionA (TextField t0, String s0) { t = t0; s = s0;  }

  public void actionPerformed (ActionEvent e) {
    t.setText(s);
} }


Figure 8.11 : Deux boutons et un texte en AWT


Voici un autre exemple d'interface où on a deux détecteurs d'actions déclenchées par des boutons, et une autre plus basique déclenchée par la souris. Cette dernière est mise en place par la fonction addMouseListener. L'action correspondante écrit sur le terminal les coordonnées courantes du curseur au moment où l'événement e de la souris s'est produit. Ces coordonnées sont accessibles par les méthodes getX et getY. Dans cet exemple, on utilise les fonctions validate et pack pour placer les boutons et la zone de texte.
public class Frame6 extends Frame {

  public Frame6 (String title) {
    super (title);
    setLayout (new FlowLayout());
    Button q = new Button ("Quit"); add(q);
    Button a = new Button ("A"); add(a);
    TextField t = new TextField (20); add(t);
    validate(); pack();
    q.addActionListener (new Quit());
    a.addActionListener (new ActionA(t, "Bouton a!"));
    addMouseListener (new ActionB());
    show();
  }

  public static void main (String[ ] args) {
    Frame6 f = new Frame6 ("Une interaction souris");
  }
}

class ActionA implements ActionListener {
  TextField t; String s;
  ActionA (TextField t0, String s0) { t = t0; s = s0;  }

  public void actionPerformed (ActionEvent e) {
    t.setText(s);
  }
}

class ActionB extends MouseAdapter {
  public void mouseReleased (MouseEvent e) {
    System.out.println ("Bouton B: " + e.getX() + "," + e.getY());
    System.exit(1);
  }
}

Les événements souris sont: bouton enfoncé, bouton relâché, souris déplacée, souris déplacée bouton enfoncé (drag). Un détecteur d'événements-souris MouseListener est une interface contenant les quatre méthodes mouseClicked, mouseEntered, mouseExited, mouseReleased. Pour simplifier la programmation, on peut utiliser un MouseAdapter qui est une implémentation de l'interface précédente avec les quatre méthodes prédéfinies comme étant vides. Ainsi on peut considérer des sous-classes de MouseAdapter en ne redéfinissant que les méthodes à spécifier.
Exercice 64   Programmer une interface utilisateur où on imprime les coordonnées du point courant sur un clic souris.

Exercice 65   Programmer une interface utilisateur qui dessine un vecteur entre deux points rentrés à la souris.

8.4 Un exemple d'appliquette

Une appliquette (applet) est une sous-classe des paneaux, et donc aussi une sous-classe des conteneurs de AWT, comme indiqué par la hiérarchie des classes de la figure 8.8. Une appliquette permet à un programme Java de s'exécuter dans un paneau à l'intérieur d'une page en format Html affichée par un navigateur (Tous les navigateurs modernes contiennent un interpréteur Java). Voici un exemple de telle page avec un paneau calculé par une appliquette dont le code est le code compilé d'une classe Mondrian et dont la taille est un rectangle 48 × 32 sur l'écran.
<html>
<head>
<title>Mondrian</title>
</head>
<body text="#00004c" bgcolor="#ffffff" link="#00004c">
<br><br><br>
<applet
    code=Mondrian.class
    width=48
    height=32> Mondrian
</applet> Une belle appliquette!
</body>
</html>

Le code (trop long) de l'appliquette n'a pas un grand intérêt, mais est assez représentatif. Il se trouve à de multiples endroits sur le Web: il s'agit de faire des tableaux imaginaires de Piet Mondrian, artiste abstrait du début du 20ème siècle. Quand l'appliquette est chargée, le contrôle est donné à sa méthode init; c'est là qu'on crée le processus exécutant l'appliquette et que l'on note les tailles du rectangle englobant passées en paramètres dans la page Web. L'appliquette contient aussi deux méthodes: start pour redémarrer l'appliquette chaque fois qu'elle a été stoppée, stop pour arréter l'exécution de l'appliquette. Typiquement le navigateur relance l'appliquette chaque fois que la page Web est affichée et l'arrête lorsque la page Web disparait. La méthode destroy sert à récupérer les ressources allouées à l'appliquette, quand on est sûr qu'elle ne réapparaitra pas. Enfin, la méthode run comme dans tout processus d'une classe Runnable est le point d'entrée du code de ce processus, appelé par t.start(). Cette fonction repeint le paneau de l'appliquette toutes les 4s ou quand le bouton de la souris est pressé.

Le code suivant tire au sort un certain nombre de lignes horizontales et verticales. Puis il tire un certain nombre de points en traçant les lignes horizontales ou verticales les plus longues ne coupant pas les lignes déjà tracées. Enfin, il tire au sort un autre ensemble de points pour colorier dans une couleur aléatoire les rectangles les contenant.
import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

public class Mondrian extends Applet implements Runnable {
  Thread t;
  final static int nMaxL = 4, nMaxR = 7, epaisseur = 1, pas = 2;
  static int nLV, nLH, nRects;
  static int xmax, ymax;
  Ligne[ ] lV = new Ligne[nMaxL*2], lH = new Ligne[nMaxL*2];
  Rect[ ] rect = new Rect[nMaxR];
  Random rand = new Random();

  public Mondrian() { super(); }

  public void init()
  {
    xmax = getSize().width; ymax = getSize().height;
    repaint();
    addMouseListener (new Action(this));
    t = new Thread (this);
    t.start();
  }

  public void start() {
    if (t.isAlive()) t.resume();
    else t.start();
    repaint();
  }

  public void stop() { t.suspend(); }
  public void destroy() { t.stop(); }
  public void run() {
    while (true) {
      repaint();
      try { Thread.sleep(4000); }
      catch (InterruptedException e) { stop(); }
    }
  }

  public void paint (Graphics g) {
   nLV = 0; nLH = 0; nRects = 0;
   g.setColor (Color.white);
   g.fillRect (0, 0, xmax, ymax);
   g.setColor (Color.black);
   choisirLV (1+randInt(nMaxL-1));
   choisirLH (1+randInt(nMaxL-1));
   choisirLV2 (1+randInt(nMaxL-1));
   choisirLH2 (1+randInt(nMaxL-1));
   choisirRects(3+randInt(nMaxR-3));
   dessinerRects (g);
   dessinerLV (g);
   dessinerLH (g);
  }

  int randInt (int m) {
    return Math.round(rand.nextFloat() * m) ;
  }

  void choisirLV (int n) {
    for (int i = 0; i < n; ++i) {
      int x = (randInt(xmax) / pas) * pas;
      lV[nLV++] = new Ligne(x, 0, x, ymax);
    }
  }

  void choisirLV2 (int n) {
    for (int i = 0; i < n; ++i) {
      int x = (randInt(xmax) / pas) * pas;
      int y = (randInt(ymax) / pas) * pas;
      lV[nLV++] = new Ligne(x, enDessousDe(x,y), x, auDessusDe(x,y));
     }
  }

  void choisirLH (int n) {
    for (int i = 0; i < n; ++i) {
      int y = (randInt(ymax) / pas) * pas;
      lH[nLH++] = new Ligne(0, y, xmax, y);
    }
  }

  void choisirLH2 (int n) {
    for (int i = 0; i < n; ++i) {
      int x = (randInt(xmax) / pas) * pas;
      int y = (randInt(ymax) / pas) * pas;
      lH[nLH++] = new Ligne(aGaucheDe(x,y), y, aDroiteDe(x,y), y);
    }
  }

  void dessinerLV (Graphics g) {
    for (int i = 0; i < nLV; ++i) {
      int dy = lV[i].y2 - lV[i].y1;
      g.fillRect(lV[i].x1, lV[i].y1, epaisseur, dy);
    }
  }

  void dessinerLH (Graphics g) {
    for (int i = 0; i < nLH; ++i) {
      int dx = lH[i].x2 - lH[i].x1;
      g.fillRect(lH[i].x1, lH[i].y1, dx, epaisseur);
    }
  }

  void choisirRects (int n) {
    for (int i = 0; i < n; ++i) {
      int x = randInt (xmax);
      int y = randInt (ymax);
      int x0 = aGaucheDe (x,y);
      int y0 = enDessousDe (x,y);
      int w = aDroiteDe (x,y) - x0;
      int h = auDessusDe (x,y) - y0;
      rect[nRects++] = new Rect (x0, y0, w, h);
    }
  }

  int aGaucheDe (int x, int y) {
    int res = 0;
    for (int i = 0; i < nLV; ++i) {
      int x2 = lV[i].x1;
      if (lV[i].y1 <= y && y <= lV[i].y2 && res < x2 && x2 <= x)
 res = x2;
    }
    return res;
  }

  int aDroiteDe (int x, int y) {
    int res = xmax;
    for (int i = 0; i < nLV; ++i) {
      int x2 = lV[i].x1;
      if (lV[i].y1 <= y && y <= lV[i].y2 && x <= x2 && x2 < res)
 res = x2;
     }
     return res;
  }

  int enDessousDe(int x, int y) {
    int res = 0;
    for (int i = 0; i < nLH; ++i) {
      int y2 = lH[i].y1;
      if (lH[i].x1 <= x && x <= lH[i].x2 && res < y2 && y2 <= y)
 res = y2;
    }
    return res;
  }

  int auDessusDe(int x, int y) {
    int res = ymax;
    for (int i = 0; i < nLH; ++i) {
      int y2 = lH[i].y1;
      if (lH[i].x1 <= x && x <= lH[i].x2 && y <= y2 && y2 < res)
 res = y2;
    }
    return res;
  }

  void dessinerRects (Graphics g) {
    for (int i = 0; i < nRects; ++i) {
      g.setColor(choisirCouleur());
      g.fillRect(rect[i].x, rect[i].y, rect[i].w, rect[i].h);
    }
    g.setColor(Color.black);
  }

  Color choisirCouleur() {
    int couleur = randInt(4);
    if (couleur == 0) return Color.yellow;
    if (couleur == 1) return Color.yellow;
    if (couleur == 2) return Color.blue;
    if (couleur == 3) return Color.red;
    return Color.red;
  }
}

class Ligne {
  int  x1,y1, x2,y2;
  Ligne(int a1, int a2, int a3, int a4) { x1 = a1; y1 = a2; x2 = a3; y2 = a4; }
}

class Rect {
  int  x,y,w,h;
  Rect(int a1, int a2, int a3, int a4) { x = a1; y = a2; w = a3; h = a4; }
}

class Action extends MouseAdapter {
  Mondrian t;
  Action (Mondrian t0) {t = t0; }
  public void mousePressed (MouseEvent e) {
    t.repaint();
  }
}

8.5 Enveloppe convexe

Le calcul de l'enveloppe convexe de n points est un des tous premiers algorithmes de l'algorithmique géométrique. Les deux algorithmes que nous considérerons, les marches de Jarvis et de Graham, s'appuient sur un calcul d'angles formés par les vecteurs avec l'axe horizontal. L'angle q formé par le vecteur P1P2 de coordonnées (dx, dy) avec l'axe Ox vérifie q = atan(dy/dx), comme indiqué sur la figure 8.12. Mais le calcul de la fonction Math.atan peut être long. Une astuce, due à Sedgewick, consiste à approximer cette valeur par une fonction theta(P1, P2) plus rapide à calculer et telle que q < q' si et seulement si theta(P1, P2) < theta(P1', P2'):
static float theta (Point p1, Point p2) {
  float t; int dx = p2.x - p1.x; int dy = p2.y - p1.y;
  if (dx == 0 && dy == 0) t = 0;
  else t = (float) dy / (Math.abs(dx) + Math.abs(dy));
  if (dx < 0) t = 2 - t;
  else if (dy < 0) t = 4 + t;
  return t;
}


Figure 8.12 : Angle formé par un vecteur et l'axe Ox


Pour le calcul de l'enveloppe convexe de n points P0, P1, ...Pn-1, le premier algorithme cherche d'abord un point d'ordonnée minimale, puis il consiste à trouver les points successifs de l'enveloppe dans l'ordre trigonométrique. Si P0, P1, ...Pm sont déjà sur l'enveloppe convexe, le point Pm+1 sur l'enveloppe est le Pi tel que Pm Pi fait un angle q minimal et positif avec l'axe Ox pour les Pi pas encore sur l'enveloppe, c'est-à-dire pour i plus grand que m. D'où la fonction de calcul d'enveloppe convexe (marche de Jarvis) retournant le nombre de points sur l'enveloppe:


Figure 8.13 : Enveloppe convexe



static int enveloppe (Point[ ] p) {
  int m = 0, n = p.length;
  if (n > 0) {
    int min = 0;
    for (int i = 1; i < n; ++i) if (p[i].y < p[min].y) min =  i;
    float angle1 = 0, angle2 = 400; do {
      Point t = p[m]; p[m] = p[min]; p[min] = t;
      ++m; min = 0;
      for (int i = m; i < n; ++i) {
        float alpha = theta(p[m-1], p[i]);
        if (angle1 < alpha && alpha < angle2) {
            min = i; angle2 = alpha;
        }
      }
      angle1 = angle2; angle2 = theta(p[min], p[0]);
     } while (min != 0);
  }
  return m;
}

Cette fonction a une complexité quadratique (en O(n2)).

Une autre technique permet d'aller plus vite. Soit P0 un point d'ordonnée minimale. Si on trie les points selon l'angle qi formé par P0Pi avec l'axe Ox, en ordre croissant, on trouve rapidement les points de l'enveloppe. En effet, on doit toujours tourner à gauche pour parcourir l'enveloppe dans l'ordre trigonométrique à partir de P0. Ainsi si P0, P1, ...Pm sont déjà sur l'enveloppe, le point Pi est le point suivant sur l'enveloppe si i est minimum tel que i > m avec un angle positif formé par les vecteurs Pm-1Pm et PmPi. Si l'angle est négatif, on tourne à droite en passant de Pm-1 à Pm puis à Pi. Il faut donc retirer le point Pm de l'enveloppe trouvée jusque là. Sur l'exemple de la figure 8.14. Au début P0, P1, P2 sont sur l'enveloppe convexe. Le virage P1, P2, P3 est à gauche, on rajoute donc P3 sur l'enveloppe. Mais le virage suivant P2, P3, P4 se fait à droite, on doit donc retirer P3. On considère maintenant le virage correspondant à P1, P2, P4. Il tourne à gauche, on garde donc P4. L'enveloppe est alors formée par P0, P1, P2, P4. On considère P5 et le virage P2, P4, P5, etc. Cels donnne la fonction suivante, dite marche de Graham:


Figure 8.14 : Enveloppe convexe



static int enveloppe (Point[ ] p) {
  int m = 0; int n = p.length;
  if (n <= 2) return n;
  else {
    int min = 0;
    for (int i = 1; i < n; ++i) if (p[i].y < p[min].y) min = i;
    for (int i = 0; i < n; ++i)
      if (p[i].y == p[min].y && p[i].x > p[min].x) min =  i;
    Point t = p[0]; p[0] = p[min]; p[min] = t;
    tri(p); m = 2;
    for (int i = 3; i < n; ++i) {
      while (trigonometrique(p[m], p[m-1], p[i]) >= 0)
        --m;
      ++m;
      t = p[m]; p[m] = p[i]; p[i] = t;
    }
    return m+1;
  }
}
Cette fonction a une complexité quadratique (en O(nlogn)).

Pour tester si l'angle P1P0P2 est positif, on peut calculer le produit vectoriel P0 P1 Ù P0 P2, comparer les normes, s'il l'angle est nul.
static int trigonometrique (Point p0, Point p1, Point p2) {
  int dx1 = p1.x - p0.x; int dy1 = p1.y - p0.y;
  int dx2 = p2.x - p0.x; int dy2 = p2.y - p0.y;
  if (dx1 * dy2 > dy1 * dx2) return 1;
  else if (dx1 * dy2 < dy1 * dx2) return -1;
  else {
    if (dx1 * dx2 < 0 || dy1 * dy2 < 0) return -1;
    else if (dx1*dx1 + dy1*dy1 > dx2*dx2 + dy2*dy2) return 1;
    else if (dx1*dx1 + dy1*dy1 == dx2*dx2 + dy2*dy2) return 0;
    else return -1;
  }
}

Exercice 66   Construire un interface graphique pour calculer une enveloppe convexe de n points, entrés à l'aide d'une souris.





L'algorithmique géométrique a bien d'autres développements. C'est une des parties les plus difficiles de l'algorithmique, entrainant la révision de beaucoup de notions usuelles en mathématiques. Un des problèmes courants est la présence de points singuliers ou exceptionnels. Nos programmes de calcul d'enveloppe convexe marchent-ils encore lorsque tous les points sont alignés? C'est ce genre de problèmes qu'il faut traiter avec soin dans ce genre d'algorithmes.


Précédent Remonter Suivant