|
|
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.
Figure 8.1 : Tracés de vecteur
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; } } |
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; } } |
y = y0 + ë (x-x0) |
|
+ 0.5 û |
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); } } |
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; } |
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.
Figure 8.5 : La définition de la lettre (a) en Metafont dans la police cmr8
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.6 : Le ``bitmap `` de la lettre (a) dans une police fixe 8 × 13
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.
Figure 8.7 : Défilement de texte dans une fenêtre
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); } |
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; } } } |
|
static Point lirePoint () { while (!button()) ; Point p = getMouse (); while (button()) ; return p; } |
static Point lirePoint () { while (!button()) ; while (button()) ; return getMouse (); } |
for (;;) { Event e = nextEvent(); switch (e.type) { case keyPressed: ... break; case keyReleased: ... break; case mousePressed: ... break; case mouseReleased: ... break; ... } } |
|
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(); } } |
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.
Figure 8.9 : Un cadre en AWT
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"); } } |
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"); } } |
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); } } |
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.
Figure 8.10 : Un bouton en AWT
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); } } |
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.
Figure 8.11 : Deux boutons et un texte en AWT
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); } } |
|
<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> |
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(); } } |
|
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; } |
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.12 : Angle formé par un vecteur et l'axe Ox
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; } |
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; } } |
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; } } |