Upload
others
View
6
Download
0
Embed Size (px)
Citation preview
Enoncés des travaux dirigés d'informatique, pre-mière année
Table des matières
1 TD 1 : Deviner un nombre tiré au hasard 3
2 TD 2 : Histogramme d'une loi normale 4
3 TD 3 : Montant numérique, montant littéral 6
4 TD 4 : Tri quicksort, représentation sous forme de graphes 7
5 TD 5 : Dessin d'une ligne en 4-connexité 10
6 TD 6 : Dessiner un portrait par une seule ligne continue 15
7 TD 7 : Image de synthèse, portrait déformé 18
8 TD 8 : Enregistrer des �chiers sur une clé USB 36
9 TD 9 : Enregistrer des �chiers sur une clé USB, utilisation d'une interface fenêtrée 39
10 TD 10 : Enregistrer des �chiers sur une clé USB, utilisation d'une interface fenêtrée,enregistrement des paramètres 48
11 TD 11 : Lecture d'un �chier XML, copie de �chiers 49
12 TD 12 : Recherche de mots-clé dans une page HTML 54
13 TD 13 : Simulation d'une corde suspendue 56
14 Correction du TD 1, page 3 61
15 Correction du TD 2, page 4 62
16 Correction du TD 3, page 6 68
17 Correction du TD 4, page 7 74
18 Correction du TD 5, page 10 80
19 Correction du TD 6, page 15 85
20 Correction du TD 7, page 18 105
1
21 Correction du TD 8, page 36 109
22 Correction du TD 9, page 39 112
23 Correction du TD 10, page 48 115
24 Correction du TD 11, page 49 117
25 Correction du TD 12, page 54 120
26 Correction du TD 13, page 56 130
2
1 TD 1 : Deviner un nombre tiré au hasard
(correction page 61)
Ecrire un programme qui tire un nombre au hasard (entre 1 et 20 par exemple) et demande à l'utilisateurde le deviner. A chaque réponse, le programme dit si le nombre saisi est au-dessus ou en-dessous de labonne réponse.
Fonctions utiles :
raw_input(str) Permet de saisir une réponse, a�che str à l'écran et retourneune chaîne de caractères.
randint(a, b)
Permet de tirer un entier au hasard entre a et b. Cette fonc-tion fait partie du module random. Pour l'utiliser, il fautajouter au début du programme la ligne import random puisécrire h = random . randint(1, 20), par exemple.
Travail à faire :
Reprendre le programme et faire en sorte que le joueur joue autant de fois qu'il le veut. Lorsqu'il a �ni, leprogramme doit a�cher le nombre moyen de coups joués à chaque partie.
3
2 TD 2 : Histogramme d'une loi normale
(correction page 62)
L'objectif de ce TD est de véri�er numériquement pour un exemple le théorème central limite. Soit k ∈ Net n ∈ N, on suppose que (X1, . . . , Xnk) sont des variables aléatoires de Bernouilli telles que :
∀i, P (Xi = 0) =12et P (Xi = 1) =
12
On construit la suite de variables (Y1, . . . , Yn) telles que :
∀i, Yi =k∑
j=1
Xij
On véri�e que :
∀i, ∀l ∈ {0, . . . , k} , P (Yi = l) =C l
k
2k
Yi suit une loi binomiale B(k, 1
2
). Le théorème centrale limite permet d'a�rmer que :
1√n
n∑i=1
(Yi − k
2
)√k4
L−→ N (0, 1)
Pour véri�er numériquement ce théorème, l'idée est de comparer graphiquement l'histogramme de la loinormale et celui des variables Yi. Pour ce faire, on tire aléatoirement n réels (Zi) suivant la loi normale.Un histogramme calculé à partir de cet échantillon est une suite de nombres entiers (hm) telle que :
hm =1n
n∑i=1
1{Zi∈[mε,(m+1)ε[}
Autrement dit, hm est le nombre de nombres Zi compris dans l'intervalle [mε, (m + 1) ε[.
1)La première étape consiste à construire l'histogramme de la loi normale. On pourra prendre commevaleur :
n = 10000 ; ε = 0, 1
Fonctions utiles :
gauss(mean, var)
Permet de tirer un nombre au hasard selon une loi nor-male de moyenne mean et de variance var. Cette fonctionfait partie du module random. Pour l'utiliser, il faut ajouterau début du programme la ligne import random puis écrireh = random . gauss(0, 1), par exemple.
round(x, d) Permet d'arrondir le nombre x à d décimales.
4
L'histogramme pourra être représenté à l'aide d'un dictionnaire. Il sera ensuite a�ché puis recopié dansle tableur Excel a�n de le faire apparaître graphiquement (par l'intermédiaire d'un graphe de type XY).Cette courbe sera comparée à celle de la fonction1 :
f(x) =1√2π
e−x2
2 , qui est la fonction densité d'une loi normale.
2)La seconde étape consiste à construire l'histogramme de la variable Y ′ =√
4k
(Y − k
2
)avec Y =
k∑j=1
Xj
et Xj un entiers aléatoire, 0 ou 1. On pourra prendre comme valeur :
n = 10000 ; ε = 0, 1 ; k = 400
On construit donc un nombre Y comme étant la somme de k entiers aléatoires choisis dans l'ensemble{0, 1} et on en déduit Y ′. Puis on construit un autre histogramme de la même manière que celui de laquestion 1 mais cette fois-ci pour n nombres Y ′
i construits comme le précédent. On récupère le résultatsous Excel pour véri�er, en principale, que la courbe obtenue suit à peu près le même dessin que celui del'histogramme obtenu à la question 1.
Fonctions utiles :
randint(a, b)
Permet de tirer un entier au hasard entre a et b. Cette fonc-tion fait partie du module random. Pour l'utiliser, il fautajouter au début du programme la ligne import random puisécrire h = random . randint(1, 20), par exemple.
sqrt(x)
Calcule la racine carrée du nombre x. Cette fonction faitpartie du module math. Pour l'utiliser, il faut ajouterau début du programme la ligne import math puis écrirer = math . sqrt(6), par exemple.
Travail à faire :
Que se passe-t-il si on choisit k = 100 ? Pourquoi les courbes obtenues pour les deux questions ne coïncident-elles plus ?
Indice : Les deux courbes ont-elles le même nombre de points ? Quelle est la véritable valeur ε de l'histo-gramme obtenu pour k = 100 ?
1On compare en fait les courbes, (mε, hm)m et (mε, f(mε)ε)m. La valeur de l'histogramme correspondant à la valeur del'intégrale de la densité sur l'intervalle [mε, (m + 1)ε].
5
3 TD 3 : Montant numérique, montant littéral
(correction page 68)
L'objectif de ce TD est d'écrire un programme qui convertit en entier un nombre écrit sous forme littérale.On suppose que tous les nombres sont écrits en minuscules et correctement orthographiés.
1)Ecrire une fonction qui prend un nombre littéral et retourne une liste contenant tous ses mots.
Fonctions utiles :
replace(str, old, new)
A l'intérieur de la chaîne str, remplace toutes les occurrencesde la chaîne old par la chaîne new. Pour l'utiliser, il fautajouter au début du programme la ligne import string puisécrire l = string . replace (”dix− neuf”, ”− ”, ” ”), parexemple.
split(str[, sep])
Retourne une liste contenant tous les mots de la chaînede caractères str. Si le paramètre facultatif sep est ren-seigné, c'est cette chaîne qui fait o�ce de séparateur entremot et non les espaces. Pour l'utiliser, il faut ajouter audébut du programme la ligne import string puis écrirel = string . split (”vingt et un”, ” ”), par exemple.
2)Ecrire une fonction qui reçoit une chaîne de caractères dont la juxtaposition correspond à un nombrecompris entre 0 et 16 inclus, ainsi que les nombres 20, 30, 40, 50, 60 et qui retourne sa valeur.
3)A l'aide de la fonction précédente, écrire une fonction qui reçoit une chaîne de caractères contenant unnombre compris entre 0 et 99 inclus et qui retourne sa valeur.
Travail à faire :
Pour véri�er que la fonction précédente marche bien dans tous les cas, écrire une fonction qui écrit unnombre sous sa forme littérale puis véri�er que ces deux fonctions marchent correctement pour les nombrescompris entre 0 et 99.
6
4 TD 4 : Tri quicksort, représentation sous forme de graphes
(correction page 74)
Ce TD a pour objectif de présenter l'algorithme de tri quicksort qui permet de trier par ordre croissant unensemble d'éléments (ici des chaînes de caractères) avec un coût moyen en O (n lnn) où n est le nombred'éléments à classer. Cet algorithme itératif insère un à un les éléments d'une liste à trier dans un graphe.Chaque n÷ud de ce graphe est relié à deux autres n÷uds :
1. Un n÷ud avant qui permet d'accéder à tous les éléments classés avant celui de ce n÷ud, s'il y en a.
2. Un n÷ud apres permet d'accéder à tous les éléments classés après celui de ce n÷ud, s'il y en a.
1)On cherche à construire une classe ayant pour nom NoeudTri, qui dérive de object et qui contient unechaîne de caractères initialisée lors de la création de la classe : n = NoeudTri(”essai”).
2)On écrit la méthode __str__ de sorte que l'instruction print n a�che la chaîne de caractères quecontient n.
3)On cherche maintenant à dé�nir d'autres n÷uds, reliés à des variables avant et apres. On suppose queles n÷uds utilise l'attribut mot, on crée alors une méthode insere(s) qui :
� Si s < self.mot, alors on écrit que avant = NoeudTri(s).� Si s > self.mot, alors on écrit que apres = NoeudTri(s).
Fonctions utiles :
cmp(s1, s2)Compare deux chaînes de caractères, retourne -1,0,1 selonque s1 est classée avant, est égale ou est classée après s2.
La variable __dict__ est automatiquement incluse dans la classe NoeudTri. C'est un dictionnaire quicontient toutes les variables de la classe NoeudTri. Une fois que la méthode insere est écrite, on utilisele code suivant pour constater la création des variables avant et apres.
import pprint
racine = NoeudTri ("un")
print "------------------------------"
pprint.pprint (racine.__dict__)
racine.insere ("unité")
print "------------------------------"
pprint.pprint (racine.__dict__)
racine.insere ("deux")
print "------------------------------"
pprint.pprint (racine.__dict__)
Quel est le résultat ?
4) Il s'agit ici de modi�er la méthode __str__ a�n que l'instruction print n a�che avant.__str__()et apres.__str__() quand elles existent. Il ne faut pas perdre de vue que l'objectif est de trier une listede mots. Qu'est-ce qu'a�che le programme suivant ?
racine = NoeudTri ("un")
print "------------------------------"
print racine
7
racine.insere ("unité")
print "------------------------------"
print racine
racine.insere ("deux")
print "------------------------------"
print racine
5)Est-il possible de trier plus de trois mots avec ce programme ? Que faut-il modi�er dans la méthodeinsere a�n de pouvoir trier un nombre quelconque de mots ?
6)Cette dernière partie utilise un module téléchargeable depuis internet qui permet de dessiner un graphe,en particulier celui dé�ni par le n÷ud racine. La première étape est l'installation de ce module en quatreétape :
1. Téléchargement du module graphlib-0.5.1.tar.gz à l'adressehttp ://www.personal.psu.edu/sta�/i/u/iua1/python/graphlib/html/dist/
2. Décompression du �chier graphlib-0.5.1.tar.gz dans un répertoire temporaire, par exemplec :/python_pack.
3. On ouvre une fenêtre de commande dans le répertoire c :/python_pack/graphlib-0.5.1, puis on tapela commande set path = %path%; c : \python23. c :\python23 est le répertoire d'installation dulangage Python. En écrivant path, on véri�e que le répertoire c :\python23 a bien été ajouté à laliste des répertoires par défaut.
4. On tape la commande python setup.py install. La �gure 4.1 montre ce qui doit normalementapparaître à l'écran.
Fig. 4.1 � Etat de la fenêtre après l'installation du module graphlib-0.5.1.tar.gz.
8
Une fois le module installé, on cherche à a�cher sous forme de graphe celui qui est implicitement contenudans le n÷ud racine. L'utilisation de ce module sort du cadre de ce TD. Toutefois, si les noms des classeset membres des classes de votre programme sont identiques à ceux proposés dans l'énoncé du TD, il su�td'ajouter ces trois morceaux de codes à votre programme pour créer une image graph.png représentant legraphe :
1. Le premier morceau doit être inséré au début du programme. Il importe le module permettant detracer des graphes.
import graphlib.GraphDot as GraphDot
2. Le second morceau est une méthode qui doit être inséré à l'intérieur de la classe NoeudTri.
def affiche_graph (self, dot, n = 0):
n += 1
self.id = n
dot.node_style (self.id, label=self.str)
if "avant" in self.__dict__:
n = self.avant.affiche_graph (dot, n)
dot.edge_style (self.id, self.avant.id, label = "-")
if "apres" in self.__dict__:
n = self.apres.affiche_graph (dot, n)
dot.edge_style (self.id, self.apres.id, label = "+")
return n
3. Le troisième morceau doit être ajouté à la �n du programme. Il appelle la méthode précédemmentdé�nie puis construit l'image �nale.
dot = GraphDot.Dot ()
racine.affiche_graph (dot)
dot.save_img(file_name='graph', file_type='png')
Etant donné que ce module utilise des programmes exécutables issus d'une librairie Gra-phviz, si aucune image graph.png n'est créée, il est possible que certains programmes exé-cutables manquent. Pour les obtenir, il su�t de télécharger le �chier dot.zip à l'adressehttp ://perso.wanadoo.fr/x.dupre/programmation/python_ressources/dot.zip puis de décompresser ce �-chier dans le répertoire où se trouve le programme Python. Après une nouvelle exécution, l'image devraitapparaître.
Travail à faire :
Ajouter le code nécessaire a�n que la méthode insere génère une exception lorqu'un mot déjà présentdans l'arbre est à nouveau inséré.
9
5 TD 5 : Dessin d'une ligne en 4-connexité
(correction page 80)
1)
L'objectif est ici de modi�er un programme existant a�n de l'adapter à une tâche sen-siblement équivalente. On utilise pour cela le programme référencé à l'adresse internethttp ://perso.wanadoo.fr/x.dupre/programmation/python_cours_exemple_programme_html/bresenham_ligne.html. Bien qu'il soit repris dans cet énoncé, l'algorithme qu'il implémenteest décrit en détail dans le document fourni à l'adresse http ://perso.wanadoo.fr/x.dupre/programmation/python_cours_exemple.pdf
Ce programme implémente l'algorithme de Bresenham qui permet de tracer une ligne sans e�ectuer nimultiplication ni division. La droite obtenue est 8-connexe, c'est-à-dire que deux pixels voisins de cettedroite ont au moins un sommet en commun. L'objectif de ce TD est d'adapter le programme précédenta�n que la droite obtenue soit 4-connexe, c'est-à-dire que deux pixels voisins ont une arête en commun.L'algorithme suivant permet de tracer une ligne en 8-connexité.
Algorithme 5.1 : tracé d'une ligne (Bresenham)On suppose qu'on doit tracer la ligne rejoignant les pixels de coordonnées (x1, y1) à (x2, y2). Onsuppose de plus que : x2 > x1, y2 > y1 et x2 − x1 > y2 − y1. Les autres cas sont obtenus parsymétrie par rapport aux axes et aux premières bissectrices. On suppose que (x1, y1, x2, y2) ∈ N4.Etape A : initialisation
vx ←− x2 − x1
vy ←− y2 − y1
b ←− vx2
y ←− y1
initialisation
Etape B : étape principalepour x = x1 à x2 faire
dessiner le point de coordonnées (x, y)b←− b− vy
si b < 0y ←− y + 1b ←− b + vx
�n si�n pour
Le programme2 qui suit implémente cet algorithme qui permet de tracer une ligne en 8-connexité.
1 # -*- coding: cp1252 -*-
2 """ce module contient la fonction trace_ligne qui retourne l'ensemble des pixels
3 concernés par le tracé d'une ligne en 8-connexité entre deux pixels"""
4 import pygame # pour les affichages
5 import random
6
7 def trace_ligne_simple (x1,y1,x2,y2):
8 """trace une ligne entre les points de coordonnées (x1,y1) et (x2,y2),
9 on suppose que x2 > x1, y2 >= y1,
2Ce programme utilise pour les a�chages le module pygame disponible à l'adresse http ://www.pygame.org/.
10
10 retourne la ligne sous la forme d'un ensemble de pixels (x,y)"""
11
12 if y2 - y1 <= x2 - x1 : # droite en dessous de la première bissectrice
13 vx = x2 - x1
14 vy = y2 - y1
15 b = vx / 2
16 y = y1
17 x = x1
18
19 ligne = []
20 while x <= x2 :
21 ligne.append ((x,y))
22 b -= vy
23 x += 1
24 if b < 0:
25 b += vx
26 y += 1
27 return ligne
28 else : # droite au dessus de la première bissectrice
29 vx = x2 - x1
30 vy = y2 - y1
31 b = vy / 2
32 y = y1
33 x = x1
34
35 ligne = []
36 while y <= y2 :
37 ligne.append ((x,y))
38 b -= vx
39 y += 1
40 if b < 0:
41 b += vy
42 x += 1
43 return ligne
44
45 def trace_ligne (x1,y1,x2,y2):
46 """trace une ligne entre les points de coordonnées (x1,y1) et (x2,y2),
47 aucune contrainte sur les coordonnées,
48 retourne la ligne sous la forme d'un ensemble de pixels (x,y)"""
49
50 if x1 == x2 :
51 if y1 <= y2: return [ (x1, i) for i in xrange (y1,y2+1) ]
52 else : return [ (x1, i) for i in xrange (y2,y1+1) ]
53
54 if y1 == y2 :
55 if x1 <= x2: return [ (i, y1) for i in xrange (x1,x2+1) ]
56 else : return [ (i, y1) for i in xrange (x2,x1+1) ]
57
58 if x1 < x2 :
59 if y1 < y2 :
11
60 return trace_ligne_simple (x1,y1,x2,y2)
61 else :
62 ligne = trace_ligne_simple (x1,y2,x2,y1)
63 return [ (x,y1 + y2 - y) for (x,y) in ligne ]
64
65 if x2 < x1 :
66 if y1 < y2 :
67 ligne = trace_ligne_simple (x2,y1,x1,y2)
68 return [ (x1 + x2 - x, y) for (x,y) in ligne ]
69 else :
70 ligne = trace_ligne_simple (x2,y2,x1,y1)
71 return [ (x1 + x2 - x, y1 + y2 - y) for (x,y) in ligne ]
72
73 def display_ligne (ligne, screen):
74 """affiche une ligne à l'écran"""
75 color = 0,0,0
76 for p in ligne:
77 pygame.draw.line (screen, color, p,p)
78 pygame.display.flip ()
79
80
81 def attendre_clic (screen):
82 """attend la pression d'un clic de souris pour continuer"""
83 reste = True
84 while reste:
85 for event in pygame.event.get():
86 if event.type == pygame.MOUSEBUTTONUP :
87 reste = False
88 break
89
90 if __name__ == "__main__" :
91 pygame.init ()
92
93 size = width, height = x,y = 200, 200
94 black = 0, 0, 0
95 white = 255,255,255
96 screen = pygame.display.set_mode(size)
97 screen.fill (white)
98
99 print trace_ligne (0,0, 7,3)
100 # affiche [(0, 0), (1, 0), (2, 1), (3, 1), (4, 2), (5, 2), (6, 3), (7, 3)]
101
102 for n in xrange (0,10):
103 x1 = random.randint (0,x-1)
104 y1 = random.randint (0,y-1)
105 x2 = random.randint (0,x-1)
106 y2 = random.randint (0,y-1)
107 ligne = trace_ligne (x1,y1,x2,y2)
108 display_ligne (ligne, screen)
109
12
110 attendre_clic (screen)
2)
L'objectif de cette seconde question est de s'inspirer de l'algorithme 5.1 a�n de tracer - sans multiplicationni division - une ellipse de centre (x0, y0), de demi grand axe a et de demi petit axe b. Son équationcartésienne est la suivante :
x2
a2+
y2
b2= 1
L'algorithme est décrit dans le document fourni à l'adresse http ://perso.wanadoo.fr/x.dupre/programmation/python_cours_exemple.pdf. Il y est également démontré que le tracé obtenu ne s'écarte pas de plus d'undemi-pixel de la courbe de l'ellipse.
Algorithme 5.2 : tracé d'une ellipse (Bresenham)
On suppose qu'on doit tracer l'ellipse d'équation x2
a2 + y2
b2= 1. On suppose que a 6= 0 et b 6= 0
auquel cas, les ellipses sont des segments. On suppose (a, b) ∈ N2.Etape A : initialisation
A ←− a2
B ←− b2
x ←− ay ←− 0vx ←− aBvy ←− 0β ←− vx
2
Le point (x, y) est la position du pixel qui fera partie de l'ellipse. Le vecteur (vx, vy) re-présente le vecteur normal à l'ellipse au point (x, y). Ce vecteur est constamment égal à(vx, vy) = (xB, yA) =
(xb2, ya2
).
13
Etape B : tracé du premier huitièmetant que (vx > vy) faire
dessiner le point de coordonnées (x, y)y ←− y + 1vy ←− vy + Aβ ←− β − vy
si β < 0x ←− x− 1vx ←− vx −Bβ ←− β + vx
�n si�n tant que
Etape C : tracé du second huitièmetant que (x > 0) faire
dessiner le point de coordonnées (x, y)x ←− x− 1vx ←− vx −Bβ ←− β + vx
si β > 0y ←− y + 1vy ←− vy + Aβ ←− β − vy
�n si�n tant que
Etape D : autres huitièmesLe reste de l'ellipse est obtenu par symétrie par rapport aux deux axes durépère orthonormé du plan.
14
6 TD 6 : Dessiner un portrait par une seule ligne continue
(correction page 85)
Cette idée est tirée d'un article3 qui décrit l'image d'un portrait grâce un seul trait contigü (voir �gure 6.2).L'algorithme qui permet d'obtenir les résultats de la �gure 6.2 s'inspire de l'optimisation de la tournéed'un voyageur de commerce. Des villes sont disséminées sur toute l'image, plus une zone de l'image estsombre, plus elle acceuillera de villes. Une fois les villes placées, il su�t d'utiliser un algorithme permettantde déterminer le plus court chemin le plus passant par toutes les villes. Les valeurs qui ont permis d'obtenirces images sont k = 3 et γ = 9.
Fig. 6.2 � Dessin de Marylin Monroe et de la Joconde à l'aide d'un seul trait contigü. Le portrait deMarylin contient 20332 neurones, Mona Lisa 27486. Pour ces deux images, k = 3 et γ = 9. De loin, l'uniquechemin disparaît pour laisser place au portrait.
3Robert Bosch, Adrianne Herman, Continuous line drawings via the traveling salesman problem, Operations ResearchLetters (32), page 302-303, 2004.
15
Algorithme 6.1 : portraitSoit I(n, m) une image ayant n lignes et m colonnes. On suppose que k, γ ∈ N∗.Etape A : zoom
L'image est agrandie pour obtenir la taille (kn, km). Chaque pixel de cetteimage contient une intensité en niveau de gris, 0 pour noir, 255 pour blanc.
Etape B : partitionnementOn partitionne l'image en carrée de k × k pixels. Sur chaque carrée (i, j), ondétermine l'intensité moyenne µij . On calcule ensuite le nombre gij :
gij = γ −⌊γµij
256
⌋gij
γ est l'obscurité moyenne sur ce petit carré.
Etape C : voyageur de commerceOn répartit de manière aléatoire et uniforme gij villes dans le carré de coor-données (i, j) puis on optimise la tournée d'un voyageur de commerce.
L'objectif de ce TD est de se servir du programme développé pour la résolution duvoyageur de commerce disponible à l'adresse http ://perso.wanadoo.fr/x.dupre/programmation/python_cours_exemple_programme_html/tsp_kruskal.html et de l'utiliser pour créer l'image �gure 6.2.Il n'est pas nécessaire de connaître la méthode qui permet de résoudre ce problème, elle est néan-moins détaillée dans le document disponible à l'adresse http ://perso.wanadoo.fr/x.dupre/programmation/python_cours_exemple.pdf.
L'extrait de programme qui suit dé�nit les paramètres de l'algorithme 6.1, charge une image représentantun portrait puis exécute la séquence d'instructions permettant d'obtenir le meilleur chemin.
gamma = 9 # paramètre gamma
park = 30 # paramètre k, pas trop petit pour commencer,
# de plus en plus petit par la suite (jusqu'à 3)
# chargement d'une image
image = pygame.image.load("bette_davis.png")
size = image.get_size ()
xx,yy = size [0], size [1]
X,Y = int (xx // park) + 1, int (yy // park) + 1
# à cet endroit, il faut déterminer l'emplacement des villes
# en utilisant l'image, la fonction construit_ville
# du programme initial doit être réécrite
villes = construit_ville (image, gamma, park)
# les lignes qui suivent décrivent la séquence à écrire pour
# obtenir le plus court chemin passant pour toutes les villes
arbre = arbre_poids_minimal (villes,park)
chemin = circuit_eulerien (villes ,arbre)
neurone = circuit_hamiltonien (chemin)
neurones = [ villes [i] for i in neurone ]
amelioration_chemin (neurones, park, X,Y, 6, screen)
16
La recherche d'un plus court chemin pour quelques dizaines de milliers de villes est onéreuse en tempsde calcul. Il est conseillé dans un premier temps de prendre des valeurs pour les paramètres γ et k quine génère pas trop de villes. Les étapes s'enchaînent rapidement jusqu'au résultat �nal. Et une fois leprogramme mis au point pour un problème de petite taille, il sera possible de le faire tourner pendantquelques heures avec un grand nombre de points a�n d'obtenir une image proche de la �gure 6.2. A�nd'éviter de construire un trop grand nombe de villes, l'étape A a été éludée.
Le programme qui résoud le problème du voyageur de commerce utilise le module pygame qui permet faci-lement de réaliser des a�chages. Il est disponible à l'adresse http ://www.pygame.org/. Il utilise égalementle module psyco qui permet d'accélérer la vitesse d'exécution d'un programme. Ce module est disponibleà l'adresse http : //psyco.sourceforge.net/.
17
7 TD 7 : Image de synthèse, portrait déformé
(correction page 105)
Le document http ://perso.wanadoo.fr/x.dupre/programmation/python_cours_exemple.pdf présente laméthode du lancer de rayon pour construire des images de synthèse. Celle-ci est implémentéeau moyen de cinq �chiers accessibles à l'adresse http ://perso.wanadoo.fr/x.dupre/programmation/python_cours_exemple_programme_html/index.html. Les seuls objets que ce programme peut dessinersont des sphères et des facettes triangulaires ou en forme de parallélogrammes plan. L'objectif de ceTD est d'ajouter de nouveaux objets qui puissent être dessinés sur des images de synthèse par simpledérivation d'une classe.
1)Le premier problème à résoudre consiste à construire une facette rectangulaire dont la surface est celled'une image. Ce nouvel objet est modélisé par une nouvelle classe qui hérite de la classe rectangle (�chierimage_synthese_facette.py. La �gure 7.3 montre un exemple de résultat qu'on veut obtenir.
Fig. 7.3 � Portrait de Bette Davis partiellement caché par l'ombre d'une sphère.
Soit une facette en forme de quadrilatère dont les sommets sont ABCD, ses diagonales sont AC et BD.
Un repère possible pour cette image est le repère
(A,
−→AB∥∥∥−→AB
∥∥∥ ,−−→AD∥∥∥−−→AD
∥∥∥). La �gure 7.4 illustre ce repère. Le
problème consiste à trouver la correspondance entre :
� le point d'intersection P entre le rayon et la facette� le pixel de coordonnées (x, y) de l'image qui lui est associé
Cette image a pour dimension (X, Y ). Cette correspondance est traduite par les expressions suivantes :
x =
−→AP ·
−−→AB
X∥∥∥−−→AB∥∥∥2
y =−→AP ·
−−→AD
Y∥∥∥−−→AD∥∥∥2
(7.1)
2)Le second problème consiste à construire une surface qui re�ète une partie des rayons comme dansl'image 7.6. La �gure 7.5 montre le rayon ré�échi. On considère que le rayon incident est dé�ni par une
18
Fig. 7.4 � Repère intuitif pour une facette en forme de quadrilatère.
origine O et un vecteur directeur −→v , le point d'intersection est P et la normale à la surface au point P
est le vecteur−→N . Alors le rayon ré�échi a pour origine le point P et pour vecteur directeur
−→v′ dé�ni par :
−→v′ = −→v − (2−→v · −→n )−→n (7.2)
Fig. 7.5 � Rayon ré�échi, N est le vecteur normal, r est le rayon incident, r′ est le rayon ré�échi construità l'aide de l'expression (7.2). Les vecteurs r et r′ sont symétriques par rapport à la droite portée par n.
Le programme permettant de construire des images de synthèse contenant des sphères etdes facettes est réparti sur cinq �chiers. Le premier décrit les objets de base tels que lesvecteurs, les couleurs, les objets, les sources de lumière, les rayons. Les autres �chiers seconcentrent sur une classe en particulier, deux contiennent des objets image_synthese_sphere.py etimage_synthese_facette.py. Les deux derniers implémentent chacun un modèle d'illumination di�é-rent image_synthese_scene.py et image_synthese_phong.py. Ils sont plus amplement détaillés dansle document http ://perso.wanadoo.fr/x.dupre/programmation/python_cours_exemple.pdf.
Fichier : image_synthese_base.py
1 # -*- coding: cp1252 -*-
2 """définition des objets permettant de construire une image de synthèse"""
3 import math
4 import copy
5
6 class vecteur (object) :
7 """définit ce qu'est un point"""
8 __slots__ = "x","y","z"
9
10 def __str__ (self):
19
Fig. 7.6 � Portrait de Bette Davis partiellement caché par l'ombre d'une sphère et re�été par la plusgrande des sphères.
11 """pour l'affichage"""
12 return "(%3.2f,%3.2f,%3.2f)" % (self.x, self.y, self.z)
13
14 def __init__(self,x,y,z):
15 """initialisation"""
16 self.x, self.y, self.z = float (x), float (y), float (z)
17
18 def __add__ (self,p):
19 """addition de deux points"""
20 return vecteur (self.x + p.x, self.y + p.y, self.z + p.z)
21
22 def __neg__ (self):
23 """retourne l'opposé d'un vecteur"""
24 return vecteur (-self.x,-self.y,-self.z)
25
26 def __iadd__ (self,p):
27 """addition de deux points"""
28 self.x += p.x
29 self.y += p.y
30 self.z += p.z
31 return self
32
33 def __sub__ (self,p):
34 """soustraction de deux points"""
35 return vecteur (self.x - p.x, self.y - p.y, self.z - p.z)
36
37 def __isub__ (self,p):
38 """soustraction de deux points"""
39 self.x -= p.x
40 self.y -= p.y
41 self.z -= p.z
42 return self
20
43
44 def __mul__ (self,x):
45 """multiplication par un scalaire"""
46 return vecteur (self.x * x, self.y * x, self.z * x)
47
48 def __imul__ (self,x):
49 """multiplication par un scalaire"""
50 self.x *= x
51 self.y *= x
52 self.z *= x
53 return self
54
55 def __div__ (self,x):
56 """division par un scalaire"""
57 return vecteur (self.x / x, self.y / x, self.z / x)
58
59 def __idiv__ (self,x):
60 """division par un scalaire"""
61 self.x /= x
62 self.y /= x
63 self.z /= x
64 return self
65
66 def norme2 (self) :
67 """retourne la norme du vecteur au carrée"""
68 return self.x * self.x + self.y * self.y + self.z * self.z
69
70 def scalaire (self, v) :
71 """calcule le produit scalaire entre self et v"""
72 return self.x * v.x + self.y * v.y + self.z * v.z
73
74 def vectoriel (self, v) :
75 """calcule le produit vectoriel entre self et v"""
76 res = vecteur (0,0,0)
77 res.x = self.y * v.z - self.z * v.y
78 res.y = self.z * v.x - self.x * v.z
79 res.z = self.x * v.y - self.y * v.x
80 return res
81
82 def norme (self) :
83 """retourne la norme du vecteur"""
84 return math.sqrt (self.norme2 ())
85
86 def renorme (self) :
87 """renorme ce vecteur"""
88 n = self.norme ()
89 if n > 0 : return self / n
90 else : return copy.copy (self)
91
92 def cosinus (self, v) :
21
93 """retourne le cosinus de entre le vecteur self et le vecteur r"""
94 sc = self.scalaire (v)
95 n1 = self.norme ()
96 n2 = v.norme ()
97 n = n1 * n2
98 if n == 0 : return 0
99 return float (sc) / float (n)
100
101 def sinus (self, v, norm) :
102 """retourne le sinus de entre le vecteur self et le vecteur r,
103 norm est un vecteur normal et de norme 1 permettant d'orienter
104 le plan dans lequel se trouve les deux vecteurs dont il faut mesurer le sinus"""
105 sc = self.vectoriel (v)
106 n1 = self.norme ()
107 n2 = v.norme ()
108 n = n1 * n2
109 if n == 0 : return 0
110 return sc.scalaire (norm) / float (n)
111
112 def angle (self, v, norm) :
113 """retourne l'angle entre les vecteur self et v,
114 retourne un angle compris entre -pi et pi,
115 norm est la direction du vecteur normal au plan des deux vecteurs"""
116 cos = self.cosinus (v)
117 sin = self.sinus (v, norm)
118 angle = math.atan2 (sin, cos)
119 if angle > math.pi : angle -= math.pi * 2
120 return angle
121
122 def diff_abs (self, v):
123 """retourne la somme des valeurs absolues des différentes entre coordonnées"""
124 r = abs (self.x - v.x)
125 r += abs (self.y - v.y)
126 r += abs (self.z - v.z)
127 return r
128
129 def __eq__ (self, v) :
130 """définit l'égalité entre deux vecteurs"""
131 if v == None : return False
132 return self.diff_abs (v) < 1e-10
133
134 def __ne__ (self, v) :
135 """définit l'égalité entre deux vecteurs"""
136 if v == None : return True
137 return self.diff_abs (v) > 1e-10
138
139
140 class couleur (vecteur) :
141 """une couleur est un vecteur dont les coordonnées sont comprises entre 0 et 1,
142 x <--> rouge, y <--> vert, z <--> bleu"""
22
143
144 def __init__ (self, x,y,z) :
145 vecteur.__init__(self, x,y,z)
146 self.borne ()
147
148 def borne (self) :
149 """si une couleur est hors bornes, réajuste la couleur, prend le maximum devient 1,
150 les autres intensités sont ajustées selon ce facteur d'échelle"""
151 if self.x < 0 : self.x = 0
152 if self.y < 0 : self.y = 0
153 if self.z < 0 : self.z = 0
154 m = max (self.x, self.y)
155 m = max (m, self.z)
156 if m > 1 :
157 self.x /= m
158 self.y /= m
159 self.z /= m
160
161 def __add__ (self,p):
162 """addition de deux couleurs"""
163 return couleur (self.x + p.x, self.y + p.y, self.z + p.z)
164
165 def produit_terme (self, v) :
166 """effectue un produit terme à terme"""
167 return couleur (self.x * v.x, self.y * v.y, self.z * v.z)
168
169 def __mul__ (self,x):
170 """multiplication par un scalaire"""
171 return couleur (self.x * x, self.y * x, self.z * x)
172
173
174
175 class repere (object) :
176 """définition d'un repère orthonormé"""
177
178 def __init__ (self, origine = vecteur (0,0,0), \
179 axex = vecteur (1,0,0), \
180 axey = vecteur (0,1,0), \
181 axez = vecteur (0,0,1)) :
182 """initialisation, origine et les trois axes"""
183 self.origine = origine
184 self.x = axex
185 self.y = axey
186 self.z = axez
187
188 def coordonnees (self, v) :
189 """on suppose que les coordonnées de v sont exprimées dans ce repère,
190 calcule les coordonnées de v dans le repère d'origine"""
191 res = copy.copy (self.origine)
192 res.x += v.x * self.x.x + v.y * self.y.x + v.z * self.z.x
23
193 res.y += v.x * self.x.y + v.y * self.y.y + v.z * self.z.y
194 res.z += v.x * self.x.z + v.y * self.y.z + v.z * self.z.z
195 return res
196
197 def __str__ (self):
198 """affichage"""
199 s = "origine : " + str (self.origine) + "\n"
200 s += "axe des x : " + str (self.x) + "\n"
201 s += "axe des y : " + str (self.y) + "\n"
202 s += "axe des z : " + str (self.z) + "\n"
203 return s
204
205 class pixel (object) :
206 """définit ce qu'est un pixel"""
207 __slots__ = "x","y"
208
209 def __init__(self,x,y):
210 """initialisation"""
211 self.x, self.y = int (x), int (y)
212
213 def __str__ (self):
214 """pour l'affichage"""
215 return "(%d, %d)" % (self.x, self.y)
216
217
218
219
220 class rayon (object) :
221 """définit ce qu'est un rayon"""
222 __slots__ = "origine", "direction", "pixel", "couleur"
223
224 def __init__ (self, origine, direction, pixel, couleur):
225 """initialisation"""
226 self.origine, self.direction, self.pixel, self.couleur = \
227 origine, direction, pixel, couleur
228
229 def __str__ (self):
230 """pour l'affichage"""
231 s = "origine : " + str (self.origine)
232 s += " direction : " + str (self.direction)
233 s += " pixel : " + str (self.pixel)
234 s += " couleur : " + str (self.couleur)
235 return s
236
237
238 class objet (object):
239 """définit l'interface pour un objet à dessiner dans une image de synthese"""
240
241 def intersection (self, r) :
242 """retourne le point d'intersection avec le rayon r,
24
243 retourne None s'il n'y pas d'intersection"""
244 return None
245
246 def normale (self, p, rayon) :
247 """retourne la normale au point de coordonnée p, et connaissant le rayon"""
248 return None
249
250 def couleur_point (self, p) :
251 """retourne la couleur au point de coordonnée p"""
252 return None
253
254 def rayon_refracte (self, rayon, p) :
255 """retourne le rayon réfracté au point p de la surface,
256 si aucune, retourne None"""
257 return None
258
259 def rayon_reflechi (self, rayon, p) :
260 """retourne le rayon réfléchi au point p de la surface,
261 si aucune, retourne None"""
262 return None
263
264 def phong_coefficient (self):
265 """retourne un coefficient propre à l'objet pour
266 le modèle d'illumination de Phong"""
267 return float (0)
268
269
270
271 class source (object) :
272 """définition d'une source ponctuelle"""
273 __slots__ = "origine", "couleur"
274
275 def __init__ (self, origine, couleur):
276 """initialisation"""
277 self.origine, self.couleur = origine, couleur
278
279 def __str__ (self) :
280 """affichage"""
281 return "source : " + str (self.origine) + " couleur : " + str (self.couleur)
282
283 if __name__ == "__main__" :
284 v = vecteur (0,1,2)
285 u = vecteur (0,1,2)
286 w = u + v
287 print u,v,w
288 print w * 6
289 p = pixel (5,5)
290 print p
291 c = couleur (1,1,1)
292 print c
25
293 r = rayon (u,w,p,c)
294 print r
295 s = source (v, c)
296 print s
297
Fichier : image_synthese_sphere.py
1 # -*- coding: cp1252 -*-
2 """définition d'une sphère"""
3 import image_synthese_base as base
4 import math
5
6 class sphere (base.objet):
7 """définit une sphère"""
8 __slots__ = "centre", "rayon", "couleur"
9
10 def __init__ (self, centre, rayon, couleur):
11 """initialisation"""
12 self.centre, self.rayon, self.couleur = centre, float (rayon), couleur
13
14 def intersection (self, r) :
15 """retourne le point d'intersection avec le rayon r,
16 retourne None s'il n'y pas d'intersection"""
17 oc = self.centre - r.origine
18 vn = r.direction.norme2 ()
19 s = r.direction.scalaire (oc)
20 delta = s*s - vn * (oc.norme2 () - self.rayon * self.rayon)
21 if delta < 0 : return None
22 delta = math.sqrt (delta)
23 l1 = (s - delta) / vn
24 l2 = (s + delta) / vn
25
26 if 0 < l1 < l2 : l = l1
27 elif l1 < 0 < l2 : l = l2
28 elif 0 < l2 < l1 : l = l2
29 elif l2 < 0 < l1 : l = l1
30 else : l = None
31
32 if l == None : return None
33
34 v = r.origine + r.direction * l
35 return v
36
37 def normale (self, p, rayon) :
38 """retourne la normale au point de coordonnée p"""
39 v = (p - self.centre) / self.rayon
40 return v
41
42 def couleur_point (self, p) :
26
43 """retourne la couleur au point de coordonnée p"""
44 return self.couleur
45
46 def __str__ (self):
47 """affichage"""
48 s = "sphère --- centre : " + str (self.centre)
49 s += " rayon : " + str (self.rayon)
50 s += " couleur : " + str (self.couleur)
51 return s
52
53
54
55 if __name__ == "__main__" :
56 s = sphere (base.vecteur (0,0,0), 5, base.couleur (0,1,0))
57 r = base.rayon ( base.vecteur (10,0,0), base.vecteur (1,0,0), \
58 base.pixel (0,0), base.couleur (0,0,0))
59 print s
60 print r
61 p = s.intersection (r)
62 print p
63
64
Fichier : image_synthese_scene.py
1 # -*- coding: cp1252 -*-
2 """définition d'une scène"""
3 import image_synthese_base as base
4 import image_synthese_sphere as obj
5 import math
6 import pygame
7
8 class scene (object):
9 """définit une scène, les axes x,y sont ceux de l'écran,
10 z-1 est la distance à l'écran du point (x,y,z)"""
11
12 def __init__ (self, repere, alpha, x,y) :
13 """définit la position de l'oeil, l'angle d'ouverture,
14 et la taille de l'écran"""
15 self.repere = repere
16 self.alpha = float (alpha)
17 self.dim = (int (x), int (y))
18
19 def ajoute_source (self, source):
20 """ajoute une source ponctuelle de lumière"""
21 if not self.__dict__.has_key ("sources") : self.sources = []
22 self.sources.append (source)
23
24 def ajoute_objet (self, objet):
25 """ajoute un objet à la scène"""
27
26 if not self.__dict__.has_key ("objets") : self.objets = []
27 self.objets.append (objet)
28
29 def __str__ (self) :
30 """affichage"""
31 s = "scène ----------------------------\n"
32 s += "repère : " + str (self.repere) + "\n"
33 s += "angle d'ouverture : " + str (self.alpha) + "\n"
34 s += "dimension de l'écran : " + str (self.dim) + "\n"
35 if self.__dict__.has_key ("sources") :
36 for a in self.sources : s += " " +str (a) + "\n"
37 if self.__dict__.has_key ("objets") :
38 for a in self.objets : s += " " + str (a) + "\n"
39 return s
40
41 def intersection (self, rayon) :
42 """calcule le point d'intersection entre un rayon et le plus proche des objets,
43 retourne l'objet et le point d'intersection"""
44 if not self.__dict__.has_key ("objets") : return None, None
45 p = rayon.origine
46 sp,so = None, None
47 for o in self.objets :
48 i = o.intersection (rayon)
49 if i == None : continue
50 if rayon.direction.scalaire (i - p) <= 0 : continue
51 if i == rayon.origine : continue
52 if sp == None :
53 sp = i
54 so = o
55 else :
56 v = i - p
57 d = sp - p
58 if v.norme2 () < d.norme2 () :
59 sp = i
60 so = o
61 return so, sp
62
63 def sources_atteintes (self, p) :
64 """retourne la liste des sources atteintes depuis une position p de l'espace,
65 vérifie qu'aucun objet ne fait obstacle"""
66 res = []
67 for s in self.sources:
68 r = base.rayon (s.origine, p - s.origine, base.pixel (0,0), s.couleur)
69 o,i = self.intersection (r)
70 if i == None : continue
71 if (i - p).norme2 () < 1e-10 : # possible problème d'arrondi
72 res.append (s)
73 continue
74 return res
75
28
76 def construit_rayon (self, pixel) :
77 """construit le rayon correspondant au pixel pixel"""
78 x = (pixel.x - self.dim [0] / 2) * math.tan (self.alpha / 2) / min (self.dim)
79 y = (pixel.y - self.dim [1] / 2) * math.tan (self.alpha / 2) / min (self.dim)
80 v = base.vecteur (x,y,1)
81 r = base.rayon (self.repere.origine, self.repere.coordonnees (v), \
82 pixel, base.couleur (1,1,1))
83 return r
84
85 def modele_illumination (self, rayon, p, obj, source) :
86 """calcule la couleur pour un rayon donné, un point p, un objet obj,
87 et une source de lumière source"""
88 n = obj.normale (p, rayon)
89 cos = n.cosinus (source.origine - p)
90 cl = obj.couleur_point (p) * cos
91 cl = cl.produit_terme (rayon.couleur)
92 return cl
93
94 def couleur_fond (self) :
95 """retourne la couleur du fond"""
96 return base.couleur (0,0,0)
97
98 def rayon_couleur (self, rayon, ref = True) :
99 """retourne la couleur d'un rayon connaissant les objets,
100 cette fonction doit être surchargée pour chaque modèle d'illumination,
101 si ref == True, on tient compte des rayons réfracté et réfléchi"""
102
103 list_rayon = [ rayon ]
104 c = base.couleur (0,0,0)
105 b = False
106 while len (list_rayon) > 0 :
107 r = list_rayon.pop ()
108 o,p = self.intersection (r)
109
110 if p == None : continue
111
112 if ref :
113 t = o.rayon_refracte (r, p)
114 if t != None : list_rayon.append (t)
115 t = o.rayon_reflechi (r, p)
116 if t != None : list_rayon.append (t)
117
118 sources = self.sources_atteintes (p)
119 if len (sources) == 0 : return base.couleur (0,0,0)
120 for s in sources :
121 cl = self.modele_illumination (r, p, o, s)
122 c += cl
123 b = True
124
125 if not b : c = self.couleur_fond ()
29
126 else : c.borne ()
127 return c
128
129 def construit_image (self, screen):
130 """construit l'image de synthèse où screen est un objet du module pygame"""
131 count = 0
132 nbpixel = int (self.dim [0] * self.dim [1] / 100)
133 for y in xrange (0, self.dim [1]) :
134 for x in xrange (0, self.dim [0]) :
135 p = base.pixel (x,y)
136 r = self.construit_rayon (p)
137 c = self.rayon_couleur (r, True)
138 q = (p.x,self.dim [1] - p.y - 1)
139 d = (int (c.x * 255), int (c.y * 255), int (c.z * 255))
140 pygame.draw.line (screen, d, q,q)
141 count += 1
142 if count % 150 == 0 : pygame.display.flip ()
143 if count % nbpixel == 0 : print "avancement " , count // nbpixel , "%"
144 pygame.display.flip ()
145
146
147 def attendre_clic ():
148 """dessine une croix sur l'écran et attend la pression d'un clic de souris"""
149 reste = True
150 while reste:
151 for event in pygame.event.get():
152 if event.type == pygame.MOUSEBUTTONUP :
153 reste = False
154 break
155
156
157 if __name__ == "__main__" :
158 s = scene (base.repere (), math.pi / 1.5, 400, 300)
159 s.ajoute_source ( base.source (base.vecteur (0,10,10), \
160 base.couleur (1,1,1) ) )
161 s.ajoute_source ( base.source (base.vecteur (10,10,5), \
162 base.couleur (0.5,0.5,0.5) ) )
163 s.ajoute_objet ( obj.sphere (base.vecteur (0,0,12), \
164 3, base.couleur (1,0,0) ) )
165 s.ajoute_objet ( obj.sphere (base.vecteur (0,-400,12), \
166 396, base.couleur (0.5,0.5,0.5) ) )
167 print s
168
169 screen = pygame.display.set_mode (s.dim)
170 screen.fill ((255,255,255))
171 s.construit_image (screen)
172
173 print "image terminée"
174 attendre_clic ()
175
30
Fichier : image_synthese_phong.py
1 # -*- coding: cp1252 -*-
2 """implémentation du modèle d'illumination de Phong"""
3 import image_synthese_scene as scene
4 import image_synthese_base as base
5 import image_synthese_sphere as obj
6 import math
7 import pygame
8
9
10 class scene_phong (scene.scene):
11 """définit une scène et utilise le modèle d'illumination de Phong
12 pour construire l'image de synthèse"""
13
14 def __init__ (self, repere, alpha, x,y,
15 ka = 0.1,
16 kb = 0.8,
17 kc = 0.3,
18 reflet = 6,
19 fond = base.couleur (200,200,200)) :
20 """définit la position de l'oeil, l'angle d'ouverture,
21 et la taille de l'écran"""
22 scene.scene.__init__ (self, repere, alpha, x, y)
23 self.ka, self.kb, self.kc = ka,kb,kc
24 self.reflet = reflet
25 self.fond = fond
26 self.constante = float (1)
27
28 def __str__ (self) :
29 """affichage"""
30 s = scene.scene.__str__ (self)
31 s += "ka = %1.3f kb = %1.3f kc = %1.3f\n" % (self.ka,self.kb,self.kc)
32 s += "reflet " + str (self.reflet) + "\n"
33 s += "couleur du fond " + str (self.fond) + "\n"
34 return s
35
36 def couleur_fond (self) :
37 """retourne la couleur du fond"""
38 return self.fond * self.ka
39
40 def modele_illumination (self, rayon, p, obj, source) :
41 """calcule la couleur pour un rayon donné, un point p, un objet obj,
42 et une source de lumière source"""
43 n = obj.normale (p, rayon).renorme ()
44 vr = rayon.direction.renorme ()
45 vr *= float (-1)
46 vs = source.origine - p
47 vs = vs.renorme ()
48 bi = vs + vr
31
49 bi = bi.renorme ()
50
51 # premier terme
52 cos = n.scalaire (vs)
53 couleur = source.couleur.produit_terme (obj.couleur_point (p)) * (cos * self.kb)
54
55 # second terme : reflet
56 cos = n.scalaire (bi) ** self.reflet
57 couleur += source.couleur.produit_terme (source.couleur) * (cos * self.kc)
58 couleur = couleur.produit_terme (rayon.couleur)
59
60 return couleur
61
62
63 if __name__ == "__main__" :
64 s = scene_phong (base.repere (), math.pi / 1.5, 400, 300)
65
66 s.ajoute_source ( base.source (base.vecteur (0,10,10), \
67 base.couleur (1,1,1) ) )
68 s.ajoute_source ( base.source (base.vecteur (10,10,5), \
69 base.couleur (0.5,0.5,0.5) ) )
70 s.ajoute_objet ( obj.sphere (base.vecteur (0,0,12), \
71 3, base.couleur (1,0,0) ) )
72 s.ajoute_objet ( obj.sphere (base.vecteur (0,-400,12), \
73 396, base.couleur (0.5,0.5,0.5) ) )
74 print s
75
76 screen = pygame.display.set_mode (s.dim)
77 screen.fill ((255,255,255))
78 s.construit_image (screen)
79
80 print "image terminée"
81 scene.attendre_clic ()
82
Fichier : image_synthese_facette.py
1 # -*- coding: cp1252 -*-
2 """définition d'une sphère"""
3 import image_synthese_base as base
4 import image_synthese_sphere as obj
5 import image_synthese_phong as scene
6 import image_synthese_scene as scene_p
7 import pygame
8 import math
9
10 class facette (base.objet):
11 """définit un triangle dans l'espace"""
12
13 def __init__ (self, a,b,c, couleur):
32
14 """initialisation"""
15 self.a, self.b, self.c = a,b,c
16 ab = b - a
17 ac = c - a
18 self.vnorm = ab.vectoriel (ac)
19 self.vnorm = self.vnorm.renorme ()
20 self.couleur = couleur
21
22 def intersection_plan (self, r) :
23 """retourne le point d'intersection entre le plan et le rayon r"""
24 if r.direction.scalaire (self.vnorm) == 0 :
25 return None
26 oa = self.a - r.origine
27 l = self.vnorm.scalaire (oa) / self.vnorm.scalaire (r.direction)
28 p = r.origine + r.direction * l
29 return p
30
31 def point_interieur (self, p) :
32 """dit si un point appartient à l'intérieur du triangle"""
33 pa = self.a - p
34 pb = self.b - p
35 pc = self.c - p
36 theta = pa.angle (pb, self.vnorm)
37 theta += pb.angle (pc, self.vnorm)
38 theta += pc.angle (pa, self.vnorm)
39 theta = abs (theta)
40 if theta >= math.pi * 0.9 : return True
41 else : return False
42
43 def intersection (self, r) :
44 """retourne le point d'intersection avec le rayon r,
45 retourne None s'il n'y pas d'intersection"""
46 p = self.intersection_plan (r)
47 if p == None : return None
48 if self.point_interieur (p) : return p
49 else : return None
50
51 def normale (self, p, rayon) :
52 """retourne la normale au point de coordonnée p et connaissant le rayon"""
53 if rayon.direction.scalaire (self.vnorm) < 0 :
54 return self.vnorm
55 else :
56 return - self.vnorm
57
58 def couleur_point (self, p) :
59 """retourne la couleur au point de coordonnée p"""
60 return self.couleur
61
62 def __str__ (self):
63 """affichage"""
33
64 s = "facette --- a : " + str (self.a)
65 s += " b : " + str (self.b)
66 s += " c : " + str (self.c)
67 s += " couleur : " + str (self.couleur)
68 return s
69
70
71 class rectangle (facette):
72 """définit un rectangle dans l'espace"""
73
74 def __init__ (self, a,b,c,d, couleur):
75 """initialisation, si d == None, d est calculé comme étant
76 le symétrique de b par rapport au milieu du segment [ac]"""
77 facette.__init__(self, a,b,c, couleur)
78 if d != None : self.d = d
79 else :
80 i = (a + c) / 2
81 self.d = b + (i-b) * 2
82
83 def point_interieur (self, p) :
84 """dit si un point appartient à l'intérieur du triangle"""
85 pa = self.a - p
86 pb = self.b - p
87 pc = self.c - p
88 pd = self.d - p
89 theta = pa.angle (pb, self.vnorm)
90 theta += pb.angle (pc, self.vnorm)
91 theta += pc.angle (pd, self.vnorm)
92 theta += pd.angle (pa, self.vnorm)
93 theta = abs (theta)
94 if theta >= math.pi * 0.9 : return True
95 else : return False
96
97 def __str__ (self):
98 """affichage"""
99 s = "rectangle --- a : " + str (self.a)
100 s += " b : " + str (self.b)
101 s += " c : " + str (self.c)
102 s += " d : " + str (self.d)
103 s += " couleur : " + str (self.couleur)
104 return s
105
106
107
108
109
110 if __name__ == "__main__" :
111
112 s = scene.scene_phong (base.repere (), math.pi / 1.5, 400, 300)
113
34
114 s.ajoute_source ( base.source (base.vecteur (0,8,8), \
115 base.couleur (0.6,0.6,0.6) ) )
116 s.ajoute_source ( base.source (base.vecteur (10,0,0), \
117 base.couleur (0.6,0.6,0.6) ) )
118 s.ajoute_source ( base.source (base.vecteur (8,8,4.5), \
119 base.couleur (0.6,0.6,0.6) ) )
120 s.ajoute_objet ( obj.sphere (base.vecteur (1,0,5), \
121 1, base.couleur (1,0,0) ) )
122 s.ajoute_objet ( obj.sphere (base.vecteur (0,-400,12), \
123 396, base.couleur (0.5,0.5,0.5) ) )
124 s.ajoute_objet (facette ( base.vecteur (0,-2.5,6), \
125 base.vecteur (-2,-2.5,3), \
126 base.vecteur (1,-3.5,4.5), \
127 base.couleur (0.2,0.8,0)))
128 s.ajoute_objet (rectangle ( base.vecteur (0,-2.5,6), \
129 base.vecteur (-2,-2.5,3), \
130 base.vecteur (-2,2.8,3.5), \
131 None, \
132 base.couleur (0,0,1)))
133 print s
134
135 screen = pygame.display.set_mode (s.dim)
136 screen.fill ((255,255,255))
137 s.construit_image (screen)
138
139 print "image terminée"
140 scene_p.attendre_clic ()
141
142
143
35
8 TD 8 : Enregistrer des �chiers sur une clé USB
(correction page 109)
Lorsqu'on e�ectue une recherche de �chiers, on utilise souvent un �ltre. Par exemple, le �ltre ∗.∗ désignetous les �chiers possibles, ∗.doc désigne tous les �chiers créés par Microsoft Word. L'objectif de ce TD estde recopier un ensemble de �chiers d'un répertoire vers un autre en respectant l'arborescence d'origine.Ces �chiers seront inclus dans un répertoire racine ou un de ses sous-répertoires et leur nom devra véri�erdeux �ltres :
1. Le premier �ltre sélectionne les �chiers à copier.
2. Le second permet d'exclure des �chiers sélectionnés par le premier �ltre.
Ce petit programme pourra être utilisé par la suite pour recopier des �chiers vers une clé USB par exemple.Il regroupe deux tâches indépendantes, la copie de �chiers et l'adéquation entre un nom de �chier et un�ltre. Le schéma proposé est de réaliser ces deux tâches à l'aide d'une classe copie_usb.
class copie_usb (object):
"""recopie des fichiers sur une clé USB"""
def __init__(self,ch1,ch2,accept = ".*",refuse = "") :
"""initialisation,
@param ch1 répertoire source
@param ch2 répertoire destination
@param accept filtre pour les fichiers acceptés pour la copie
@param refuse pour refuser des fichiers parmi ceux déjà acceptés"""
def accepter (self, fichier) :
"""dit si un fichier est accepté à la copie ou non,
retourne un booléen"""
def liste_fichier_repertoire (self,repertoire):
"""récupération de la liste des répertoires et celle des fichiers,
inclus dans le répertoire repertoire"""
def copie (self) :
"""effectue la copie"""
# première étape
# récupération de la liste des répertoires et fichiers
# seconde étape
# élimination des importuns
# troisième étape
# on créé les répertoires s'ils n'existent pas
# quatrième étape
# on recopie les fichiers
36
# petit exemple d'utilisation
c = copie_usb (ch1, ch2, filtre_accept, filtre_refuse)
c.copie ()
1)La première étape est d'écrire le code concernant le constructeur __init__ de la classe copie_usb.Il s'agit d'initialiser les paramètres de la classe qui sont aussi ceux du constructeur.
2)Cette seconde question se concentre sur l'adéquation entre un nom de �chier et un �ltre, c'est-à-direl'implémentation de la méthode liste_fichier_repertoire. Pour ce faire, on utilise le module re quitraite les expressions régulières.
Une expression régulière est une sorte de schéma de construction pour les chaînes de caractères. Parexemple, le format .∗ désigne tous les chaînes de caractères. Le format [̂a].∗ désigne toutes les chaînesde caractères commençant par la lettre a minuscule. L'ensemble de ces règles est décrit à l'adressehttp ://docs.python.org/lib/re-syntax.html. Le tableau qui suit regroupe les expressions nécessaires à laréalisation de ce TD.
. ∗ [.].∗Cette expression régulière correspond à tous les noms de �chiers ayantune extension, c'est-à-dire au moins un point inclus dans le nom du�chier.
. ∗ [.]pdf$|. ∗ [.]html$Cette expression régulière correspond à tous les noms de �chiers ayantune extension pdf ou html. Le "ou" est traduit par le symbole |, il peuty en avoir plusieurs dans la même expression régulière.
programme\\. ∗ [.]zip$Cette expression régulière correspond à tous les noms de �chiers ayantune extension zif et inclus dans un répertoire programme\ ou un de sessous-répertoires.
Le module re traite les expressions régulières. Parmi les fonctions proposées par ce module, deux serontutilisées.
Fonctions utiles :
re.compile(str, flag = 0)
Construit une expression régulière à partir d'une chaîne decaractères str. Si flag = re.IGNORECASE, l'expression régu-lière ne fait pas la distinction entre les minuscules et les ma-juscules.
re.match(ex, str)Retourne une expression régulière si la chaîne de caractèresstr est en adéquation avec l'expression régulière ex, et Nonedans les cas contraire.
Petit exemple de code :
import re
t = re.compile (".*[.]htm$", re.IGNORECASE)
if re.match (t, "inDex.htm") : print True
else : print False
if re.match (t, "inDex.html") : print True
else : print False
Le programme a�che True puis False. Le résultat de la fonction match est une expression régulière s'il ya adéquation ou un résultat vide s'il n'y a pas adéquation comme le montre l'exemple suivant.
37
print re.match (t, "inDex.htm") # affiche <_sre.SRE_Match object at 0x008712C0>
print re.match (t, "inDex.html") # affiche None
3)La troisième partie du TD concerne la récupération des �chiers et des répertoires inclus dans un ré-pertoire appelé racine qui se conclut par l'implémentation des fonctions liste_fichier_repertoire etcopie de la classe copie_usb. Tout d'abord, le plus simple, la copie d'un �chier est réalisée au moyen dela fonction copy du module shutil.
Fonctions utiles :
shutil.copy(source, destination)Copie le �chier source, ses nouveauxnom et emplacement sont donnés pardestination.
Ensuite, il existe une fonction listdir du module os qui permet d'obtenir la liste des �chiers et sous-répertoires inclus dans un répertoire. Ce même module propose une fonction mkdir qui permet de créerun répertoire.
Fonctions utiles :
os.listdir(rep)
Retourne la liste des �chiers et sous-répertoires inclus dansle répertoire rep. Les noms retournés sont relatifs au réper-toire rep. Le nom complet d'un �chier f inclus dans la listeretournée est donc rep + ”\\” + f.
os.mkdir(rep)Crée le répertoire rep, si les répertoires intermédiairesn'existent pas, cette fonction génère une exception.
os.makedirs(rep)Crée le répertoire rep, si les répertoires intermédiairesn'existent pas, cette fonction les crée également.
En�n, le module os.path propose entre autres trois fonctions qui permettent de savoir si un �chier ou unrépertoire existe, et si un nom correspond à un �chier ou à un répertoire.
Fonctions utiles :os.path.exists(nom) Retourne True si le répertoire ou le �chier nom existe.
os.path.isfile(nom) Retourne True si nom correspond à un nom de �chier.
os.path.isdir(nom) Retourne True si nom correspond à un nom de répertoire.
Travail à faire :
La liste des �chiers sélectionnés ne contient pas forcément tous les �chiers inclut dans un répertoire et sessous-répertoires. Il est probable que la classe copie_usb crée alors des répertoires sur la clé USB qui necontiennent aucun �chier. Comment faire pour éviter que la méthode copie ne crée ces répertoires vides ?
38
9 TD 9 : Enregistrer des �chiers sur une clé USB, utilisation d'une
interface fenêtrée
(correction page 112)
L'objectif de ce TD est de reprendre le programme du TD 8 et de lui adjoindre une fenêtre graphique pourle rendre plus facilement utilisable comme celle de la �gure 9.7.
Fig. 9.7 � Exemple de fenêtre demandée pour le TD 9. Elle permet de modier les répertoires source etdestination, les deux �ltres, dé�nis au TD 8, puis de lancer la copie.
1) Il s'agit dans cette première question de dessiner la fenêtre graphique. Trois types d'objet issus dumodule Tkinter ou widgets interviennent :
LabelCet objet permet d'a�cher du texte, des légendes, permettant d'indiquerce qu'il faut saisir dans les objets de saisie voisins.
EntryCet objet permet de saisir du texte, un nom de répertoire, ou un �ltrepar exemple.
ButtonInsère un bouton dans une fenêtre graphique. Relié à une fonction, lapression de ce bouton exécute cette fonction.
L'exemple de code suivant permet de créer un objet pour chacun de ces types et de les placer en diagonale.Cet exemple permet d'obtenir la fenêtre de la �gure 9.8. Ces objets doivent être précédés du pré�xeTkinter ou Tk dans l'exemple qui suit car ils appartiennent au module Tkinter.
import Tkinter as Tk # import du module Tkinter
root = Tk.Tk () # création de la fenêtre principale,
# c'est toujours la première ligne
b = Tk.Button (text = "bouton") # création d'un bouton
e = Tk.Entry () # création d'une zone de saisie
l = Tk.Label (text = "légende") # création d'une légende
b.grid (row = 0, column = 0) # positionnement de b dans la case (0,0)
e.grid (row = 1, column = 1) # positionnement de e dans la case (1,1)
l.grid (row = 2, column = 2) # positionnement de e dans la case (2,2)
root.mainloop () # on lance le programme et l'affichage de la fenêtre
39
Fig. 9.8 � Fenêtre simple comprenant une instance des objets Button, Entry et Label.
Il est possible d'allonger la taille d'un objet Button, Label, ou Entry. Il su�t d'ajouter quelqueslignes entre la création des objets et le lancement de la fenêtre par l'intermédiaire de l'instructionroot.mainloop(). Le résultat est celui de la �gure 9.9.
Fig. 9.9 � Même fenêtre que celle de la �gure 9.8, les dimensions des objets sont changé.
import Tkinter as Tk # import du module Tkinter
root = Tk.Tk () # création de la fenêtre principale,
# c'est toujours la première ligne
b = Tk.Button (text = "bouton") # création d'un bouton
e = Tk.Entry () # création d'une zone de saisie
l = Tk.Label (text = "légende") # création d'une légende
b.grid (row = 0, column = 0) # positionnement de b dans la case (0,0)
e.grid (row = 1, column = 1) # positionnement de e dans la case (1,1)
l.grid (row = 2, column = 2) # positionnement de e dans la case (2,2)
# spécifications
b.config (width = 30, height = 4) # largeur de 30, hauteur de 4
e.config (width = 50, font = "arial") # largeur de 50, police arial
l.config (width = 30, height = 6) # largeur de 30, hauteur de 6
root.mainloop () # on lance le programme et l'affichage de la fenêtre
On désire maintenant insérer du texte dans la zone de saisie. On utilise pour cela la méthode insert. Onobtient la �gure 9.10.
import Tkinter as Tk # import du module Tkinter
root = Tk.Tk () # création de la fenêtre principale,
# c'est toujours la première ligne
40
Fig. 9.10 � On reprend le modèle de la �gure 9.8, la zone de saisie contient maintenant du texte.
b = Tk.Button (text = "bouton") # création d'un bouton
e = Tk.Entry () # création d'une zone de saisie
l = Tk.Label (text = "légende") # création d'une légende
b.grid (row = 0, column = 0) # positionnement de b dans la case (0,0)
e.grid (row = 1, column = 1) # positionnement de e dans la case (1,1)
l.grid (row = 2, column = 2) # positionnement de e dans la case (2,2)
e.insert (0, "texte par défaut") # on insère une chaîne de caractères dans la zone de saisie
root.mainloop () # on lance le programme et l'affichage de la fenêtre
Ces trois exemples permettent de dessiner une fenêtre graphique semblable à celle de la �gure 9.7 quicontient quatre zones de saisie (Entry) et quatre zones de textes (Label). Elle contient aussi quatreboutons (Button). Dans un premier temps, on se contentera des boutons intitulés Fermer et Copier. Lesdeux autres seront utilisés dans la dernière partie de cet énoncé. Pour réaliser ce programme, on peut parexemple créer une nouvelle classe qui héritera de celle créée lors du TD 8.
class copie_usb_window (copie_usb.copie_usb):
def fenetre (self) :
# ici, création de la fenêtre graphique
# ...
Pour a�cher la fenêtre graphique et lancer la copie, on utilise une liste d'instructions semblable à celleutilisé dans le TD 8.
# programme principal
ch1 = "C:\\Documents and Settings\\Dupré\\" \
"Mes documents\\informatique\\support\\python_td"
ch2 = "c:\\temp\\copie_usb"
filtre_accept = ".*[.].*"
filtre_refuse = ".*[.]pdf$|.*[.]html$|.*[.]bmp|programme\\\\.*[.]zip$"
c = copie_usb_window (ch1, ch2, filtre_accept, filtre_refuse)
c.fenetre () # affiche la fenêtre graphique
2) Il faut maintenant faire en sorte que la pression d'un bouton entraîne à une action. On reprend lepremier exemple et on a�ecte au bouton b une fonction qui écrire une chaîne de caractères. Ceci mène auprogramme suivant :
41
import Tkinter as Tk # import du module Tkinter
root = Tk.Tk () # création de la fenêtre principale,
# c'est toujours la première ligne
b = Tk.Button (text = "bouton") # création d'un bouton
e = Tk.Entry () # création d'une zone de saisie
l = Tk.Label (text = "légende") # création d'une légende
b.grid (row = 0, column = 0) # positionnement de b dans la case (0,0)
e.grid (row = 1, column = 1) # positionnement de e dans la case (1,1)
l.grid (row = 2, column = 2) # positionnement de e dans la case (2,2)
# fonction à exécuter si le bouton b est pressé
def affichage_bouton ():
print "chaîne affichée si le bouton est pressé"
# on affecte la fonction affichage_bouton au bouton b
b.config (command = affichage_bouton)
root.mainloop () # on lance le programme et l'affichage de la fenêtre
On peut aussi vouloir que la fenêtre se ferme si le bouton b est pressé. Dans ce cas, on remplace l'avantdernière ligne par la ligne suivante :
b.config (command = root.destroy)
Lors de la pression du bouton b, la fenêtre disparaît et le programme se termine. Il reste à savoir commentmanipuler une ligne de saisie (classe Entry). Pour cet exercice, les trois méthodes suivantes seront utiles.
Fonctions utiles :get() Permet d'obtenir le contenu d'une zone de saisie.
delete(i, j)Détruit les caractères de la zone de saisie compris entre i etj exclu.
insert(i, s) Insère dans la zone de saisie le texte s à la position i.
On peut par exemple utiliser ces trois méthodes pour récupérer le contenu d'une zone de saisie, le mettreen majuscules, puis modi�er le contenu de la zone de saisie. Dans l'exemple qui suit, on suppose que lavariable e désigne une zone de saisie.
s = e.get () # on récupère le contenu de la zone de saisie
i = len (s) # i est égal à la longueur de la chaîne s
e.delete (0, i) # on vide la zone de saisie
s = s.upper () # mise en majuscules
e.insert (0,s) # on remplace le contenu de la zone de saisie
Il ne reste plus qu'à programmer les fonctions qui seront actionnées par la pression des boutons de lafenêtre graphique décrite dans la première question.
42
Travail à faire :
L'interface fenêtrée impose que les répertoires source et destination soient saisis à la main. L'interface dela �gure 9.7 propose aussi que ces répertoires puissent être aussi saisis à l'aide d'une boîte de dialogue. Ilsu�t d'ajouter deux autresboutons (Button) intitulés Chercher, ils font appel à une fonction qui utilisele code suivant :
import selection_file
fs = selection_file.FileSelection (titre, "c:\\temp", file = False)
r = fs.run ()
print r # chaîne de caractères ou None
Ce code crée une seconde boîte de dialogue (celle de la �gure 9.11) qui permet de sélectionnerun répertoire à l'aide de la souris sans avoir à le saisir au clavier. La méthode run de la classeselection_file.FileSelection retourne la valeur None si le bouton Annuler a été pressé et un réper-toire si le bouton Ok a été pressé. Cette boîte de dialogue est dé�nie dans le �chier selection_file.py.
Fig. 9.11 � Boîte de dialogue implémentée dans le �chier selection_file.py et permettant de sélec-tionner un répertoire ou un �chier. Les noms de répertoires sont précédés du symbole +.
Fichier selection_file.py
1 # -*- coding: cp1252 -*-
2 """module contenant une boîte de dialogue permettant
3 de sélectionner un fichier ou un répertoire,
4 il utilise l'interface Tkinter"""
5 import Tkinter as Tk
6 import os.path
7 import os
8
9 class FileSelection (object) :
10 """classe permettant de sélectionner un fichier
11 ou un répertoire à travers une boîte de dialogue"""
12
13 def __init__ (self, titre = "Sélection de fichier", \
14 chemin = None, file = True, exist= True) :
43
15 """initialise la classe
16 @param titre titre de la fenêtre
17 @param chemin fichier ou répertoire par défaut
18 @param file True : fichier, False : répertoire
19 @param exist True : le répertoire ou le fichier
20 sélectionné doit exister"""
21 self.titre = titre
22 self.chemin = chemin
23 self.file = file
24 self.exist = exist
25
26 if self.chemin == None : self.chemin = os.getcwd ()
27
28 def get_list (self) :
29 """retourne la liste des fichiers et des répertoires (2 listes),
30 répertoires seulement et [] si self.file == False"""
31 if os.path.isdir (self.chemin) :
32 list = os.listdir (self.chemin)
33 else :
34 ch,fi = os.path.split (self.chemin)
35 list = os.listdir (ch)
36
37 lifile = []
38 lidir = []
39 for l in list :
40 if os.path.isdir (self.chemin + "\\" + l) :
41 lidir.append (l)
42 elif self.file :
43 lifile.append (l)
44
45 lidir.sort ()
46 lifile.sort ()
47 return lidir, lifile
48
49 def run (self) :
50 """lance la boîte de dialogue et retourne la chaîne sélectionnée"""
51 top = Tk.Toplevel ()
52 top.wm_title (self.titre)
53
54 fli = Tk.Frame (top)
55 scrollbar = Tk.Scrollbar (fli)
56 li = Tk.Listbox (fli, width = 120, height = 15, \
57 yscrollcommand = scrollbar.set)
58 scrollbar.config (command = li.yview)
59 ch = Tk.Entry (top, width = 120)
60 f = Tk.Frame (top)
61 prec = Tk.Button (f, text = "Précédent")
62 suiv = Tk.Button (f, text = "Entre")
63 annul = Tk.Button (f, text = "Annuler")
64 ok = Tk.Button (f, text = "Ok")
44
65
66 prec.grid (column = 0, row = 0)
67 suiv.grid (column = 1, row = 0)
68 annul.grid (column = 3, row = 0)
69 ok.grid (column = 4, row = 0)
70 li.pack (side = Tk.LEFT)
71 scrollbar.pack(side = Tk.RIGHT, fill = Tk.Y)
72 fli.pack ()
73 ch.pack ()
74 f.pack ()
75
76 def update_chemin () :
77 """mise à jour du chemin dans la boîte de dialogue"""
78 s = ch.get ()
79 ch.delete (0, len (s))
80 ch.insert (0, self.chemin)
81
82 def update_list () :
83 """mise à jour de la liste des fichiers et répertoires
84 à partir de la chaîne dans la boîte de dialogue"""
85 self.chemin = ch.get ()
86 lidir, lifile = self.get_list ()
87 li.delete (0, Tk.END)
88 if len (lidir) > 0 :
89 for l in lidir : li.insert (Tk.END, "+ "+ l)
90 if len (lifile) > 0 :
91 for l in lifile : li.insert (Tk.END, " "+ l)
92
93 def precedent () :
94 """passe au répertoire précédent"""
95 if os.path.isdir (self.chemin) :
96 ch, last = os.path.split (self.chemin)
97 self.chemin = ch
98 else :
99 ch, last = os.path.split (self.chemin)
100 ch, last = os.path.split (ch)
101 self.chemin = ch
102 update_chemin ()
103 update_list ()
104
105 def suivant () :
106 """rentre dans un répertoire"""
107 sel = ch.get ()
108 if os.path.isdir (sel) :
109 self.chemin = sel
110 update_chemin ()
111 update_list ()
112
113 def update_sel () :
114 """mise à jour de la chaîne de caractères
45
115 dans la boîte de dialogue à partir de la ligne
116 sélectionnée dans la liste"""
117 li.after (200, update_sel)
118 sel = li.curselection ()
119 if len (sel) == 1 :
120 t = li.get (sel [0])
121 c = self.chemin + "\\" + t [2:len (t)]
122 s = ch.get ()
123 ch.delete (0, len (s))
124 ch.insert (0, c)
125
126 def annuler () :
127 """annule la recherche"""
128 self.resultat = False
129 top.destroy ()
130 top.quit ()
131
132 def accepter () :
133 """accepte le résultat"""
134 self.resultat = True
135 self.chemin = ch.get ()
136 top.destroy ()
137 top.quit ()
138
139 prec.config (command = precedent)
140 suiv.config (command = suivant)
141 annul.config (command = annuler)
142 ok.config (command = accepter)
143
144 update_chemin ()
145 update_list ()
146 update_sel ()
147 ch.focus_set ()
148 top.mainloop ()
149
150 if self.resultat : return self.chemin
151 else : return None
152
153
154 if __name__ == "__main__" :
155 root = Tk.Tk ()
156
157 def run () :
158 r = FileSelection ("sélection d'un fichier", "c:\\")
159 s = r.run ()
160 print "fichier sélectionné ", s
161
162 Tk.Button (text = "fenêtre", command = run).pack ()
163 Tk.Button (text = "fermer", command = root.destroy).pack ()
164 root.mainloop ()
46
165
47
10 TD 10 : Enregistrer des �chiers sur une clé USB, utilisation d'une
interface fenêtrée, enregistrement des paramètres
(correction page 115)
L'objectif de ce TD est de reprendre le programme du TD 9 et d'enregister les paramètres utilisés lors dela dernière sauvegarde a�n de les retrouver lors de la prochaine utilisation. Comme pour le TD 9, l'idéeest de reprendre la classe copie_usb_window, de la dériver en une classe qui permet de lire et d'écrireles paramètres utilisés pour la copie de �chiers vers une clé USB.
1)La première tâche est d'écrire une méthode qui écrit dans un �chier texte les quatre paramètres dela classe qui sont les deux répertoires source et destination, les deux �ltres utilisés pour sélectionner les�chiers à copier. On pourra s'inspirer du petit programme suivant.
# ouverture fichier essai.txt en mode écriture
f = open ("essai.txt", "w")
# écriture d'une chaîne de caractères dans le fichier
f.write ("première ligne")
# passage à la ligne
f.write ("\n")
# fermeture du fichier
f.close ()
2)La seconde tâche est d'écrire une méthode qui lit dans un �chier texte les quatre paramètres de laclasse écrit par la méthode implémentée lors de la question précédente. On pourra aussi s'inspirer du petitprogramme suivant.
# ouverture fichier essai.txt en mode lecture
f = open ("essai.txt", "r")
# lecture de la première ligne du fichier
s = f.readline ()
# on enlève de la chaîne de caractères s le symbole de fin de ligne
s = s.replace ("\n", "")
# affichage de s
print s
# fermeture du fichier
f.close ()
3)On peut maintenant surcharger la méthode fenetre de la classe copie_usb_window dé�nie au TD 9de sorte qu'elle lise ses paramètres dans un �chier et qu'elle les écrive une fois la copie terminée.
48
11 TD 11 : Lecture d'un �chier XML, copie de �chiers
(correction page 117)
Ce TD s'adresse plus particulièrement à ceux qui utilise le logiciel Winamp4 qui permet d'écouter desmorceaux musicaux de tout format sur ordinateur. Ce logiciel comme beaucoup d'autres o�re la possibilitéde construire une sélection de morceaux et de l'enregistrer sur disque au format XML comme par exemplele �chier qui suit et qui regroupe trois chansons.
1 <?xml version="1.0" encoding='UTF-8' standalone="yes"?>
2 <WinampXML>
3 <!-- Generated by: Nullsoft Winamp3 rc2 1GdGi -->
4 <playlist num_entries="190" label="New playlist">
5 <entry Playstring="file:C:\x_Musique\Rock\_melting pot\Bruce Springsteen 04 - Track 04.mp3">
6 <Name>Bruce Springsteen - Track 04</Name>
7 <Length>168446</Length>
8 </entry>
9 <entry Playstring="file:C:\x_Musique\Rock\_melting pot\Pulp Fiction - 07_Track 07.mp3">
10 <Name>Pulp Fiction - Track 07</Name>
11 <Length>297019</Length>
12 </entry>
13 <entry Playstring="file:C:\x_Musique\Rock\Robbie Williams\Escapology\Robbie Williams - Track 09.mp3">
14 <Name>Robbie Williams - Track 09</Name>
15 <Length>278499</Length>
16 </entry>
17 </playlist>
18 </WinampXML>
Ces �chiers sont souvent disséminés à divers endroits du disque dur et il est fastidieux de les copier unpar un pour regrouper tous ces morceaux dans un seul répertoire a�n de fabriquer une compilation. CeTD se propose de décrypter le �chier XML présenté ci-dessus, d'extraire tous les noms de �chiers et de lesrecopier dans un répertoire.
Le langage XML est un langage à balises comme le langage HTML. Il permet de décrire n'importe quelleinformation pour peu que le sens des balises ait été préalablement dé�ni. Le principe consiste à insérerchaque information entre deux balises portant le même nom < nom_balise > et < /nom_balise >. Sicette information est elle-même complexe, il est possible de la décrire elle-aussi à l'aide de balises. Parexemple, pour le �chier précédent, une chanson est dé�nie par trois attributs :
1. un nom de �chier Playstring
2. un nom à a�cher à l'écran Name
3. une durée Length
Les balises < entry > et < /entry > délimitent ce qu'est une chanson qu'on pourrait résumer par lasyntaxe XML suivante :
<entry>
<Playstring> file:C:\x_Musique\Rock\_melting pot\Pulp Fiction - 7_Track 7.mp3 </Playstring>
<Name>Pulp Fiction - Track 7</Name>
<Length>297019</Length>
</entry>
4http ://www.winamp.com
49
Parfois certaines informations simples comme un nom de �chier peuvent être non plus insérées entre deuxbalises mais a�ectés comme attributs à une certaine balise. C'est le cas ici pour l'attribut Playstring.
<entry Playstring="file:C:\x_Musique\Rock\_melting pot\Pulp Fiction - 7_Track 7.mp3">
<Name>Pulp Fiction - Track 7</Name>
<Length>297019</Length>
</entry>
C'est la même information mais représentée de manière di�érente. Ce choix dépend du logiciel qui utilisele �chier XML. Toutefois, l'avantage d'un tel langage est qu'il peut être édité et modi�é facilement. Onpourrait encore écrire cet petit exemple sous la forme :
<entry Playstring="file:C:\x_Musique\Rock\_melting pot\Pulp Fiction - 7_Track 7.mp3"
Name="Pulp Fiction - Track 7"
Length="297019">
</entry>
Il est possible de supprimer aussi la balise de �n < /entry > puisque elle et sa balise jumelle n'encadrentrien.
<entry Playstring="file:C:\x_Musique\Rock\_melting pot\Pulp Fiction - 7_Track 7.mp3"
Name="Pulp Fiction - Track 7"
Length="297019"/>
La dernière contrainte du langage est que toutes les balises doivent être entourées de deux premièresbalises, par exemple < WinampXML > et < /WinampXML >. On représente souvent un tel �chier sous formede graphe (voir �gure 11.12).
L'objectif de ce TD est de concevoir un programme qui permette d'obtenir la liste de tous les morceauxmusicaux inclus dans le �chier XML et de les recopier dans un autre répertoire.
1)On cherche tout d'abord à récupérer la liste des �chiers musicaux. Cela revient à parcourir le �chierXML et à insérer dans une liste le contenu de l'attribut Playstring de la balise entry. Il existe déjà unmodule qui permet de lire un �chier XML, le module xml.sax. Toutefois, son fonctionnement di�ère de lalecture d'un �chier de texte normal. Ce n'est plus le programmeur qui gère la lecture mais il délègue cettetâche à une classe qui appelle les fonctions de l'utilisateur lorsqu'elle rencontre une balise.
L'idée est de dé�nir ce que doit faire le programme lorsqu'il lit un �chier XML, quelles instructions ildoit exécuter lorsque des événements se présentent durant cette lecture. A chaque événement correspondune méthode de la classe xml.sax.ContentHandler. Il su�t de créer une classe dérivée pour modi�erle comportement du programme lorsqu'un événement survient lors de la lecture du �chier XML. Cesévénements sont :
1. Le début de la lecture (méthode startDocument).
2. La �n de la lecture (méthode endDocument).
3. La rencontre d'une balise ouvrante (méthode startElement).
4. La rencontre d'une balise fermante (méthode endElement).
5. La lecture d'un texte compris entre une balise ouvrante et une balise fermante (méthode characters)
50
Fig. 11.12 � Transcription sous forme de graphe d'une partie du �chier XML présenté en exemple parl'énoncé du TD 11. Les cadres grisés représentent les balises, les cadres dont le fond est rayé représententles attributs, le contenu des cadres dont le fond est blanc est inséré entre deux balises.
class XML_comportement (xml.sax.ContentHandler) :
def startDocument (self) :
"""méthode appelée lorsque le document XML est ouvert"""
def endDocument (self) :
"""méthode appelée lorsque le document XML est fermé"""
def startElement (self, ba, attr) :
"""méthode appelée chaque fois qu'une nouvelle balise
est rencontrée, le nom de la balise est ba, les attributs
associées sont stockées dans attr (dictionnaire)"""
def endElement (self, ba) :
"""méthode appelée lorsqu'une balise de fin est rencontrée"""
def characters (self,data) :
"""méthode appelée entre une balise et sa balise de fin associée"""
Par exemple, pour le petit exemple qui suit :
<entry Playstring="fichier_exemple.mp3">
<Name>Pulp Fiction - Track 7</Name>
51
<Length>297019</Length>
</entry>
On suppose que c est une instance de la classe xml.sax.ContentHandler. Le programme doit appeler laséquence des méthodes suivantes :
1. c.startElement(”entry”, {”Playstring” : ”fichier_exemple.mp3”})2. c.startElement(”Name”, {})3. c.characters(”PulpFiction− Track7”)
4. c.endElement(”Name”)
5. c.startElement(”Length”, {})6. c.characters(”297019”)
7. c.endElement(”Length”)
8. c.characters(”\n”)
9. c.endElement(”entry”)
Il su�t de surcharger les méthodes de la classe xml.sax.ContentHandler pour adapter le programme à vosbesoins. Ensuite, pour lire le �chier XML, on va créer ce qu'on appelle un parseur (ou parser en anglais)et l'informer du comportement qu'il doit suivre lors de la lecture d'un �chier XML.
# création du parseur
p = xml.sax.make_parser ()
# création d'une instance de la classe XML_comportement
x = XML_comportement ()
# on affecte au parseur une instance de la classe XML_comportement
# pour préciser au parseur quelles instructions il doit exécuter
# à chaque événement
p.setContentHandler (x)
Un parseur ne lit pas directement un �chier, il décrypte un chaîne de caractères au format XML qu'ilpeut recevoir en un ou plusieurs morceaux par l'intermédiaire de la méthode feed. On suppose que filescontient le nom d'un �chier texte.
# on lit le fichier file ligne par ligne,
# chaque ligne est envoyée au parser XML
f = open (file, "r")
for l in f : # pour toutes les lignes du fichier f
p.feed (l)
p.close ()
f.close ()
L'objectif de cette première question est de construire une liste incluant tous les noms de morceauxmusicaux du �chier XML.
2)Lorsque la liste des �chiers est récupérée, il ne reste plus qu'à copier chaque �chier de cette liste dansun autre répertoire.
52
Fonctions utiles :
shutil.copy(source, destination)Copie le �chier source, ses nouveaux nom et empla-cement sont donnés par destination.
replace(str, old, new)
A l'intérieur de la chaîne str, remplace toutesles occurrences de la chaîne old par la chaînenew. Pour l'utiliser, il faut ajouter au débutdu programme la ligne import string puis écrirel = string . replace (”dix− neuf”, ”− ”, ” ”), parexemple.
Remarque 11.1: accentIl est possible que certaines erreurs apparaissent parce que certains noms de �chiers contiennent des accents.Pour faire disparaître ces erreurs, il faut convertir les caractères de ce nom de �chier avec l'instructionsuivante :
v.encode ("latin-1") # v est une chaîne de caractères
# obtenue depuis un fichier XML
Travail à faire :
Quelle réponse apporter lorsque deux �chiers à copier porte le même nom bien qu'ils soient dans desrépertoires di�érents ? S'ils gardent ce même nom, dans le répertoire de destination, le premier sera écraséau pro�t du second.
53
12 TD 12 : Recherche de mots-clé dans une page HTML
(correction page 120)
Ce TD a pour but de rechercher une expression dans une page HTML et les pages que la première référence.Ce peut être par exemple pour rechercher tous les articles d'un journal relatifs à un même sujet.
1)La première étape consiste à décliner une version de la classe HTMLParser du module HTMLParsera�n de conserver lors du déchi�rage d'une page HTML le contenu de cette page et les hyperliens qu'ellecontient. Pour lire une page HTML à l'aide d'une classe de type HTMLParser. L'extrait suivant montrecomment se servir d'une telle classe :
p = HTMLParser ()
p.feed (text)
p.close ()
Il su�t ensuite de dériver cette classe HTMLParser pour surcharger les deux méthodes suivantes :
1. handle_starttag est appelée chaque fois qu'une nouvelle balise est lue dans un �chier HTML, enparticulier la balise < a href = ... < /a > qui permet d'insérer un lien hypertexte. Surcharger cetteméthode permet de balayer tous les hyperliens d'une page. Elle reçoit deux paramètres, tag qui estle nom de la balise et attr qui contient une liste de couples (attribut,valeur). La balise recherchéeest a qui contient un attribut href comme celui de l'exemple qui suit :
<a href="bresenham_ligne4.html"> tracé d'une ligne</a>
Les quelques lignes qui suivent sont les premières notes de la méthodes handle_starttag.
def handle_starttag (self, tag,attr) :
print "balise ", tag
for i,j in attr :
print i,j
if i == "href" :
# ...
2. handle_data est appelée chaque fois qu'un texte est inclus entre deux balises, il s'agit du textedans lequel les mots-clés, les expressions, seront cherchés. Le programme concatène chaque chaînede caractères que reçoit cette fonction. La méthode handle_data ne reçoit qu'un paramètre data,une chaîne de caractères dans laquelle il faudra chercher une expression régulière. Quelques notesencore...
def handle_data (self, data) :
d = data.replace ("\n", "")
Encore quelques notes pour la déclaration de la classe et son constructeur. list est une liste d'hyperliensà explorer. Lors de la lecture d'une page HTML, cette liste sera étendue des hyperliens rencontrés. Demême, text contiendra après la lecture tout le contenu d'une page débarrassée de ses balises.
class HTML_explore (HTMLParser.HTMLParser) :
def __init__ (self, list, url, text) :
html_parser_script.HTMLParserScript.__init__(self)
self.list = list
self.url = url
self.text = text
54
Une dernière précision, le module urlparse permet de concaténer un lien absolu - par exemplehttp ://www.lemonde.fr/ - et un hyperlien relatif à cette adresse :
adr = urlparse.urljoin ("http://www.lemonde.fr/", "web/article/")
2) Il faut encore ouvrir une page HTML, charger son contenu, le déchi�er, en extraire des hyperliens etrechercher une expression régulière à l'aide du module re. Tout d'abord, il faut charger le contenu d'unepage comme le montre l'exemple suivant :
try :
f = urllib.urlopen (url)
d = f.read ()
whole = d
except Exception, exc:
print " exception lecture ", exc, "\t -- ", url
error.append (url)
continue
Une fois que la page HTML est chargée, il faut encore la déchi�rer à l'aide de la classe HTML_exploreécrite lors de la première question. Cette classe hérite de la classe HTMLParser qui inclut une méthodefeed. Pour déchi�er la chaîne HTML whole, il faut utiliser le code suivant :
p = HTML_explore (adr, url, text)
p.feed (whole)
p.close ()
La récupération des hyperliens et du contenu d'une page sans ses balises est faite par la classeHTML_explore. Il reste encore à chercher une expression régulière à l'aide de l'exemple suivant (voirégalement le TD 8, page 36) :
s = ".*Bush.*"
ex = re.compile (s, re.IGNORECASE)
if ex.match (contenu) :
# ...
Pour �nir, la partie principale du programme doit ressembler aux lignes qui suivent.
url = "http://www.lemonde.fr/"
# on appelle la fonction process_file pour récupérer les informations
# inscrites dans le fichier XML
s = ".*ukraine.*"
ex = re.compile (s, re.IGNORECASE)
li,error,nb = process_file (url, ex, 3, -10)
Remarque 12.1: version du langage HTMLLa classe HTML_explore peut dériver indi�éremment de la classe HTMLParser du module HTMLParser oude la classe HTMLParserScript du module portant le même nom. Dans le premier cas, ce programme nepourra lire que la version 2.01 du langage HTML. Dans le second cas, le programme sera capable de liredes versions plus récentes sans toutefois déchi�rer complètement la version 4.01, la plus répandue.
55
13 TD 13 : Simulation d'une corde suspendue
(correction page 130)
Ce TD détaille les étapes qui permettent de construire un programme simulant la chute d'une cordejusqu'à sa stabilisation autour d'une position d'équilibre. L'étude physique est détaillée dans le documenthttp ://perso.wanadoo.fr/x.dupre/programmation/python_cours_exemple.pdf, ce TD ne concerne que lasimulation informatique.
La corde est représentée par une suite de n masses ponctuelles reliés par des ressorts de masse nulle quiexercent une traction lorsque leur longueur dépasse un certain seuil. On considère une corde de longueurL et de masse M , elle est divisée en n masses de masses M
n . Ces masses sont reliées par n− 1 ressorts quiexercent une traction sur les masses qu'ils relient lorsque leur longueur dépasse le seuil L
n−1 . Les massessont initialement placées sur une droite reliant les deux extremités �xes de la corde.
Chaque masse est soumis à une accélération égale à la somme de trois forces qui sont son poids et lestractions exercées par les ressorts auxquels elle est attachée (voir �gure 13.13). A chaque instant t, on peutcalculer cette accélération, en déduire la vitesse puis la position à l'instant t + 1. Ce mécanisme permetd'obtenir une animation de la corde atteignant sa position d'équilibre (voir �gure 13.14). On construitl'algorithme suivant.
Fig. 13.13 � Dessin d'une corde suspendue entre ses deux extrémités, cette corde est représentée par unensemble de masses ponctuelles reliées par des ressorts. Trois forces s'exercent sur chaque masse, son poidset les deux tensions dues à ses deux voisins.
56
a b
c d
Fig. 13.14 � Dessin d'une corde suspendue entre ses deux extrémités, cette corde est modélisée par unensemble de masses ponctuelles reliées par des morceaux de corde élastiques sans masse. Ces quatre imagesa, b, c, d représentent la corde lorsqu'on la laisse tomber. La courbe bleue et lisse est la courbe théoriquede la corde.
Algorithme 13.1 : mouvement d'une cordeSoit une corde de longueur L suspendue entre les points d'abscisse (−x0, 0) et (x0, 0) de tellesorte que 2x0 < L. Cette corde à une masse M et une raideur k. La pesanteur est notée g. Ondivise cette corde en n masses ponctuelles de masse ∀i ∈ {1, . . . , n} , mi = M
n . Chaque massea une position pi. On note pour chaque point pi sa vitesse vi. On désigne par f un coe�cientde freinage, plus cette vitesse est grande, plus la corde convergera rapidement vers sa positiond'équilibre. dt désigne un pas de temps.Etape A : initialisation∀i ∈ {1, . . . , n} , pi = −x0 + 2x0
i−1n−1
Etape B : calcul des forcesPour chaque masse, on calcule une accélération ai ∈ R2. a0 = an = 0 (lesextrémités sont �xes).pour i = 1 à n− 1 faire
ai ←− (0,−mig)− fvi
si ‖−−−−→pi−1, pi‖ > Ln−1
ai ←− ai + k[‖−−−−→pi−1, pi‖ − L
n−1
] −−−−→pipi−1
‖−−−−→pi−1,pi‖�n sisi ‖−−−−→pi+1, pi‖ > L
n−1
ai ←− ai + k[‖−−−−→pi+1, pi‖ − L
n−1
] −−−−→pipi+1
‖−−−−→pi+1,pi‖�n si
�n pour
Etape C : mise à jour des positionspour i = 1 à n− 1 faire
pi ←− pi + vidtvi ←− vi + aidt
�n pour
57
Etape D : terminaisonTant que l'algorithme n'a pas convergé, on retourne à l'étape B.
1)On cherche dans un premier temps à dé�nir une classe point qui modélise une masse ponctuelle dela code. Cette classe contient quatre méthodes __init__, deplace_point, difference et norme. Onajoute également la méthode __str__ de manière à pouvoir a�cher le contenu de la classe et corrigercertaines erreurs lors de l'implémentation.
class point (object) :
"""définition d'un point : deux coordonnées et une masse"""
__slots__ = "x","y","m"
def __init__ (self, x,y,m) :
"""définit un point de la corde, de coordonnées (x,y) et de masse m"""
def deplace_point (self, dep, dt) :
"""déplace un point, le vecteur de déplacement est dp * dt
où dep est aussi un point (self += dep * dt)"""
def difference (self, p) :
"""retourne le vecteur qui relie deux points,
retourne le couple de ses coordonnées"""
def norme (self) :
"""retourne la norme du vecteur (x,y)"""
def __str__ (self) :
"""afficher le point"""
return "(x,y) = (%4.1f,%4.1f) masse %f" % (self.x,self.y,self.m)
2)On dé�nit ensuite la classe corde qui contient également quatre méthodes __init__, force_point,iteration, display. La méthode force_point correspond à l'étape B de l'algorithme tandis que la classeiteration correspond à l'étape C. Le constructeur initialise la classe, il répartit également uniformémentles masses ponctuelles sur le segment rejoignant les deux extremités. La méthode display permet d'a�cherla corde à l'écran et de véri�er visuellement visuellement que le programme fonctionne bien.
class corde (object) :
"""définition d'une corde, une liste de points"""
def __init__(self, nb, p1, p2, m, k, g, f, l) :
"""initialisation d'une corde
@param nb nombre de points
@param p1 = x1,y1 coordoonnées du premier point (fixe)
@param p2 = x2,y2 coordoonnées du dernier point (fixe)
@param m masse de la corde,
répartie entre tous les pointstous les points
@param k raideur de l'élastique
58
@param g intensité de l'apesanteur,
valeur positive
@param f vitesse de freinage
@param l longueur de la corde"""
def force_point (self, i) :
"""calcule les forces qui s'exerce en un point, retourne un point x,y"""
def iteration (self, dt) :
"""calcule les déplacements de chaque point et les met à jour,
on ne déplace pas les points situés aux extrémités,
retourne la somme des vitesses et des accélérations au carré"""
def display (self, screen) :
"""affichage de la corde à l'aide du module pyagame"""
3) Il ne reste plus qu'à faire évoluer la corde au fur et à mesure du temps. Cela passe d'abord par unephase d'initialisation.
# initialisation du module pygame
pygame.init ()
size = width, height = x,y = 800, 500
white = 255,255,255
screen = pygame.display.set_mode(size)
# création de la corde
nb = 10
c = corde (nb, (100,450), (700,450), m = 400, k = 1, g = 0.1, f = 0.05, l = 800)
dt = 0.1
On se sert également d'une fonction qui attend la pression d'un clic de souris avant de se terminer. Cettefonction permet de �ger l'écran en attendant un événement.
def attendre_clic (screen,x,y):
"""dessine un rectangle rouge sur l'écran et
attend la pression d'un clic de souris"""
color = 255,0,0
pygame.draw.line (screen, color, (10,10), (x-10,10), 2)
pygame.draw.line (screen, color, (x-10,10), (x-10,y-10), 2)
pygame.draw.line (screen, color, (x-10,y-10), (10,y-10), 2)
pygame.draw.line (screen, color, (10,y-10), (10,10), 2)
pygame.display.flip ()
reste = True
while reste:
for event in pygame.event.get():
if event.type == pygame.MOUSEBUTTONUP :
reste = False
break
Le programme se termine par cette boucle qui doit réitérer les étapes B et C a�n de déplacer la corde. Ilsu�t d'ajouter la ou les instructions qui manque à cette boucle incomplète.
59
iter = 0 # numéro d'itération
dep = len (c.list) * (x*x + y*y) # continue tant que dep n'est pas proche de 0
while True and dep > 1e-3 :
# on peut stopper temporairement le programme d'une pression
# du bouton gauche de la souris
for event in pygame.event.get():
if event.type == pygame.QUIT: sys.exit()
if event.type == pygame.MOUSEBUTTONUP:
attendre_clic (screen,x,y)
# on affiche régulièrement la corde, ici toutes les dix itérations
if iter % 10 == 0 :
screen.fill (white)
c.display (screen)
pygame.display.flip ()
# on incrémente le nombre d'itérations
iter += 1
# on fait une pause dès la première itérations pour voir la corde
# dans sa position initiale
if iter == 1: attendre_clic (screen,x,y)
# on met à jour l'écran
pygame.display.flip ()
# le programme est terminé, on fait une pause pour voir le résultat final
attendre_clic (screen,x,y)
60
14 Correction du TD 1, page 3
La première ligne de commentaire permet d'insérer des accents dans les commentaires et les chaînes decaractères.
1 # -*- coding: cp1252 -*-
2 # la première ligne permet d'insérer des accents dans les commentaires
3 import random
4 rejouer = True
5 somme = 0
6 nb_partie = 0
7 while rejouer :
8 hasard = rd.randint(1,20)
9 nb_partie += 1
10
11 devine = 0
12 coup = 0
13 while devine != hasard :
14 coup += 1
15 devine = raw_input ("Entrer un nombre ?")
16 devine = float (devine) # conversion en réel
17 if (devine > hasard) :
18 print "Le nombre entré est trop grand."
19 if (devine < hasard) :
20 print "Le nombre entré est trop petit."
21
22 somme += coup
23 print "Vous avez trouvé en " , coup, " coups."
24 print "Vous avez déjà joué ", somme, " coups et ", nb_partie, " parties."
25 rejouer = raw_input("Voulez-vous rejouer ?")
26 rejouer = rejouer == "oui" or rejouer == "o" or rejouer == "1"
27
28 moyenne = float (somme) / nb_partie # conversion en réel, sinon la division est entière
29 print "Nombre de coups moyen par parties : " , moyenne
�n correction TD 1 ut
61
15 Correction du TD 2, page 4
1)
# -*- coding: cp1252 -*-
import random
import math
n = 10000
hn = dict ()
for i in xrange (1,n):
x = random.gauss (0,1)
xx = round (x, 1)
if xx not in hn: # si h [xx] n'existe pas encore
hn [xx] = 0
hn [xx] += 1
# affichage de l'histogramme
for w in hn:
print w, " \t", float (hn [w]) / float (n)
L'histogramme est ensuite recopié depuis l'interpréteur Python vers Excel où il sera dessiné (voir �-gure 15.15).
Fig. 15.15 � Histogramme sous Excel d'une variable suivant la loi normale (courbe noire), et sa densité(courbe rouge, grisée). Les abscisses ont été triées par ordre croissant. Si Excel est en version française,il est nécessaire de remplacer le symbol "." par ",". Les deux courbes comparées sont (mε, hm)m pourl'histogramme et (mε, f(mε)ε)m pour la densité. La valeur de l'histogramme correspondant à la valeur del'intégrale de la densité sur l'intervalle [mε, (m + 1)ε].
2)
# -*- coding: cp1252 -*-
import random
62
import math
n = 10000
hb = dict ()
k = 400
for i in xrange (1,n):
if (i % 500 == 0) : # comme le programme est assez lent,
print i # cela permet de suivre l'avancement
s = 0
for j in xrange (1,k):
a = random.randint (0,1)
s += a
x = float (s - k/2) / math.sqrt (float (k * 0.25))
xx = round (x, 1)
if xx not in hb:
hb [xx] = 0
hb [xx] += 1
# affichage de l'histogramme
for w in hb:
print w, " \t", float (hb [w]) / float (n)
Fig. 15.16 � Graphique regroupant les deux histogrammes et la densité. Les trois courbes suivent le mêmechemin. Plus n sera grand, plus les histogrammes vont se rapprocher de la courbe de la densité.
Comme pour la question 1, l'histogramme est ensuite recopié depuis l'interpréteur Python vers Excel où
il sera dessiné (voir �gure 15.16). Lorsque k = 100, la variable Y ′ =
k∑i=1
(Xi− k2 )√
k4
où Xi ∈ {0, 1} est une
variable aléatoire de binomiale B(k, 1
2
)dé�nie par :
Y ′ =
k∑i=1
(Xi − 50)
5
63
Par conséquent, Y ′ est un nombre entier divisé par 5, c'est donc un multiple entier de 0, 2. Or la largeurd'un intervalle est de ε = 0, 1 < 0, 2. L'histogramme calculé pour k = 100 ne peut avoir une largeurd'intervalle ε inférieure à 0, 2. Par conséquent, les histogrammes obtenus pour les deux questions ne sontplus comparables (voir �gure 15.18).
Fig. 15.17 � Pour k = 100, ε doit être supérieur à 0, 2. L'histogramme obtenu a une amplitude deux foisplus grande mais, pour la moitié des intervalles [mε, (m + 1)ε[, la valeur hm de l'histogramme est nul. On
véri�e que pour tous les histogrammes,∑
m hm = 1 =∫∞−∞
1√2π
e−x2
2 dx.
Pour aller plus loin :
Il est possible d'éviter le passage par Excel et d'a�cher directement depuis Python la représentationgraphique d'une distribution, ce que le code suivant permet de faire (voir �gure 15.18). Cette solutionnécessite l'installation de trois modules, le module IaGraph5, Numeric6, ScientificPython7. Ceux-ci sontparfois fournis avec un �chier exécutable qui e�ectue l'installation de manière automatique. L'installationest parfois manuelle et suit le même schéma que celle présentée au TD ??, question 6.
x = hn.keys ()
x.sort ()
y = [ hn [a] for a in x ]
import IaGraph.plot
IaGraph.plot(x, y)
import Tkinter
Tkinter.mainloop ()
Il est aussi possible d'utiliser la librairie SciPy8. Ce module inclut un sous-module gplt. Le programmefait apparaître une fenêtre (voir �gure 15.19) qui disparaît lorsqu'on termine une session de Python.
5Module permettant de tracer des graphes de types XY ou des courbes de niveaux, adresse : http ://www.johnny-lin.com/py_pkgs/IaGraph/Doc/
6Module proposant des fonctionnalités mathématiques, manipulation de tableaux, transformée de Fourier rapide, ...adresse : http ://sourceforge.net/projects/numpy
7Module proposant d'autres fonctionnalités scienti�ques, utilisation de VRML, multi threading, librairie MPI, dérivés,interpolation, quaternion, histogramme, ... adresse : http ://starship.python.net/ hinsen/Scienti�cPython/
8Le module SciPy propose de nombreux algorithmes, algorithmes de classi�cation, intégration, optimisation, générationde nombres aléatoires, traitement du signal, interpolation, algorithmes génétiques, algèbre linéaire, transformée de Fourier,dessin de courbe 2D, 3D, adresse : http ://www.scipy.org/
64
Fig. 15.18 � Représentation de l'histogramme obtenu à partir d'une loi normale en utilisant le moduleIaGraph.plot.
from scipy import gplt
x1 = hn.keys ()
x1.sort ()
y = [ hn [a] for a in x1 ]
x2 = hb.keys ()
x2.sort ()
z = [ hb [a] for a in x2 ]
gplt.plot (x1,y,x2,z)
Fig. 15.19 � Représentation des histogrammes obtenus en utilisant le module scipy.gplt.
Un autre module biggles permet de dessiner une courbe. Il a l'avantage de pouvoir convertir les graphesdirectement sous forme d'images. Il est accessible depuis l'adresse http ://biggles.sourceforge.net/. Lerésultat obtenu est illustré par la �gure 15.20.
x1 = hn.keys ()
x1.sort ()
y = [ hn [a] for a in x1 ]
x2 = hb.keys ()
x2.sort ()
z = [ hb [a] for a in x2 ]
65
import biggles
p = biggles.FramedPlot()
p.title = "Histogramme"
p.xlabel = "x"
p.ylabel = "y"
p.add( biggles.Curve(x1, y, color="red") )
p.add( biggles.Curve(x2, z, color="blue") )
p.show()
Fig. 15.20 � Représentation des histogrammes obtenus en utilisant le module biggles.
Finalement, le programme est :
1 # -*- coding: cp1252 -*-
2 import random
3 import math
4
5 n = 10000
6 hn = dict ()
7
8 for i in xrange (1,n):
9 x = random.gauss (0,1)
10 xx = round (x, 1)
11 if xx not in hn: # si h [xx] n'existe pas encore
12 hn [xx] = 0
13 hn [xx] += 1
14
15 # affichage de l'histogramme
16 for w in hn:
17 print w, " \t", float (hn [w]) / float (n)
18
19
20 n = 10000
21 hb = dict ()
22 k = 400
23 for i in xrange (1,n):
24 if (i % 500 == 0) : # comme le programme est assez lent,
66
25 print i # cela permet de suivre l'avancement
26 s = 0
27 for j in xrange (1,k):
28 a = random.randint (0,1)
29 s += a
30 x = float (s - k/2) / math.sqrt (float (k * 0.25))
31 xx = round (x, 1)
32
33 if xx not in hb:
34 hb [xx] = 0
35 hb [xx] += 1
36
37 # affichage de l'histogramme
38 for w in hb:
39 print w, " \t", float (hb [w]) / float (n)
40
41
42 x1 = hn.keys ()
43 x1.sort ()
44 y = [ hn [a] for a in x1 ]
45 x2 = hb.keys ()
46 x2.sort ()
47 z = [ hb [a] for a in x2 ]
48
49 import biggles
50 p = biggles.FramedPlot()
51 p.title = "Histogramme"
52 p.xlabel = "x"
53 p.ylabel = "y"
54 p.add( biggles.Curve(x1, y, color="red") )
55 p.add( biggles.Curve(x2, z, color="blue") )
56 p.show()
57
�n correction TD 2 ut
67
16 Correction du TD 3, page 6
A chaque question correspond une fonction utilisant celles décrites dans les questions précédentes. Leprogramme complet est obtenu en juxtaposant chaque morceau.
1)
# -*- coding: cp1252 -*-
def lire_separation(s):
"""divise un nombre littéral en mots"""
s = string.replace (s, "-", " ")
return string.split (s)
2)
def lire_unite (s) :
"""convertit numériquement les nombres inclus entre 0 et 16 inclus, """\
"""20, 30, 40, 50, 60, s est une chaîne de caractères, le résultat est entier"""
if s == "zéro" : return 0
elif s == "un" : return 1
elif s == "deux" : return 2
elif s == "trois" : return 3
elif s == "quatre" : return 4
elif s == "cinq" : return 5
elif s == "six" : return 6
elif s == "sept" : return 7
elif s == "huit" : return 8
elif s == "neuf" : return 9
elif s == "dix" : return 10
elif s == "onze" : return 11
elif s == "douze" : return 12
elif s == "treize" : return 13
elif s == "quatorze" : return 14
elif s == "quinze" : return 15
elif s == "seize" : return 16
elif s == "vingt" : return 20
elif s == "trente" : return 30
elif s == "quarante" : return 40
elif s == "cinquante" : return 50
elif s == "soixante" : return 60
else : return 0
3)La réponse à cette question est divisée en deux fonctions. La première traduit une liste de mots en unnombre numérique.
def lire_dizaine_liste(s):
"""convertit une liste de chaîne de caractères dont """\
"""juxtaposition forme un nombre littéral compris entre """\
"""0 et 99"""
r = 0 # contient le résultat final
68
dizaine = False # a-t-on terminé le traitement des dizaines ?
for mot in s:
n = lire_unite (mot)
if n == 10 or n == 20 :
if not dizaine and r > 0 and r != 60:
r *= n
dizaine = True
else :
r += n
else :
r += n
return r
La seconde fonction remplace tous les traits d'union par des espaces puis divise un nombre littéral en listede mots séparés par des espaces.
def lire_dizaine(s):
s2 = s.replace ("-", " ")
li = string.split (s2)
return lire_dizaine_liste (li)
Travail à faire :
Tout d'abord, les deux fonctions réciproques de celles présentées ci-dessus.
def ecrit_unite (x):
"""convertit un nombre compris inclus entre 0 et 16 inclus, """\
"""20, 30, 40, 50, 60 en une chaîne de caractères"""
if x == 0: return "zéro"
elif x == 1: return "un"
elif x == 2: return "deux"
elif x == 3: return "trois"
elif x == 4: return "quatre"
elif x == 5: return "cinq"
elif x == 6: return "six"
elif x == 7: return "sept"
elif x == 8: return "huit"
elif x == 9: return "neuf"
elif x == 10: return "dix"
elif x == 11: return "onze"
elif x == 12: return "douze"
elif x == 13: return "treize"
elif x == 14: return "quatorze"
elif x == 15: return "quinze"
elif x == 16: return "seize"
elif x == 20: return "vingt"
elif x == 30: return "trente"
elif x == 40: return "quarante"
elif x == 50: return "cinquante"
elif x == 60: return "soixante"
69
else : return "zéro"
def ecrit_dizaine(x):
"""convertit un nombre entre 0 et 99"""\
"""sous sa forme littérale"""
if x <= 16:
return ecrit_unite(x)
s = ""
dizaine = x / 10
unite = x % 10
if dizaine == 1:
s = "dix "
s += ecrit_unite(unite)
elif dizaine <= 6:
s = ecrit_unite (dizaine*10)
s += " "
s += ecrit_unite (unite)
else:
if dizaine == 7:
s = "soixante dix"
elif dizaine == 8:
s = "quatre vingt"
else:
s = "quatre vingt dix"
s += " "
s += ecrit_unite (unite)
return s
Le morceau de code ci-dessous permet de véri�er que le passage d'un nombre sous sa forme littérale etréciproquement fonctionne correctement pour tous les nombres compris entre 0 et 99 inclus.
for i in xrange(0,100):
s = ecrit_dizaine (i)
j = lire_dizaine (s)
if i != j :
print "erreur ", i, " != ", j, " : ", s
Finalement, le programme est :
1 # -*- coding: cp1252 -*-
2 def lire_separation(s):
3 """divise un nombre littéral en mots"""
4 s = string.replace (s, "-", " ")
5 return string.split (s)
6
7 def lire_unite (s) :
8 """convertit numériquement les nombres inclus entre 0 et 16 inclus, """\
70
9 """20, 30, 40, 50, 60, s est une chaîne de caractères, le résultat est entier"""
10 if s == "zéro" : return 0
11 elif s == "un" : return 1
12 elif s == "deux" : return 2
13 elif s == "trois" : return 3
14 elif s == "quatre" : return 4
15 elif s == "cinq" : return 5
16 elif s == "six" : return 6
17 elif s == "sept" : return 7
18 elif s == "huit" : return 8
19 elif s == "neuf" : return 9
20 elif s == "dix" : return 10
21 elif s == "onze" : return 11
22 elif s == "douze" : return 12
23 elif s == "treize" : return 13
24 elif s == "quatorze" : return 14
25 elif s == "quinze" : return 15
26 elif s == "seize" : return 16
27 elif s == "vingt" : return 20
28 elif s == "trente" : return 30
29 elif s == "quarante" : return 40
30 elif s == "cinquante" : return 50
31 elif s == "soixante" : return 60
32 else : return 0
33
34 def lire_dizaine_liste(s):
35 """convertit une liste de chaîne de caractères dont """\
36 """juxtaposition forme un nombre littéral compris entre """\
37 """0 et 99"""
38 r = 0 # contient le résultat final
39 dizaine = False # a-t-on terminé le traitement des dizaines ?
40 for mot in s:
41 n = lire_unite (mot)
42 if n == 10 or n == 20 :
43 if not dizaine and r > 0 and r != 60:
44 r *= n
45 dizaine = True
46 else :
47 r += n
48 else :
49 r += n
50 return r
51
52 def lire_dizaine(s):
53 s2 = s.replace ("-", " ")
54 li = string.split (s2)
55 return lire_dizaine_liste (li)
56
57 def ecrit_unite (x):
58 """convertit un nombre compris inclus entre 0 et 16 inclus, """\
71
59 """20, 30, 40, 50, 60 en une chaîne de caractères"""
60 if x == 0: return "zéro"
61 elif x == 1: return "un"
62 elif x == 2: return "deux"
63 elif x == 3: return "trois"
64 elif x == 4: return "quatre"
65 elif x == 5: return "cinq"
66 elif x == 6: return "six"
67 elif x == 7: return "sept"
68 elif x == 8: return "huit"
69 elif x == 9: return "neuf"
70 elif x == 10: return "dix"
71 elif x == 11: return "onze"
72 elif x == 12: return "douze"
73 elif x == 13: return "treize"
74 elif x == 14: return "quatorze"
75 elif x == 15: return "quinze"
76 elif x == 16: return "seize"
77 elif x == 20: return "vingt"
78 elif x == 30: return "trente"
79 elif x == 40: return "quarante"
80 elif x == 50: return "cinquante"
81 elif x == 60: return "soixante"
82 else : return "zéro"
83
84 def ecrit_dizaine(x):
85 """convertit un nombre entre 0 et 99"""\
86 """sous sa forme littérale"""
87
88 if x <= 16:
89 return ecrit_unite(x)
90
91 s = ""
92 dizaine = x / 10
93 unite = x % 10
94 if dizaine == 1:
95 s = "dix "
96 s += ecrit_unite(unite)
97 elif dizaine <= 6:
98 s = ecrit_unite (dizaine*10)
99 s += " "
100 s += ecrit_unite (unite)
101 else:
102 if dizaine == 7:
103 s = "soixante dix"
104 elif dizaine == 8:
105 s = "quatre vingt"
106 else:
107 s = "quatre vingt dix"
108 s += " "
72
109 s += ecrit_unite (unite)
110 return s
111
112 for i in xrange(0,100):
113 s = ecrit_dizaine (i)
114 j = lire_dizaine (s)
115 if i != j :
116 print "erreur ", i, " != ", j, " : ", s
�n correction TD 3 ut
73
17 Correction du TD 4, page 7
1)La chaîne de caractères que contient NoeudTri s'appelle str.
class NoeudTri (object):
def __init__(self,s):
self.str = s
2)
class NoeudTri (object):
def __init__(self,s):
self.str = s
def __str__(self):
return self.str
3)
class NoeudTri (object):
def __init__(self,s):
self.str = s
def __str__(self):
return self.str
def insere (self,s):
c = cmp (s, self.str)
if c == -1:
self.avant = NoeudTri (s)
elif c == 1:
self.apres = NoeudTri (s)
Après les lignes d'instructions suivantes :
import pprint
racine = NoeudTri ("un")
print "------------------------------"
pprint.pprint (racine.__dict__)
racine.insere ("unité")
print "------------------------------"
pprint.pprint (racine.__dict__)
racine.insere ("deux")
print "------------------------------"
pprint.pprint (racine.__dict__)
Python a�che :
74
------------------------------
{'str': 'un'}
------------------------------
{'apres': <__main__.NoeudTri object at 0x00A54BD0>, 'str': 'un'}
------------------------------
{'apres': <__main__.NoeudTri object at 0x00A54BD0>,
'avant': <__main__.NoeudTri object at 0x00A72410>,
'str': 'un'}
4)
class NoeudTri (object):
def __init__(self,s):
self.str = s
def __str__(self):
s = ""
if "avant" in self.__dict__:
s += self.avant.__str__ ()
s += self.str + "\n"
if "apres" in self.__dict__:
s += self.apres.__str__()
return s
def insere (self,s):
c = cmp (s, self.str)
if c == -1:
self.avant = NoeudTri (s)
elif c == 1:
self.apres = NoeudTri (s)
Le programme suivant permet d'a�cher une liste de trois mots triée.
racine = NoeudTri ("un")
print "------------------------------"
print racine
print "------------------------------"
racine.insere ("unité")
print racine
print "------------------------------"
racine.insere ("deux")
print racine
Voici le résultat :
------------------------------
un
------------------------------
75
un
unité
------------------------------
deux
un
unité
5)Le programme avec la méthode insere la plus complète :
# -*- coding: cp1252 -*-
import string
class NoeudTri (object):
def __init__(self,s):
self.str = s
def __str__(self):
s = ""
if "avant" in self.__dict__:
s += self.avant.__str__ ()
s += self.str + "\n"
if "apres" in self.__dict__:
s += self.apres.__str__()
return s
def insere (self,s):
c = cmp (s, self.str)
if c == -1:
if "avant" in self.__dict__:
self.avant.insere (s)
else:
self.avant = NoeudTri (s)
elif c == 1:
if "apres" in self.__dict__:
self.apres.insere (s)
else:
self.apres = NoeudTri (s)
6)Le programme avec le code permettant de transcrire le graphe de manière graphique. La �gure 17.21détient le graphe obtenu.
1 # -*- coding: cp1252 -*-
2
3 import string
4 import graphlib.GraphDot as GraphDot
5
6 class SecondeInserstion (AttributeError):
7 "insertion d'un mot déjà inséré"
8
76
9 class NoeudTri (object):
10
11 def __init__(self,s):
12 self.str = s
13
14 def __str__(self):
15 s = ""
16 if "avant" in self.__dict__:
17 s += self.avant.__str__ ()
18 s += self.str + "\n"
19 if "apres" in self.__dict__:
20 s += self.apres.__str__()
21 return s
22
23 def affiche_graph (self, dot, n = 0):
24 n += 1
25 self.id = n
26 dot.node_style (self.id, label=self.str)
27 if "avant" in self.__dict__:
28 n = self.avant.affiche_graph (dot, n)
29 dot.edge_style (self.id, self.avant.id, label = "-")
30 if "apres" in self.__dict__:
31 n = self.apres.affiche_graph (dot, n)
32 dot.edge_style (self.id, self.apres.id, label = "+")
33 return n
34
35 def insere (self,s):
36 c = cmp (s, self.str)
37 if c == -1:
38 if "avant" in self.__dict__:
39 self.avant.insere (s)
40 else:
41 self.avant = NoeudTri (s)
42 elif c == 1:
43 if "apres" in self.__dict__:
44 self.apres.insere (s)
45 else:
46 self.apres = NoeudTri (s)
47 else:
48 raise SecondeInsertion, "mot : " + s
49
50
51 racine = NoeudTri ("un")
52 racine.insere ("deux")
53 racine.insere ("unité")
54 racine.insere ("dizaine")
55 racine.insere ("exception")
56 racine.insere ("programme")
57 racine.insere ("abc")
58 racine.insere ("xyz")
77
59 racine.insere ("mnop")
60
61 print racine
62
63
64 dot = GraphDot.Dot ()
65 racine.affiche_graph (dot)
66 dot.save_img(file_name='graph', file_type='png')
Fig. 17.21 � Graphe de tri obtenu lors du tri quicksort. Chaque n÷ud du graphe inclus un mot. Lessymboles "-" et "+" des arcs désigne les membres avant et apres de la classe NoeudTri. Tous les motsattachés à un arc "-" d'un n÷ud sont classés avant le mot de ce n÷ud. De même, tous les mots attachésà un arc "+" d'un n÷ud sont classés après le mot de ce n÷ud.
Travail à faire :
Le programme �nal avec les exceptions mais sans le code liés à l'a�chage du graphe sous sa forme gra-phique :
1 # -*- coding: cp1252 -*-
2 import string
3
4 class SecondeInserstion (AttributeError):
5 "insertion d'un mot déjà inséré"
6
7 class NoeudTri (object):
8
9 def __init__(self,s):
10 self.str = s
11
12 def __str__(self):
13 s = ""
78
14 if "avant" in self.__dict__:
15 s += self.avant.__str__ ()
16 s += self.str + "\n"
17 if "apres" in self.__dict__:
18 s += self.apres.__str__()
19 return s
20
21 def insere (self,s):
22 c = cmp (s, self.str)
23 if c == -1:
24 if "avant" in self.__dict__:
25 self.avant.insere (s)
26 else:
27 self.avant = NoeudTri (s)
28 elif c == 1:
29 if "apres" in self.__dict__:
30 self.apres.insere (s)
31 else:
32 self.apres = NoeudTri (s)
33 else:
34 raise SecondeInsertion, "mot : " + s
35
36
37 racine = NoeudTri ("un")
38 racine.insere ("deux")
39 racine.insere ("unité")
40 racine.insere ("dizaine")
41 racine.insere ("exception")
42 racine.insere ("programme")
43 racine.insere ("abc")
44 racine.insere ("xyz")
45 racine.insere ("mnop")
46
47 print racine
Le programme a�che les mots dans l'ordre suivant :
abc
deux
dizaine
exception
mnop
programme
un
unité
xyz
�n correction TD 4 ut
79
18 Correction du TD 5, page 10
1)
Par rapport au programme initial, deux lignes ont été ajoutées, deux lignes ont été déplacées, elles sont sui-vies d'un commentaires commençant par # −−−−−−−−. Un exemple d'exécution de ce programmeapparaît à la �gure 18.22.
La première fonction trace_ligne_simple contient deux parties presque identiques. La première,lignes 12 à 28, trace des lignes partant de l'origine (x1, y1) vers un point situé entre l'axe des abscisseset la première bissectrice. A chaque itération, on se déplace d'un pixel vers la droite et parfois d'un pixelvers le haut. La seconde partie, lignes 30 à 45, trace des lignes partant de l'origine (x1, y1) vers un pointsitué entre l'axe des ordonnées et la première bissectrice. A chaque itération, on se déplace d'un pixel versle haut et parfois d'un pixel vers la droite.
La seconde fonction, trace_ligne, trace toutes les lignes en se ramenant par translation et/ou symétrieaxiale à l'un des deux cas traités par la première fonction.
1 # -*- coding: cp1252 -*-
2 """ce module contient la fonction trace_ligne qui retourne l'ensemble des pixels
3 concernés par le tracé d'une ligne en 8-connexité entre deux pixels"""
4 import pygame # pour les affichages
5 import random
6
7 def trace_ligne_simple (x1,y1,x2,y2):
8 """trace une ligne entre les points de coordonnées (x1,y1) et (x2,y2),
9 on suppose que x2 > x1, y2 >= y1,
10 retourne la ligne sous la forme d'un ensemble de pixels (x,y)"""
11
12 if y2 - y1 <= x2 - x1 : # droite en dessous de la première bissectrice
13 vx = x2 - x1
14 vy = y2 - y1
15 b = vx / 2
16 y = y1
17 x = x1
18
19 ligne = []
20 while x <= x2 :
21 ligne.append ((x,y))
22 b -= vy
23 if b < 0:
24 b += vx
25 y += 1
26 ligne.append ((x,y)) # ------ ligne ajoutée
27 x += 1 # ------ ligne déplacée
28 return ligne
29 else : # droite au dessus de la première bissectrice
30 vx = x2 - x1
31 vy = y2 - y1
32 b = vy / 2
33 y = y1
80
34 x = x1
35
36 ligne = []
37 while y <= y2 :
38 ligne.append ((x,y))
39 b -= vx
40 if b < 0:
41 b += vy
42 x += 1
43 ligne.append ((x,y)) # ------ ligne ajoutée
44 y += 1 # ------ ligne déplacée
45 return ligne
46
47 def trace_ligne (x1,y1,x2,y2):
48 """trace une ligne entre les points de coordonnées (x1,y1) et (x2,y2),
49 aucune contrainte sur les coordonnées,
50 retourne la ligne sous la forme d'un ensemble de pixels (x,y)"""
51
52 if x1 == x2 :
53 if y1 <= y2: return [ (x1, i) for i in xrange (y1,y2+1) ]
54 else : return [ (x1, i) for i in xrange (y2,y1+1) ]
55
56 if y1 == y2 :
57 if x1 <= x2: return [ (i, y1) for i in xrange (x1,x2+1) ]
58 else : return [ (i, y1) for i in xrange (x2,x1+1) ]
59
60 if x1 < x2 :
61 if y1 < y2 :
62 return trace_ligne_simple (x1,y1,x2,y2)
63 else :
64 ligne = trace_ligne_simple (x1,y2,x2,y1)
65 return [ (x,y1 + y2 - y) for (x,y) in ligne ]
66
67 if x2 < x1 :
68 if y1 < y2 :
69 ligne = trace_ligne_simple (x2,y1,x1,y2)
70 return [ (x1 + x2 - x, y) for (x,y) in ligne ]
71 else :
72 ligne = trace_ligne_simple (x2,y2,x1,y1)
73 return [ (x1 + x2 - x, y1 + y2 - y) for (x,y) in ligne ]
74
75 def display_ligne (ligne, screen):
76 """affiche une ligne à l'écran"""
77 color = 0,0,0
78 for p in ligne:
79 pygame.draw.line (screen, color, p,p)
80 pygame.display.flip ()
81
82
83 def attendre_clic (screen):
81
84 """attend la pression d'un clic de souris pour continuer"""
85 reste = True
86 while reste:
87 for event in pygame.event.get():
88 if event.type == pygame.MOUSEBUTTONUP :
89 reste = False
90 break
91
92 if __name__ == "__main__" :
93 pygame.init ()
94
95 size = width, height = x,y = 200, 200
96 black = 0, 0, 0
97 white = 255,255,255
98 screen = pygame.display.set_mode(size)
99 screen.fill (white)
100
101 print trace_ligne (0,0, 7,3)
102 # affiche [(0, 0), (1, 0), (1, 1), (2, 1), (3, 1),
103 # (3, 2), (4, 2), (5, 2), (5, 3), (6, 3), (7, 3)]
104 # rappel : résultat en 8-connexité :
105 # [(0, 0), (1, 0), (2, 1), (3, 1), (4, 2), (5, 2), (6, 3), (7, 3)]
106
107 for n in xrange (0,10):
108 x1 = random.randint (0,x-1)
109 y1 = random.randint (0,y-1)
110 x2 = random.randint (0,x-1)
111 y2 = random.randint (0,y-1)
112 ligne = trace_ligne (x1,y1,x2,y2)
113 display_ligne (ligne, screen)
114
115 attendre_clic (screen)
2)
Les fonctions display_ligne, attendre_clic sont identiques aux programmes précédent. La partieprincipale (celle qui suit l'instruction if __name__ == ”__main__” :) est quasiment identique.La fonction qui permet de tracer une ellipse s'intitule trace_ellipse. Un exemple d'exécution de ceprogramme apparaît à la �gure 18.22.
1 # -*- coding: cp1252 -*-
2 """ce module contient la fonction trace_ellipse qui retourne l'ensemble des pixels
3 concernés par le tracé d'une ellipse en 8-connexité"""
4 import pygame # pour les affichages
5 import random
6 import math
7
8 def trace_ellipse (xc,yc,a,b):
9 """dessine une ellipse de centre xc,yc, de demi axe horizontal a,
10 de demi-axe vertical b, l'ellipse a pour équation x²/a² + y²/b² = 1
11 si l'origine est placée en xc,yc,
82
12 l'équation de la tangente au point x0, y0 est : x x0 / a² + y y0 / b² = 0,
13 ou x x0 b² + y y0 a² = 0"""
14
15 # on évite les cas litigieux
16 if a == 0 :
17 return [ (xc, yc + y) for y in xrange (-b,b) ]
18 if b == 0 :
19 return [ (xc + x, yc) for x in xrange (-a,a) ]
20
21 bb = b * b
22 aa = a * a
23
24 # on trace l'ellipse de centre 0,0
25 ellipse = []
26 # premier huitième
27 vx = a * bb
28 vy = 0
29 x = a
30 y = 0
31 bl = vx / 2
32
33 while vx >= vy and x >= 0 :
34 ellipse.append ((x,y))
35 y += 1
36 vy += aa # vy = y * aa
37 bl -= vy
38 if bl < 0 :
39 x -= 1
40 vx -= bb # vx = x * bb
41 bl += vx
42
43 # second huitième
44 while x >= 0 :
45 ellipse.append ((x,y))
46 x -= 1
47 vx -= bb # vx = x * bb
48 bl += vx
49 if bl > 0 :
50 y += 1
51 vy += aa # vy = y * aa
52 bl -= vy
53
54 # second quart, symétrique par rapport à l'axe des ordonnées
55 ellipse2 = [ (-x,y) for (x,y) in ellipse ]
56 ellipse2.reverse ()
57 ellipse.extend (ellipse2)
58
59 # troisième et quatrième quarts : symétrique par rapport à l'axe des abscisse
60 ellipse2 = [ (x,-y) for (x,y) in ellipse ]
61 ellipse2.reverse ()
83
62 ellipse.extend (ellipse2)
63
64 return [ (x + xc, y + yc) for (x,y) in ellipse ]
65
66 def display_ligne (ensemble, screen):
67 """affiche un ensemble de pixels à l'écran"""
68 color = 0,0,0
69 for p in ensemble:
70 pygame.draw.line (screen, color, p,p)
71 pygame.display.flip ()
72
73 def attendre_clic (screen):
74 """attend la pression d'un clic de souris pour continuer"""
75 reste = True
76 while reste:
77 for event in pygame.event.get():
78 if event.type == pygame.MOUSEBUTTONUP :
79 reste = False
80 break
81
82 if __name__ == "__main__" :
83 pygame.init ()
84
85 size = width, height = x,y = 300, 300
86 black = 0, 0, 0
87 white = 255,255,255
88 screen = pygame.display.set_mode(size)
89 screen.fill (white)
90
91 print trace_ellipse (0,0,6,6)
92 # pour le premier quart, affiche
93 # [(6, 0), (6, 1), (6, 2), (5, 3), (4, 4), (3, 5), (2, 6), (1, 6), (0, 6), ...
94
95 for n in xrange (0,10):
96 x1 = random.randint (0,x-1)
97 y1 = random.randint (0,y-1)
98 x2 = random.randint (0,x-1)
99 y2 = random.randint (0,y-1)
100 xc,yc = (x1 + x2) / 2 , (y1 + y2) / 2
101 a,b = abs (x2 - x1) / 2 , abs (y2 - y1) / 2
102 ell = trace_ellipse (xc,yc,a,b)
103 display_ligne (ell, screen)
104
105 attendre_clic (screen)
�n correction TD 5 ut
84
Fig. 18.22 � Illustration des deux programmes de tracé de lignes (4-connexité) et d'ellipses (8-connexité),algorithmes de Bresenham, sans multiplication ni division.
19 Correction du TD 6, page 15
Le programme qui suit reprend celui disponible à l'adresse http ://perso.wanadoo.fr/x.dupre/programmation/python_cours_exemple_programme_html/tsp_kruskal.html. Les fonctions d'a�chage ont été modi�éespour prendre en compte l'image chargée au début du programme. La fonction amelioration_chemin aété également modi�ée pour pouvoir arrêter l'optimisation et la reprendre d'un clic de souris. La pressionde la touche ECHAP permet d'interrompre l'optimisation et de terminer le programme par l'a�chage dumeilleur chemin à une échelle double. Le résultat obtenu avec le programme est présenté �gures 19.23et 19.24.
85
Fig. 19.23 � Dessin de Bette Davies obtenu avec le programme inclus dans le paragraphe 19. Les para-mètres choisis sont k = 3 et γ = 4, soit 18000 villes. Le programme a tourné une heure et demi sur unPentium IV cadencé à 1,6 GHz.
Fig. 19.24 � Même dessin que celui de la �gure 19.23 mais agrandi. Le visage apparaît lorsqu'on s'éloignede quelques mètres de l'écran.
86
1 # -*- coding: cp1252 -*-
2 import random # pour tirer aléatoirement des nombres
3 import math # fonctions cos, sin
4 import pygame # pour les affichages
5 import copy
6 import bresenham_ligne4 as brl # pour dessiner des lignes
7 import psyco # pour accélérer le programme
8
9 def attendre_clic (screen,x,y):
10 """dessine une croix sur l'écran et attend la pression d'un clic de souris"""
11 color = 0,0,0
12 pygame.draw.line (screen, color, (0,0), (x-1,y-1))
13 pygame.draw.line (screen, color, (x-1,0), (0,y-1))
14 pygame.display.flip ()
15 reste = True
16 while reste:
17 for event in pygame.event.get():
18 if event.type == pygame.MOUSEBUTTONUP :
19 reste = False
20 break
21
22 def ajuste_image (image, park):
23 """arrondi les dimensions d'une images à park, retourne une partie de l'image"""
24 x,y = image.get_size ()
25 x = (x // park) * park
26 y = (y // park) * park
27 image2 = image.subsurface (((0,0),(x,y)))
28 image3 = image2.copy ()
29 return image3
30
31 def construit_ville(image, gamma, park):
32 """tire aléatoirement des villes,
33 ces villes sont d'autant plus nombreuses que l'intensité de l'image
34 est faible, évite les villes confondues"""
35 x,y = image.get_size ()
36 nbx = x // park
37 nby = y // park
38
39 villes = []
40 for i in xrange(0,nbx):
41 for j in xrange(0,nby):
42 x1 = i * park
43 x2 = (i+1) * park
44 y1 = j * park
45 y2 = (j+1) * park
46
47 # calcul de l'obscurité moyenne
48 moy = 0
49 for k in xrange(x1,x2):
50 for l in xrange(y1,y2):
87
51 int = image.get_at ((k,l))
52 moy += int [0] + int [1] + int [2]
53 moy /= park * park * 3
54
55 # nombre de villes
56 nbv = gamma - gamma * moy / 256
57 pl = []
58
59 for k in xrange(0,nbv):
60 xx = random.randint (x1,x2-1)
61 yy = random.randint (y1,y2-1)
62 if (xx,yy) not in pl :
63 villes.append ((xx,yy))
64 pl.append ((xx,yy))
65
66 return villes
67
68 def display_ville(villes,screen):
69 """dessine les villes à l'écran"""
70 color = 0,0,0
71 for v in villes:
72 pygame.draw.line (screen, color, v, v)
73
74
75 def display_neurone(neurones_,screen,mult = 1):
76 """dessine les neurones à l'écran"""
77 color = 0,0,0
78 color2 = 0,255,0
79 if mult != 1 :
80 neurones = [ (n [0] * mult, n [1] * mult ) for n in neurones_ ]
81 if mult == 2 : l = 1
82 else : l = 1
83 for n in neurones :
84 pygame.draw.line (screen, color, n, n)
85 #pygame.draw.circle (screen, color2, neurones [0], 8)
86 if len (neurones) > 1 :
87 color3 = 150,0,0
88 #pygame.draw.circle (screen, color3, neurones [1], 6)
89 if len (neurones) > 1:
90 pygame.draw.lines (screen, color, True, neurones, l)
91 else :
92 neurones = [ (n [0] * mult, n [1] * mult ) for n in neurones_ ]
93 if mult == 2 : l = 1
94 else : l = 1
95 for n in neurones_ :
96 pygame.draw.line (screen, color, n, n)
97 #pygame.draw.circle (screen, color2, neurones [0], 8)
98 if len (neurones_) > 1 :
99 color3 = 150,0,0
100 #pygame.draw.circle (screen, color3, neurones [1], 6)
88
101 if len (neurones_) > 1:
102 pygame.draw.lines (screen, color, True, neurones_, l)
103
104 def display_arbre (villes, arbre, mult = 1):
105 """dessine le graphe de poids minimal défini par arbre"""
106 if mult == 2 :
107 color = 0,255,0
108 l = 4
109 else :
110 l = 1
111 color = 0,0,255
112
113 for i in xrange (0, len (villes)):
114 for j in arbre [i]:
115 v = (villes [i][0] * mult, villes [i][1] * mult)
116 vv = (villes [j][0] * mult, villes [j][1] * mult)
117 pygame.draw.line (screen, color, v, vv, l)
118
119
120 def repartition_zone (villes, zone_taille, ask_zone = False) :
121 """répartit les villes en zones, retourne les villes rangées par zones,
122 chaque éléments zones [z][k] contient :
123 - les coordonnées de la ville
124 - ses coordonnées en zone, (zx, zy)
125 - son indice dans la liste villes
126 la fonction retourne également le nombre de zones
127 selon l'axe des abscisses et l'axe des ordonnées,
128 retourne aussi le nombre de zones, si ask_zone est True,
129 retourne un paramètre supplémentaire : zone"""
130 print "gestion des zones"
131 X,Y = 0,0
132 for v in villes:
133 X = max (v [0] // zone_taille, X)
134 Y = max (v [1] // zone_taille, Y)
135 X += 1
136 Y += 1
137
138 # attribution des zones
139 zone = []
140 nb = len (villes)
141 Zmax = 0
142 for i in xrange (0,len (villes)):
143 v = villes [i]
144 x = int (v [0] // zone_taille)
145 y = int (v [1] // zone_taille)
146 z = int (y * X + x)
147 Zmax = max (z,Zmax)
148 zone.append ((z, v, (x,y), i))
149
150 # rangement par zone
89
151 Zmax += 1
152 zones = [ [] for i in xrange (0,Zmax) ]
153 for z in zone:
154 zones [ z [0] ].append ((z [1], z [2], z [3]))
155
156 if ask_zone :
157 return zones,X,Y,Zmax,zone
158 else :
159 return zones,X,Y,Zmax
160
161 def voisinage_zone (z,Zmax,X,Y):
162 """retourne la liste des voisins d'une zone z
163 sachant qu'il y a X zones sur l'axe des abscisses et Y zones sur l'axe des ordonnées,
164 Zmax est le nombre de zones,
165 inclus z dans cette liste"""
166 x = z % X
167 y = z // X
168 voisin_ = [z]
169 if x > 0: voisin_.append (z-1)
170 if x < X: voisin_.append (z+1)
171 if y > 0: voisin_.append (z-X)
172 if y < Y: voisin_.append (z+X)
173 if x > 0 and y > 0 : voisin_.append (z-1-X)
174 if x > 0 and y < Y : voisin_.append (z-1+X)
175 if x < X and y > 0 : voisin_.append (z+1-X)
176 if x < X and y < Y : voisin_.append (z+1+X)
177 voisin = [ int (i) for i in voisin_ if i >= 0 and i < Zmax ]
178 return voisin
179
180 def distance (p1,p2):
181 """calcule la distance entre deux villes"""
182 x = p1 [0] - p2[0]
183 y = p1 [1] - p2[1]
184 return math.sqrt (x*x + y*y)
185
186 def arbre_poids_minimal(villes, zone_taille):
187 """construit l'arbre de poids minimal, retourne une liste de
188 listes, chaque sous-liste associée à une ville contient la liste des ses voisins,
189 zone_taille permet de découper l'image en zones,
190 les distances ne seront calculées que si
191 deux éléments sont dans la même zone ou dans une zone voisine"""
192
193 def tri_distance (u,v):
194 if u [2] < v [2] : return -1
195 elif u [2] > v [2] : return 1
196 else : return 0
197
198 zones,X,Y,Zmax = repartition_zone (villes, zone_taille)
199
200 # calcul des distances
90
201 print "calcul des distances"
202 li = []
203
204 for z in xrange (0,len (zones)):
205 if z % 1000 == 0 : print "zone ", z, len(zones)
206 voisin = voisinage_zone (z,Zmax,X,Y)
207 for v in zones [z]:
208 for zz in voisin:
209 for u in zones [zz]:
210 d = distance (v [0], u [0])
211 li.append ((v [2], u [2], d))
212
213 print "tri ", len(li)
214 li.sort (tri_distance)
215
216 # composantes connexes
217 print "construction de l'arbre"
218
219 # nombre de composantes connexes
220 nb_comp = len (villes)
221
222 # indice de la composante d'une ville
223 num_comp = [ i for i in xrange(0,len(villes)) ]
224
225 # liste des voisins pour chaque ville
226 arbre = [ [] for i in xrange(0,len(villes)) ]
227
228 # liste des villes par composante connexe
229 list_comp = [ [i] for i in xrange(0,len(villes)) ]
230
231 iii = 0
232 for c in li:
233 if iii % 10000 == 0 : print "arête ", iii, len(li)
234 iii += 1
235 i,j = c [0], c [1]
236 if num_comp [i] != num_comp [j]:
237 # on relie les villes i et j car elles appartiennent
238 # à des composantes connexes différentes
239 arbre [i].append (j) # i est voisine de j
240 arbre [j].append (i) # j est voisine de i
241 cl = num_comp [i] # composante connexe restante
242 ki = num_comp [j] # composante connexe à aggréger à la précédente
243 for k in list_comp [ki]:
244 num_comp [k] = cl
245 list_comp [cl].append (k)
246 list_comp [ki] = []
247 nb_comp -= 1 # une composante connexe en moins
248
249 if nb_comp == 0:
250 break # il n'y a plus qu'une seule composante connexe, inutile de continuer
91
251
252 return arbre
253
254 def vecteur_points (p1,p2):
255 """retourne le vecteur entre les points p1 et p2"""
256 return ( p2 [0] - p1 [0], p2 [1] - p1 [1])
257
258 def vecteur_norme (vec):
259 """retourne la norme d'un vecteur"""
260 return math.sqrt (vec [0] * vec [0] + vec [1] * vec [1])
261
262 def vecteur_cosinus (vec1, vec2):
263 """retourne le cosinus entre deux vecteurs, utilise le produit scalaire"""
264 norm1 = vecteur_norme (vec1)
265 norm2 = vecteur_norme (vec2)
266 if norm1 == 0: return 1
267 if norm2 == 0: return 1
268 scal = vec1 [0] * vec2 [0] + vec1 [1] * vec2 [1]
269 return scal / (norm1 * norm2)
270
271 def vecteur_sinus (vec1, vec2):
272 """retourne le sinus entre deux vecteurs, utilise le produit vectoriel"""
273 norm1 = vecteur_norme (vec1)
274 norm2 = vecteur_norme (vec2)
275 if norm1 == 0: return 0
276 if norm2 == 0: return 0
277 scal = vec1 [0] * vec2 [1] - vec1 [1] * vec2 [0]
278 return scal / (norm1 * norm2)
279
280 def oppose_vecteur (vec):
281 """retourne le vecteur opposé"""
282 return (- vec [0], - vec [1])
283
284 def circuit_eulerien (villes, arbre):
285 """définit un circuit eulérien, villes contient la liste des villes,
286 tandis que arbre est une liste de listes, arbre [i] est la liste des villes
287 connectées à la ville i,
288 on suppose que arbre est un graphe de poids minimal non orienté,
289 l'algorithme ne marche pas s'il existe des villes confondues"""
290
291 # on choisit une ville qui est une extrémité et parmi celle-là on la choisit au hasard
292 has = []
293 for i in xrange (0,len (villes)):
294 n = len (arbre [i])
295 if n == 1: has.append (i)
296
297 bm = random.randint (0, len (has) -1)
298 bm = has [bm]
299
300 # vecteur, le circuit eulérien contient
92
301 # nécessairement 2 * len (villes) noeuds puisque c'est
302 # le graphe eulérien d'un arbre de poids minimal non orienté
303 vec = (1,1)
304 chemin = [bm]
305 while len (chemin) < 2 * len (villes)-1 :
306
307 v = villes [bm]
308
309 ma = - math.pi - 1
310 bvec = vec
311 opvec = oppose_vecteur (vec)
312 for k in xrange (0, len (arbre [bm])) :
313 l = arbre [bm][k]
314 vec2 = vecteur_points (v, villes [l])
315 if opvec == vec2 :
316 angle = -math.pi
317 else :
318 cos = vecteur_cosinus (vec, vec2)
319 sin = vecteur_sinus (vec, vec2)
320 angle = math.atan2 (sin, cos)
321 if angle > ma :
322 ma = angle
323 bl = k
324 bvec = vec2
325
326 b = arbre [bm][bl]
327 chemin.append (b)
328 del arbre [bm][bl] # on supprime l'arc pour ne plus l'utiliser
329 bm = b
330 vec = bvec
331
332 return chemin
333
334 def circuit_hamiltonien (chemin):
335 """extrait un circuit hamiltonien depuis un circuit eurlérien"""
336 nb = max (chemin) + 1
337 res = []
338 coche = [ False for i in xrange (0, nb) ]
339 for c in chemin :
340 if coche [c] : continue
341 res.append (c)
342 coche [c] = True
343
344 return res
345
346 def equation_droite (p1,p2) :
347 """retourne l'équation d'une droite passant par p1 et p2,
348 ax + by + c = 0, retourne les coefficients a,b,c"""
349 vec = vecteur_points (p1,p2)
350 a = vec [1]
93
351 b = - vec [0]
352 c = - a * p1 [0] - b * p1 [1]
353 return a,b,c
354
355 def evaluation_droite (a,b,c,p):
356 """l'équation d'une droite est : ax + by + c, retourne la valeur
357 de cette expression au point p"""
358 return a * p [0] + b * p [1] + c
359
360 def intersection_segment (p1,p2,p3,p4):
361 """dit si les segments [p1 p2] et [p3 p4] ont une intersection,
362 ne retourne pas l'intersection"""
363 # équation de la droite (p1 p2)
364 a1,b1,c1 = equation_droite (p1,p2)
365 a2,b2,c2 = equation_droite (p3,p4)
366 s1 = evaluation_droite (a2,b2,c2,p1)
367 s2 = evaluation_droite (a2,b2,c2,p2)
368 s3 = evaluation_droite (a1,b1,c1,p3)
369 s4 = evaluation_droite (a1,b1,c1,p4)
370 if s1 * s2 <= 0 and s3 * s4 <= 0 : return True
371 else : return False
372
373 def longueur_chemin (chemin):
374 """retourne la longueur d'un chemin"""
375 s = 0
376 nb = len (chemin)
377 for i in xrange (0,nb) :
378 s += distance ( chemin [i], chemin [ (i+1) % nb ])
379 return s
380
381 def retournement_essai (chemin, i,j, negligeable = 1e-5):
382 """dit s'il est judicieux de parcourir le chemin entre les sommets i et j
383 en sens inverse, si c'est judicieux, change le chemin et retourne True,
384 sinon, retourne False,
385 si j < i, alors la partie à inverser est
386 i, i+1, i+2, ..., len(chemin) -1, 0, 1, ..., j"""
387
388 nb = len (chemin)
389 if i == j : return False
390 if j - i == -1 : return False
391 if j - i - nb == -1 : return False
392
393 ia = (i - 1 + nb) % nb
394 ja = (j + 1 ) % nb
395 # arcs enlevés
396 d_ia_i = distance (chemin [ia], chemin [i])
397 d_j_ja = distance (chemin [j], chemin [ja])
398 # arcs ajoutés
399 d_ia_j = distance (chemin [ia], chemin [j])
400 d_i_ja = distance (chemin [i], chemin [ja])
94
401 # amélioration ?
402 d = d_ia_j + d_i_ja - d_j_ja - d_ia_i
403 if d >= - negligeable : return False
404
405 # si amélioration, il faut retourner le chemin entre les indices i et j
406 jp = j
407 if jp < i : jp = j + nb
408 ip = i
409
410 while ip < jp :
411 i = ip % nb
412 j = jp % nb
413 ech = chemin [i]
414 chemin [i] = chemin [j]
415 chemin [j] = ech
416 ip = ip+1
417 jp = jp-1
418
419 return True
420
421 def retournement (chemin, taille) :
422 """amélioration du chemin par un algorithme simple,
423 utilise des retournements de taille au plus <taille>,
424 retourne le nombre de modifications"""
425
426 # traitement des petits retournements
427 nb = len (chemin)
428 nb_change = 1
429 nbtout = 0
430 retour = { }
431 while nb_change > 0 :
432 nb_change = 0
433 for t in xrange (1,taille+1):
434 retour [t] = 0
435 for i in xrange (0, nb) :
436 j = (i + t) % nb
437 b = retournement_essai (chemin, i, j)
438 if b :
439 retour [t] += 1
440 nb_change += 1
441 nbtout += nb_change
442 print "nombre de retournements %d longueur : \t %10.0f détail \t" \
443 % (nbtout, longueur_chemin (chemin)), " détail : ", retour
444 return nbtout
445
446 def echange_position_essai (chemin, a,b, x, inversion, negligeable = 1e-5):
447 """échange la place des villes ka à kb pour les placer entre les villes i et i+1,
448 si inversion est True, on inverse également le chemin inséré, si inversion est False,
449 on ne l'inverse pas,
450 si cela améliore, déplace les villes et retourne True, sinon, retourne False"""
95
451
452 nb = len(chemin)
453 xa = (x + 1) % nb
454 ka = (a - 1 + nb) % nb
455 kb = (b + 1 ) % nb
456
457 if not inversion :
458
459 if x == ka : return False
460 if x == kb : return False
461 if xa == ka : return False
462 if b < a :
463 if a <= x <= b + nb : return False
464 elif a <= x <= b : return False
465 if b < a :
466 if a <= x + nb <= b + nb : return False
467 elif a <= x + nb <= b : return False
468
469 # arcs enlevés
470 d_x_xa = distance (chemin [x], chemin [xa])
471 d_ka_a = distance (chemin [ka], chemin [a])
472 d_b_kb = distance (chemin [b], chemin [kb])
473 # arcs ajoutés
474 d_ka_kb = distance (chemin [ka], chemin [kb])
475 d_x_a = distance (chemin [x], chemin [a])
476 d_b_xa = distance (chemin [b], chemin [xa])
477
478 d = d_ka_kb + d_x_a + d_b_xa - d_x_xa - d_ka_a - d_b_kb
479 if d >= -negligeable : return False
480
481 # villes à déplacer
482 ech = []
483 bp = b
484 if bp < a : bp = b + nb
485 for i in xrange (a,bp+1):
486 ech.append (chemin [i % nb] )
487 diff = bp - a + 1
488
489 xp = x
490 if xp < b : xp += nb
491
492 for l in xrange (b+1,xp+1) :
493 ll = l % nb
494 bp = (a + l - b-1) % nb
495 chemin [bp] = chemin [ll]
496
497 for l in xrange (0,len(ech)) :
498 chemin [ (x+l-diff+1 + nb) % nb ] = ech [l]
499
500 return True
96
501
502 else :
503
504 if x == ka : return False
505 if x == kb : return False
506 if xa == ka : return False
507 if b < a :
508 if a <= x <= b + nb : return False
509 elif a <= x <= b : return False
510 if b < a :
511 if a <= x + nb <= b + nb : return False
512 elif a <= x + nb <= b : return False
513
514
515 # arcs enlevés
516 d_x_xa = distance (chemin [x], chemin [xa])
517 d_ka_a = distance (chemin [ka], chemin [a])
518 d_b_kb = distance (chemin [b], chemin [kb])
519 # arcs ajoutés
520 d_ka_kb = distance (chemin [ka], chemin [kb])
521 d_x_b = distance (chemin [x], chemin [b])
522 d_a_xa = distance (chemin [a], chemin [xa])
523
524 d = d_ka_kb + d_x_b + d_a_xa - d_x_xa - d_ka_a - d_b_kb
525 if d >= -negligeable : return False
526
527 # villes à déplacer
528 ech = []
529 bp = b
530 if bp < a : bp = b + nb
531 for i in xrange (a,bp+1):
532 ech.append (chemin [i % nb] )
533 ech.reverse ()
534 diff = bp - a + 1
535
536 cop = copy.copy (chemin)
537
538 xp = x
539 if xp < b : xp += nb
540
541 for l in xrange (b+1,xp+1) :
542 ll = l % nb
543 bp = (a + l - b-1) % nb
544 chemin [bp] = chemin [ll]
545
546 for l in xrange (0,len(ech)) :
547 chemin [ (x+l-diff+1 + nb) % nb ] = ech [l]
548
549 return True
550
97
551 def dessin_arete_zone (chemin, taille_zone, X,Y):
552 """retourne une liste de listes de listes,
553 res [i][j] est une liste des arêtes passant près de la zone (x,y) = [i][j],
554 si k in res [i][j], alors l'arête k,k+1 est dans la zone (i,j),
555 X est le nombre de zones horizontalement, Y est le nombre de zones verticalement,
556 taille_zone est la longueur du côté du carré d'une zone"""
557 res = [ [ [] for j in xrange (0,Y+1) ] for i in xrange (0,X+1) ]
558 nb = len (chemin)
559 for i in xrange (0,nb):
560 a = chemin [i]
561 b = chemin [(i+1) % nb]
562 x1,x2 = int (a [0] // taille_zone), int (b [0] // taille_zone)
563 y1,y2 = int (a [1] // taille_zone), int (b [1] // taille_zone)
564 line = brl.trace_ligne (x1,y1,x2,y2)
565 for x,y in line:
566 res [x][y].append (i)
567 return res
568
569 def voisinage_zone_xy (x,y,X,Y):
570 """retourne la liste des voisins d'une zone (x,y)
571 sachant qu'il y a X zones sur l'axe des abscisses et Y zones sur l'axe des ordonnées,
572 inclus z dans cette liste"""
573 voisin = [(x,y)]
574 if x > 0 : voisin.append ((x-1,y))
575 if x < X-1 : voisin.append ((x+1,y))
576 if y > 0 : voisin.append ((x,y-1))
577 if y < Y-1 : voisin.append ((x,y+1))
578 if x > 0 and y > 0 : voisin.append ((x-1,y-1))
579 if x > 0 and y < Y-1 : voisin.append ((x-1,y+1))
580 if x < X-1 and y > 0 : voisin.append ((x+1,y-1))
581 if x < X-1 and y < Y-1 : voisin.append ((x+1,y+1))
582 return voisin
583
584 def echange_position (chemin, taille, taille_zone, X,Y, grande = 0.5) :
585 """regarde si on ne peut pas déplacer un segment de longueur taille
586 pour supprimer les arêtes les plus longues,
587 au maximum <grande> longues arêtes,
588 retourne le nombre de changement effectués,
589 X est le nombre de zones horizontalement,
590 Y est le nombre de zones verticalement,
591 taille_zone est la longueur d'un côté du carré d'une zone"""
592
593 nb = len(chemin)
594
595 def tri_arete (x,y):
596 """pour trier la liste l par ordre décroissant"""
597 if x [2] < y [2] : return 1
598 elif x [2] > y [2] : return -1
599 else : return 0
600
98
601 # list des arêtes triés par ordre décroissant
602 la = []
603 for i in xrange (0,nb) :
604 im = (i+1) % nb
605 la.append ( (i, im, distance (chemin [i], chemin [im]) ) )
606 la.sort (tri_arete)
607
608 # zone associé à chaque arête
609 zone = dessin_arete_zone (chemin, taille_zone, X, Y)
610
611 dseuil = la [ int (nb * grande) ] [ 2 ]
612 nbtout = 0
613 nb_change = 0
614 iarete = 0
615 retour = { }
616 for t in xrange (1, taille+1): retour [t] = 0
617
618 while iarete < nb :
619 nb_change = 0
620 arete = la [iarete]
621 iarete += 1
622 x = arete [0]
623 xm = arete [1]
624 a = chemin [x]
625 b = chemin [xm]
626 d = distance ( a,b )
627 if d < dseuil : break # arête trop petite
628
629 # zone traversée par la ligne
630 x1,x2 = int (a [0] // taille_zone), int (b [0] // taille_zone)
631 y1,y2 = int (a [1] // taille_zone), int (b [1] // taille_zone)
632 ens = brl.trace_ligne (x1,y1,x2,y2)
633 ville = []
634 for k,l in ens:
635 voisin = voisinage_zone_xy (k,l,X,Y)
636 for u,v in voisin :
637 ville.extend (zone [u][v])
638
639 # on supprime les doubles
640 ville.sort ()
641 if len (ville) == 0 : continue
642 sup = []
643 mx = -1
644 for v in ville:
645 if v == mx : sup.append (v)
646 mx = v
647 for s in sup:
648 ville.remove (s)
649
650 # on étudie les possibilités de casser l'arête (x,xm) aux alentours des villes
99
651 # comprise dans l'ensemble ville
652 for t in xrange (1, taille+1):
653
654 for i in ville:
655
656 # on essaye d'insérer le sous-chemin (x- t + 1 + nb) --> x
657 # au milieu de l'arête i,i+1
658 b = echange_position_essai (chemin, (x- t + 1 + nb) % nb,x, i, False)
659 if b :
660 nb_change += 1
661 retour [t] += 1
662 continue
663
664 # on essaye d'insérer le sous-chemin (xm+ t - 1) --> xm
665 # au milieu de l'arête i,i+1
666 b = echange_position_essai (chemin, (xm + t - 1) % nb, xm, i, False)
667 if b :
668 nb_change += 1
669 retour [t] += 1
670 continue
671
672 # on essaye de casser l'arête x,xm en insérant
673 # le sous-chemin i --> (i+t) % nb
674 b = echange_position_essai (chemin, i, (i+t) % nb, x, False)
675 if b :
676 nb_change += 1
677 retour [t] += 1
678 continue
679 # idem
680 b = echange_position_essai (chemin, i, (i+t) % nb, x, True)
681 if b :
682 retour [t] += 1
683 nb_change += 1
684 continue
685 # idem
686 b = echange_position_essai (chemin, (i-t+nb) % nb, i, x, False)
687 if b :
688 nb_change += 1
689 retour [t] += 1
690 continue
691 # idem
692 b = echange_position_essai (chemin, (i-t + nb) % nb, i, x, True)
693 if b :
694 retour [t] += 1
695 nb_change += 1
696 continue
697
698 nbtout += nb_change
699
700 print "nombre de déplacements %d longueur : \t %10.0f détail \t" \
100
701 % (nbtout, longueur_chemin (chemin)), " détail : ", retour
702 return nbtout
703
704 def supprime_croisement (chemin, taille_zone, X,Y) :
705 """supprime les croisements d'arêtes,
706 retourne le nombre de changement effectués,
707 X est le nombre de zones horizontalement,
708 Y est le nombre de zones verticalement,
709 taille_zone est la longueur d'un côté du carré d'une zone"""
710
711 nb = len(chemin)
712
713 # zone associé à chaque arête
714 zone = dessin_arete_zone (chemin, taille_zone, X, Y)
715 nbtout = 0
716
717 for i in xrange (0,nb) :
718 im = (i+1) % nb
719 a = chemin [i]
720 b = chemin [im]
721
722 # zone traversée par la ligne
723 x1,x2 = int (a [0] // taille_zone), int (b [0] // taille_zone)
724 y1,y2 = int (a [1] // taille_zone), int (b [1] // taille_zone)
725 ens = brl.trace_ligne (x1,y1,x2,y2)
726 ville = []
727 for k,l in ens:
728 voisin = voisinage_zone_xy (k,l,X,Y)
729 for u,v in voisin :
730 ville.extend (zone [u][v])
731
732 # on supprime les doubles
733 ville.sort ()
734 if len (ville) == 0 : continue
735 sup = []
736 mx = -1
737 for v in ville:
738 if v == mx : sup.append (v)
739 mx = v
740 for s in sup:
741 ville.remove (s)
742
743 nb_change = 0
744 for v in ville :
745 b = retournement_essai (chemin, i,v)
746 if b :
747 nb_change += 1
748 continue
749 b = retournement_essai (chemin, im,v)
750 if b :
101
751 nb_change += 1
752 continue
753
754 nbtout += nb_change
755
756 print "nombre de croisements %d longueur : \t %10.0f détail \t" \
757 % (nbtout, longueur_chemin (chemin))
758 return nbtout
759
760 def amelioration_chemin (chemin, taille_zone, X, Y, taille = 10, \
761 screen = None, image = None):
762 """amélioration du chemin par un algorithme simple,
763 utilise des retournements de taille au plus taille,
764 traite les arcs qui se croisent,
765 traite les grands arcs, utilise un quadrillage de taille window,
766 X est le nombre de zones horizontalement,
767 Y est le nombre de zones verticalement,
768 taille_zone est la longueur d'un côté du carré d'une zone"""
769
770 white = 255,255,255
771
772 #première étape rapide
773 nb = 1
774 while nb > 0:
775 nb = retournement (chemin, taille)
776 if screen != None:
777 screen.fill (white)
778 display_neurone(chemin, screen, 1)
779 pygame.display.flip ()
780
781 # amélioration
782 nb = 1
783 size = image.get_size ()
784 dec = size [0]
785 fin = False
786 while nb > 0 and not fin :
787 nb = retournement (chemin, taille)
788 if screen != None:
789 screen.fill (white)
790 if image != None : screen.blit (image, (dec,0))
791 display_neurone(chemin, screen)
792 pygame.display.flip ()
793 nb += echange_position (chemin, taille / 2, taille_zone, X, Y)
794 if screen != None:
795 screen.fill (white)
796 if image != None : screen.blit (image, (dec,0))
797 display_neurone(chemin, screen)
798 pygame.display.flip ()
799 nb += supprime_croisement (chemin, taille_zone,X,Y)
800 if screen != None:
102
801 screen.fill (white)
802 if image != None : screen.blit (image, (dec,0))
803 display_neurone(chemin, screen)
804 pygame.display.flip ()
805
806 if screen != None :
807 for event in pygame.event.get():
808 if event.type == pygame.MOUSEBUTTONUP :
809 print "attendre.............................................."
810 attendre_clic (screen,0,0)
811 print "reprise"
812 break
813 if event.type == pygame.KEYDOWN and event.key == 27 :
814 # si la touche ECHAP est pressée, l'optimisation s'arrête
815 print "..............arrêter l'optimisation"
816 fin = True
817 break
818
819
820 ################################################################################
821
822 if __name__ == "__main__" :
823 pygame.init ()
824 psyco.full ()
825
826 gamma = 4
827 park = 3
828
829 image2 = pygame.image.load("bette_davis.png")
830 image = ajuste_image (image2, park)
831
832 size = image.get_size ()
833 xx,yy = size [0], size [1]
834 X,Y = int (xx // park) + 1, int (yy // park) + 1
835 dec = size [0]
836 size = (size [0] * 2, size [1])
837 size = width, height = x,y = size
838 black = 0, 0, 0
839 white = 255,255,255
840 screen = pygame.display.set_mode(size)
841 villes = construit_ville (image, gamma, park)
842
843 print "taille de l'image : ", size
844 print "nombre de villes : ", len(villes)
845
846 screen.fill (white)
847 screen.blit (image, (dec,0))
848 display_ville (villes, screen)
849 pygame.display.flip ()
850
103
851 print "calcul"
852 arbre = arbre_poids_minimal (villes,park)
853 arbre2 = copy.deepcopy (arbre)
854
855 print "dessin"
856 display_arbre (villes, arbre)
857 attendre_clic(screen,0,0)
858
859 print "circuit eulérien"
860 chemin = circuit_eulerien (villes ,arbre)
861
862 print "circuit hamiltonien"
863 neurone = circuit_hamiltonien (chemin)
864
865 print "dessin"
866 neurones = [ villes [i] for i in neurone ]
867 display_neurone(neurones, screen)
868 attendre_clic(screen,0,0)
869
870 print "amélioration"
871 amelioration_chemin (neurones, park, X,Y, 6, screen, image)
872 attendre_clic(screen,0,0)
873
874 # taille double
875 print "taille double"
876 size = (size [0], size [1]*2)
877 screen = pygame.display.set_mode(size)
878 screen.fill (white)
879 #display_arbre (villes, arbre2, 2)
880 display_neurone (neurones, screen, 2)
881 attendre_clic(screen,0,0)
�n correction TD 6 ut
104
20 Correction du TD 7, page 18
Le �chier image_synthese_facette_image.py contient la réponse aux deux questions de l'énoncé de ceTD. La scène qui y est incluse en exemple contient à la fois une facette rectangulaire dont la surface estune image et une sphère en partie ré�échissante puisqu'elle ré�échit un rayon d'une intensité diminué demoitié par rapport à celle du rayon incident.
1)La classe rectangle_image est un nouvel objet qui hérite de la classe rectangle du �chierimage_synthese_facette.py. Le comportement de ce nouvel objet est identique à celui d'un rectangle,seule la couleur n'est plus uniforme le long de la surface (méthode couleur_point) puisqu'elle est obtenuedepuis une image. La phase d'initialisation change aussi pour charger l'image.
Le fonction couleur_point considère que les vecteurs−−→AB et
−−→AD forment le repère dans lequel sera
a�chée l'image. Cette fonction calcule la correspondance entre les coordonnées du point d'intersectionavec un rayon de lumière et le pixel de l'image qui doit y être a�ché.
2)La classe sphere_reflet redé�nit la méthode rayon_reflechi a�n de retourner un rayon ré�échidé�ni par l'expression (7.2) (page 19). Le paramètre reflet présent dans le constructeur __init__ dela classe sphere_reflet permet de dé�nir l'intensité lumineuse ré�échie par la surface. Pour l'exemplede scène incluse dans ce programme, l'intensité du rayon ré�échi est la moitié de celle du rayon incident.
Fichier : image_synthese_facette_image.py
1 # -*- coding: cp1252 -*-
2 """définition d'une sphère"""
3 import image_synthese_base as base
4 import image_synthese_sphere as obj
5 import image_synthese_phong as scene
6 import image_synthese_scene as scene_p
7 import image_synthese_facette as facette
8 import pygame
9 import math
10 import psyco
11
12
13
14 class rectangle_image (facette.rectangle):
15 """définit un rectangle contenant un portrait"""
16
17 def __init__(self, a,b,c,d, nom_image, invertx = False):
18 """initialisation, si d == None, d est calculé comme étant
19 le symétrique de b par rapport au milieu du segment [ac],
20 la texture est une image,
21 si invertx == True, inverse l'image selon l'axe des x"""
22 facette.rectangle.__init__(self, a,b,c,d, base.couleur (0,0,0))
23 self.image = pygame.image.load (nom_image)
24 self.nom_image = nom_image
25 self.invertx = invertx
26
27 def __str__ (self):
28 """affichage"""
29 s = "rectangle image --- a : " + str (self.a)
105
30 s += " b : " + str (self.b)
31 s += " c : " + str (self.c)
32 s += " d : " + str (self.d)
33 s += " image : " + self.nom_image
34 return s
35
36 def couleur_point (self, p) :
37 """retourne la couleur au point de coordonnée p"""
38 ap = p - self.a
39 ab = self.b - self.a
40 ad = self.d - self.a
41 abn = ab.norme2 ()
42 adn = ad.norme2 ()
43 x = ab.scalaire (ap) / abn
44 y = ad.scalaire (ap) / adn
45 sx,sy = self.image.get_size ()
46 k,l = int (x * sx), int (y * sy)
47 k = min (k, sx-1)
48 l = min (l, sy-1)
49 l = sy - l - 1
50 if not self.invertx :
51 c = self.image.get_at ((k,l))
52 else :
53 c = self.image.get_at ((sx-k-1,l))
54 cl = base.couleur (float (c [0]) / 255, float (c [1]) / 255, float (c [2]) / 255)
55 return cl
56
57 class sphere_reflet (obj.sphere) :
58 """implémente une sphère avec un reflet"""
59
60 def __init__ (self, centre, rayon, couleur, reflet):
61 """initialisation, reflet est un coefficient de réflexion"""
62 obj.sphere.__init__ (self, centre, rayon, couleur)
63 self.reflet = reflet
64
65 def __str__ (self):
66 """affichage"""
67 s = "sphère reflet --- centre : " + str (self.centre)
68 s += " rayon : " + str (self.rayon)
69 s += " couleur : " + str (self.couleur)
70 return s
71
72 def rayon_reflechi (self, rayon, p) :
73 """retourne le rayon réfléchi au point p de la surface,
74 si aucune, retourne None"""
75 if p == rayon.origine : return None
76 n = self.normale (p, rayon)
77 n = n.renorme ()
78 y = n.scalaire (rayon.direction)
79 d = rayon.direction - n * y * 2
106
80 r = base.rayon (p, d, rayon.pixel, rayon.couleur * self.reflet)
81 return r
82
83
84 if __name__ == "__main__" :
85
86 psyco.full ()
87
88 s = scene.scene_phong (base.repere (), math.pi / 1.5, 400, 200)
89
90 s.ajoute_source ( base.source (base.vecteur (0,8,8), \
91 base.couleur (0.4,0.4,0.4) ) )
92 s.ajoute_source ( base.source (base.vecteur (10,0,0), \
93 base.couleur (0.4,0.4,0.4) ) )
94 s.ajoute_source ( base.source (base.vecteur (8,8,4.5), \
95 base.couleur (0.4,0.4,0.4) ) )
96 s.ajoute_objet ( obj.sphere (base.vecteur (3,-4,7), \
97 1, base.couleur (1,0,0) ) )
98 s.ajoute_objet ( sphere_reflet (base.vecteur (0,-400,12), \
99 396, base.couleur (0.5,0.5,0.5), 0.5 ) )
100
101 s.ajoute_objet (rectangle_image ( base.vecteur (8,-3.5,9), \
102 base.vecteur (2,-3.5,8), \
103 base.vecteur (2,3.8,8), \
104 None, \
105 "bette_davis.png",
106 invertx = True))
107
108 s.ajoute_source ( base.source (base.vecteur (7,2,8), \
109 base.couleur (0.2,0.2,0.2) ) )
110 s.ajoute_source ( base.source (base.vecteur (12.5,3,5), \
111 base.couleur (0.2,0.2,0.2) ) )
112
113 s.ajoute_source ( base.source (base.vecteur (-12.5,1,6), \
114 base.couleur (0.2,0.2,0.2) ) )
115
116 s.ajoute_objet (facette.rectangle ( base.vecteur (-12.4,0.99,5.9), \
117 base.vecteur (-12.6,0.99,5.9), \
118 base.vecteur (-12.6,0.99,6.1), \
119 None, \
120 base.couleur (0,0,0)))
121
122 print s
123
124 screen = pygame.display.set_mode (s.dim)
125 screen.fill ((255,255,255))
126 s.construit_image (screen)
127
128 print "sauvegarde de l'image"
129 im = pygame.display.get_surface()
107
130 print "image size : ", im.get_size ()
131 pygame.image.save (im, "c:\\temp\\image.jpg")
132 pygame.image.save (im, "c:\\temp\\image.tif")
133 pygame.image.save (im, "c:\\temp\\image.bmp")
134
135 print "image terminée"
136 scene_p.attendre_clic ()
137
138
139
140
�n correction TD 7 ut
108
21 Correction du TD 8, page 36
Le programme qui suit répond aux trois questions de l'énoncé de ce TD ainsi qu'à la question subsidiairepar l'intermédiaire de la méthode repertoire_selectionne. Cette dernière détermine si un �chier d'uneliste file_clean est inclus dans un répertoire r. Ce programme recopie tous les �chiers inclus dans lerépertoire C :/Documents and Settings/Dupré/Mes documents/informatique/support/python_td vers lerépertoire c :/temp/copie_usb. Les �chiers dont les extensions sont pdf, html et bmp ne sont pas recopiés.Les �chiers dont l'extension est zip et inclus dans le répertoire programme ne sont pas non plus récopiés.
1 # -*- coding: cp1252 -*-
2 """copie de fichiers sur une clé USB"""
3
4 import re # pour les expressions régulières
5 import os # pour les fichiers et répertoires
6 import os.path # pour les noms de fichiers et noms de répertoires
7 import copy
8 import shutil # pour la copie de fichiers
9
10 class copie_usb (object):
11 """recopie des fichiers sur une clé USB"""
12
13 def __init__(self,ch1,ch2,accept = ".*",refuse = "") :
14 """initialisation,
15 @param ch1 répertoire source
16 @param ch2 répertoire destination
17 @param accept filtre pour les fichiers acceptés pour la copie
18 @param refuse pour refuser des fichiers parmi ceux déjà acceptés"""
19 self.ch1 = ch1
20 self.ch2 = ch2
21 self.accept = re.compile (accept, re.IGNORECASE) # création des motifs
22 self.refuse = re.compile (refuse, re.IGNORECASE) # création des motifs
23
24 def accepter (self, fichier) :
25 """dit si un fichier est accepté à la copie ou non"""
26 r = re.match (self.accept, fichier)
27 if not r : return False
28 r = re.match (self.refuse, fichier)
29 return not r
30
31 def aide (self) :
32 """retourne une aide sur les formats d'expression"""
33 help (re.engine)
34
35 def liste_fichier_repertoire (self,repertoire):
36 """récupération de la liste des répertoires et celle des fichiers,
37 inclus dans le répertoire repertoire"""
38 rep = []
39 file = []
40 list = os.listdir (repertoire)
109
41
42 for cc in list :
43 c = repertoire + "\\" + cc
44 if os.path.isfile (c) : file.append (cc)
45 if os.path.isdir (c) : rep.append (cc)
46
47 rep2 = copy.copy (rep)
48 for chemin in rep2 :
49 r,f = self.liste_fichier_repertoire (repertoire + "\\" + chemin)
50 for x in r :
51 rep.append (chemin + "\\" + x)
52 for x in f :
53 file.append (chemin + "\\" + x)
54
55 return rep,file
56
57 def repertoire_selectionne (self, r, file_clean) :
58 """dit si la liste file_clean contient au moins un fichier
59 inclus dans le repertoire r"""
60 t = re.compile ("^" + r + "\\\\.*", re.IGNORECASE)
61 for l in file_clean :
62 if re.match (t,l) : return True
63 return False
64
65 def copie (self) :
66 """effectue la copie"""
67
68 # récupération de la liste des répertoires et fichiers
69 rep,file = self.liste_fichier_repertoire (self.ch1)
70 # élimination des importuns
71 file_clean = [ f for f in file if self.accepter (f) ]
72
73 # facultatif, exclue les répertoires pour lesquels aucun fichier n'est sélectionné
74 rep_clean = [ r for r in rep if self.repertoire_selectionne (r, file_clean) ]
75
76 # on créé les répertoires s'il n'existent pas
77 if not os.path.exists (self.ch2) :
78 print "création du répertoire ", self.ch2
79 os.mkdir (self.ch2)
80
81 for r in rep_clean :
82 c = self.ch2 + "\\" + r
83 if not os.path.exists (c) :
84 print "création du répertoire ", r
85 os.mkdir (c)
86
87 # on recopie les fichiers
88 for f in file_clean :
89 s = self.ch1 + "\\" + f
90 c = self.ch2 + "\\" + f
110
91 print "copie du fichier ", f
92 shutil.copy (s, c)
93
94
95 if __name__ == "__main__" :
96 print "copie de fichiers vers une clé USB"
97 ch1 = "C:\\Documents and Settings\\Dupré\\" \
98 "Mes documents\\informatique\\support\\python_td"
99 ch2 = "c:\\temp\\copie_usb"
100 filtre_accept = ".*[.].*"
101 filtre_refuse = ".*[.]pdf$|.*[.]html$|.*[.]bmp|programme\\\\.*[.]zip$"
102
103 # filtre_accept accepte tout type de fichier
104 # filtre_refuse refuse tous les fichiers dont l'extension est pdf, html ou
105 # inclus dans le répertoire programme et ayant l'extension zip
106
107 c = copie_usb (ch1, ch2, filtre_accept, filtre_refuse)
108 c.copie ()
109
�n correction TD 8 ut
111
22 Correction du TD 9, page 39
Le programme qui suit répond aux deux questions de l'énoncé de ce TD ainsi qu'à la question subsidiaire.La classe copie_usb_window hérite de la classe copie_usb dé�nie lors de la correction du TD 8 (page 21).Il ajoute deux méthodes, la première chercher permet de sélectionner un répertoire à l'aide d'une fenêtre(voir �gure 9.11, page 43) implémentée dans le �chier selection_file.py. La seconde méthode fenetrecrée une fenêtre (voir �gure 9.7, page 39) qui permet de modi�er les répertoires source et destination, lesdeux �ltres puis de lancer la copie. Cette présentation est celle suggérée par la première question.
1 # -*- coding: cp1252 -*-
2 """copie de fichiers sur une clé USB, interface fenêtrée"""
3
4 import Tkinter as Tk # pour la fenêtre
5 import selection_file # pour rechercher un répertoire
6 import copie_usb # version sans fenêtre
7 import re # pour les expressions régulières
8
9 class copie_usb_window (copie_usb.copie_usb):
10 """recopie des fichiers sur une clé USB avec une fenêtre graphique"""
11
12 def chercher (self, s, titre) :
13 """modifie un répertoire"""
14 fs = selection_file.FileSelection (titre, chemin = s, file = False)
15 r = fs.run ()
16 if r != None : return r
17 else : return s
18
19 def fenetre (self) :
20 """change les paramètres de la classe par l'intermédiaire d'une fenêtre"""
21
22 # définition de la fenêtre
23 root = Tk.Tk ()
24
25 source = Tk.Entry (width = 100)
26 source_label = Tk.Label (text = "répertoire source")
27 source_label.grid (column = 0, row = 0)
28 source.grid (column = 1, row = 0)
29
30 dest = Tk.Entry (width = 100)
31 dest_label = Tk.Label (text = "répertoire destination")
32 dest_label.grid (column = 0, row = 1)
33 dest.grid (column = 1, row = 1)
34
35 filtre_accept = Tk.Entry (width = 100)
36 accept_label = Tk.Label (text = "filtre pour les fichiers acceptés")
37 filtre_accept.grid (column = 1, row = 2)
38 accept_label.grid (column = 0, row = 2)
39
40 filtre_refuse = Tk.Entry (width = 100)
112
41 refuse_label = Tk.Label (text = "filtre pour les fichiers refusés")
42 filtre_refuse.grid (column = 1, row = 3)
43 refuse_label.grid (column = 0, row = 3)
44
45 def chercher_source () :
46 s = source.get ()
47 i = len (s)
48 s = self.chercher (s, "répertoire source")
49 source.delete (0, i)
50 source.insert (0,s)
51
52 def chercher_dest () :
53 s = dest.get ()
54 i = len (s)
55 s = self.chercher (s, "répertoire source")
56 dest.delete (0, i)
57 dest.insert (0,s)
58
59 def copier () :
60 self.ch1 = source.get ()
61 self.ch2 = dest.get ()
62 self.accept = re.compile (filtre_accept.get ())
63 self.refuse = re.compile (filtre_refuse.get ())
64 self.copie ()
65
66 brepsource = Tk.Button (text = "chercher", command = chercher_source)
67 brepdest = Tk.Button (text = "chercher", command = chercher_dest)
68 brepsource.grid (column = 2, row = 0)
69 brepdest.grid (column = 2, row = 1)
70
71 bfermer = Tk.Button (text = "Fermer", command = root.destroy)
72 bfermer.grid (column = 2, row = 4)
73 bcopier = Tk.Button (text = "Copier", command = copier)
74 bcopier.grid (column = 2, row = 3)
75
76 root.wm_title ("copie de fichiers vers une clé USB")
77
78 source.insert (0, self.ch1)
79 dest.insert (0, self.ch2)
80 filtre_accept.insert (0, self.accept.pattern)
81 filtre_refuse.insert (0, self.refuse.pattern)
82
83 root.mainloop ()
84
85
86 if __name__ == "__main__" :
87 print "copie de fichiers vers une clé USB"
88 ch1 = "C:\\Documents and Settings\\Dupré\\" \
89 "Mes documents\\informatique\\support\\python_td"
90 ch2 = "c:\\temp\\copie_usb"
113
91 filtre_accept = ".*[.].*"
92 filtre_refuse = ".*[.]pdf$|.*[.]html$|.*[.]bmp|programme\\\\.*[.]zip$"
93
94 # filtre_accept accepte tout type de fichier
95 # filtre_refuse refuse tous les fichiers dont l'extension est pdf, html ou
96 # inclus dans le répertoire programme et ayant l'extension zip
97
98 c = copie_usb_window (ch1, ch2, filtre_accept, filtre_refuse)
99 c.fenetre ()
100
101
102
�n correction TD 9 ut
114
23 Correction du TD 10, page 48
Le programme qui suit répond aux deux questions de l'énoncé de ce TD. La classecopie_usb_window_save hérite de la classe copie_usb_window dé�nie lors de la correction du TD 9(page 22). Il ajoute deux méthodes, la première ecrire_parametre permet d'écrire les quatre paramètresde la classe copie_usb dé�nie au TD 8 (correction page 109). La méthode lire_parametre permetde les relire. En�n, la fonction fenetre de la classe copie_usb_window est surchargée dans la classecopie_usb_window_save d'appeler les deux méthodes précédentes avant et après l'a�chage de l'inter-face graphique.
1 # -*- coding: cp1252 -*-
2 """copie de fichiers sur une clé USB, interface fenêtrée,
3 enregistrement des paramètres précédents"""
4
5 import copie_usb_window # version avec fenêtre
6 import os.path # pour détecter l'existence d'un fichier
7 import re # pour les expressions régulières
8
9 class copie_usb_window_save (copie_usb_window.copie_usb_window):
10 """recopie des fichiers sur une clé USB avec une fenêtre graphique,
11 et enregistrement des précédents paramètres"""
12
13 def ecrire_parametre (self, txt) :
14 """écriture des paramètres dans le fichier txt"""
15 # ouverture du fichier en mode écriture
16 f = open (txt, "w")
17 f.write (self.ch1)
18 f.write ("\n")
19 f.write (self.ch2)
20 f.write ("\n")
21 f.write (self.accept.pattern)
22 f.write ("\n")
23 f.write (self.refuse.pattern)
24 f.write ("\n")
25 f.close ()
26
27 def lire_parametre (self, txt) :
28 """relecture des paramètres écrits dans le fichier txt s'il existe"""
29 if os.path.exists (txt) :
30 f = open (txt, "r")
31
32 s = f.readline ()
33 s = s.replace ("\n", "")
34 self.ch1 = s
35
36 s = f.readline ()
37 s = s.replace ("\n", "")
38 self.ch2 = s
39
115
40 s = f.readline ()
41 s = s.replace ("\n", "")
42 self.accept = re.compile (s)
43
44 s = f.readline ()
45 s = s.replace ("\n", "")
46 self.refuse = re.compile (s)
47
48 f.close ()
49
50 def fenetre (self) :
51 """méthode fenêtre surchargée pour lire les derniers paramètres
52 et enregistrer les nouveaux"""
53 # première étape, lire les précédents paramètres
54 self.lire_parametre ("copie_usb_window_save.txt")
55 # seconde étape, appel de la méthode précédente
56 copie_usb_window.copie_usb_window.fenetre (self)
57 # troisième étape, écriture des paramètres
58 self.ecrire_parametre ("copie_usb_window_save.txt")
59
60
61 if __name__ == "__main__" :
62
63 print "copie de fichiers vers une clé USB"
64 ch1 = "C:\\Documents and Settings\\Dupré\\" \
65 "Mes documents\\informatique\\support\\python_td"
66 ch2 = "c:\\temp\\copie_usb"
67 filtre_accept = ".*[.].*"
68 filtre_refuse = ".*[.]pdf$|.*[.]html$|.*[.]bmp|programme\\\\.*[.]zip$"
69
70 # filtre_accept accepte tout type de fichier
71 # filtre_refuse refuse tous les fichiers dont l'extension est pdf, html ou
72 # inclus dans le répertoire programme et ayant l'extension zip
73
74 c = copie_usb_window_save (ch1, ch2, filtre_accept, filtre_refuse)
75 c.fenetre ()
76
�n correction TD 10 ut
116
24 Correction du TD 11, page 49
Le programme qui suit répond aux deux questions de l'énoncé. La classe XML_List dé�nit le comportementque doit suivre le programme lors de la lecture d'un �chier XML. Cette classe construit une liste dequadruplets qui contiennent :
1. Le niveau d'inclusion (nombre de balises ouvrantes - nombre de balises fermantes pour arriver jus-qu'ici).
2. Le nom de la dernière balise, None si absent.
3. Le nom d'un attribut associé à la dernière balise ou None.
4. Une chaîne de caractères, associée à l'attribut si celui-ci est di�érent de None ou à la dernière balisele cas échéant.
La fonction process_file traite le �chier XML, elle crée un parseur, lui a�ecte une instance de la classeXML_List, lit ligne à ligne le �chier XML passé en argument puis retourne la liste précédemment décrite.
Les dernières lignes exécutées permettent de copier les �chiers. A�n d'éviter qu'un �chier portant le mêmenom qu'un autre déjà copié ne l'écrase, le nom du �chier de destination inclut les noms de répertoiresséparés par des blancs soulignés. Le module file_selection.py est aussi utilisé pour sélectionner des�chiers ou répertoires à travers une boîte de dialogue.
1 # -*- coding: cp1252 -*-
2 """parcours d'un fichier au format XML, l'exemple choisi est un fichier
3 XML décrivant une liste de morceaux musicaux pour le logiciel Winamp
4 (www.winamp.com), ces morceaux placés en des endroits divers
5 du disque dur sont recopiés dans un répertoire unique"""
6 import xml.sax as XML # pour parser le fichier
7 import selection_file as FS # pour sélectionner le nom d'un fichier
8 import shutil # pour la copie de fichier
9 import os.path # gestion des noms de fichiers et répertoires
10
11 class XML_List (XML.ContentHandler) :
12 """définition d'une classe dont les méthodes sont appelées à chaque fois
13 qu'un élément dans le fichier XML est rencontré,
14 cette classe remplit une liste contenant des triplets
15 (niveau, balise, attribut, valeur) ou
16 (niveau, balise, None, valeur) ou
17 (niveau, None, None, valeur)"""
18
19 def __init__ (self) :
20 self.list = []
21
22 def get_list (self) :
23 """retourne la liste"""
24 return self.list
25
26 def startDocument (self) :
27 """méthode appelée lorsque le document XML est ouvert"""
28 #print "ouverture du fichier XML"
117
29 self.niveau = 0
30
31 def endDocument (self) :
32 """méthode appelée lorsque le document XML est fermé"""
33 #print "fermeture du fichier XML"
34 pass
35
36 def startElement (self, ba, attr) :
37 """méthode appelée chaque fois qu'une nouvelle balise
38 est rencontrée, le nom de la balise est ba, les attributs
39 associées sont stockées dans attr"""
40 self.niveau += 1
41 key = attr.keys ()
42 for k in key :
43 v = attr.get (k)
44 self.list.append ((self.niveau, ba,k,v.encode ("latin-1")))
45 # v.encode ("latin-1") permet la conversion des chaînes unicode (0-65535)
46 # en chaînes de caractères 0-255
47 self.balise = ba
48
49 def endElement (self, ba) :
50 """méthode appelée lorsqu'une balise de fin est rencontrée"""
51 self.balise = None
52 self.niveau -= 1
53
54 def characters (self,data) :
55 """méthode appelée entre une balise et sa balise de fin associée"""
56 self.list.append ((self.niveau, self.balise, None, data))
57
58 def process_file (file) :
59 """parcours un fichier et retourne une liste contenant :
60 (niveau, balise, attribut, valeur) ou
61 (niveau, balise, None, valeur) ou
62 (niveau, None, None, valeur)"""
63
64 # création d'une classe qui va parcourir le fichier XML
65 p = XML.make_parser ()
66 x = XML_List ()
67 # on affecte au parseur une instance de la classe XML_List
68 p.setContentHandler (x)
69
70 # on lit le fichier file ligne par ligne,
71 # chaque ligne est envoyée au parser XML
72 f = open (file, "r")
73 for l in f :
74 p.feed (l)
75 p.close ()
76 f.close ()
77 return x.get_list ()
78
118
79 if __name__ == "__main__" :
80 # choix d'un nom de fichier
81 file = "xml_example.xml"
82 fs = FS.FileSelection ("sélection d'un fichier XML", file)
83 file = fs.run ()
84
85 # on appelle la fonction process_file pour récupérer les informations
86 # inscrites dans le fichier XML
87 li = process_file (file)
88
89 # parmi toutes ces informations, on récupère la liste
90 # des fichiers de morceaux musicaux, ces morceaux,
91 # pour le logiciel Winamp, sont associés à l'attribut Playstring
92 file_list = []
93 for l in li :
94 if l [2] == "Playstring" : file_list.append (l [3])
95
96 # on sélectionne le répertoire dans lequel vont être copiés
97 # les morceaux sélectionnés
98 d = "c:\\temp\\selection"
99 fs = FS.FileSelection ("sélection d'un répertoire destination", d, False)
100 d = fs.run ()
101
102 # si le répertoire sélectionné n'existe pas, on le crée
103 if not os.path.exists (d) : os.makedirs (d)
104
105 # on copie les fichiers
106 for f in file_list :
107 str = f.replace ("file:C:\\x_Musique", "")
108 str = str.replace ("\\", "_")
109 fc = f.replace ("file:", "")
110 print "copie de ", fc, " vers ", d + "\\" + str
111 shutil.copy (fc, d + "\\" + str)
112
�n correction TD 11 ut
119
25 Correction du TD 12, page 54
La classe HTML_explore peut dériver indi�éremment de la classe HTMLParser du module HTMLParser oude la classe HTMLParserScript du module portant le même nom. Dans le premier cas, ce programme nepourra lire que la version 2.01 du langage HTML. Dans le second cas, le programme sera capable de liredes versions plus récentes sans toutefois déchi�rer complètement la version 4.01, la plus répandue.
La classe HTML_explore dérive donc d'une des deux classes précédemment citées dont elle surcharge deuxméthodes :
1. handle_starttag est appelée chaque qu'une nouvelle balise est lue dans un �chier HTML, enparticulier la balise < a href = ... < /a > qui permet d'insérer un lien hypertexte. Surcharger cetteméthode permet de balayer tous les hyperliens d'une page.
2. handle_data est appelée chaque fois qu'un texte est inclus entre deux balises, il s'agit du textedans lequel les mots-clés, les expressions, seront cherchés. Le programme concatène chaque chaînede caractères que reçoit cette fonction.
La fonction process_file ouvre une page HTML, la place intégralement dans une chaîne de caractères quiest envoyée à la classe HTML_explore. Après avoir déchi�ré cette page, la classe HTML_explore retourneune chaîne de caractères ne contenant que le texte sans mise en forme ainsi que la liste des hyperliens.process_file recherche une expression dans le contenu d'une page puis passe aux pages suivantes tantqu'il y en a. Le programme ne conserve pas les hyperliens si ceux-ci sont trop éloignés de la premièrepage. La fonction retourne les pages sélectionnées et les pages pour lesquelles une erreur de lecture s'estproduite.
1 # -*- coding: cp1252 -*-
2 """recherche de mot-clés dans des pages HTML,
3 ce programme ne peut lire pour l'instant que le format HTML 2.0
4 et pas HTML 4.01, format utilisé par la plupart des sites."""
5
6 import urllib # accéder une adresse internet
7 import urlparse # manipuler les adresses internet
8 import re # expression à chercher
9 import html_parser_script # classe de parser HTML modifiée pour éviter les scripts
10
11 class HTML_explore (html_parser_script.HTMLParserScript) :
12 """parcour un fichier HTML"""
13
14 def __init__ (self, list, text, url, niveau, niveau_max) :
15 html_parser_script.HTMLParserScript.__init__(self)
16 self.list = list
17 self.niveau = niveau
18 self.niveau_max = niveau_max
19 self.url = url
20 self.text = text
21
22 def cherche (self,url) :
23 """recherche un url dans la liste"""
24 for n,u in self.list :
25 if u == url : return True
120
26 return False
27
28 def diese (self,adr) :
29 """simplifie les liens avec le symboles #"""
30 p = adr.find ("#")
31 if p == -1 : return adr
32 else : return adr [0 : p]
33
34 def handle_starttag (self, tag,attr) :
35 """nouveau tag ou balise"""
36 if self.niveau >= self.niveau_max : return
37 self.tag = tag
38 if self.tag == "a" or self.tag == "area" :
39 for i,j in attr :
40 if (i == "aref" or i == "href") and len (j) > 0 and j [0] != "#" :
41 adr = self.diese (j)
42 if len (adr) > 4 and (adr [0:4] == "http" or adr == "ftp") :
43 if not self.cherche (adr) :
44 self.list.append ((self.niveau, adr))
45 elif len (adr) > 5 and adr [0:6] != "mailto" :
46 adr = urlparse.urljoin (self.url, adr)
47 if not self.cherche (adr) :
48 self.list.append ((self.niveau, adr))
49
50 def handle_endtag (self, tag) :
51 """fin d'un tag ou balise"""
52 pass
53
54 def handle_data (self, data) :
55 """texte compris entre le début et la fin d'un tag"""
56 d = data.replace ("\n", "")
57 if len (d) > 3 :
58 self.text.append (data)
59
60
61 def process_file (url, exp, niveau_max = 5, nbmax = -1) :
62 """parcours un fichier HTML et retourne la liste des url
63 qui contiennent l'expression, la liste des
64 adresses qui n'ont pas pu être atteinte ainsi que le nombre d'adresses
65 explorées, cette fonction n'explore pas plus de nbmax pages sauf si nbmax == -1"""
66
67 res = []
68 error = []
69
70 # création d'une classe qui va parcourir le fichier XML
71 adr = [(0, url)]
72 text = []
73 errfile = 0
74 nb = 0
75
121
76 for niv,url in adr :
77
78 nb += 1
79 if nb > nbmax and nbmax >= 0 : break
80 whole = ""
81 print "open %d/%d" % (nb,len (adr)), " f = ", len (res), " -- ", niv, " : ", url
82
83 try :
84 f = urllib.urlopen (url)
85 d = f.read ()
86 whole += d
87 except Exception, exc:
88 print " exception lecture ", exc, "\t -- ", url
89 error.append (url)
90 continue
91
92 try :
93 text = []
94 p = HTML_explore (adr, text, url, niv+1, niveau_max)
95 # on lit le fichier file ligne par ligne,
96 # chaque ligne est envoyée au parser XML
97 p.feed (whole)
98 p.close ()
99
100 t = ""
101 for s in text : t += s + " "
102 t = t.replace ("\n", " ")
103 t = t.replace ("\r", " ")
104 if exp.match (t) : res.append (url)
105
106 except Exception, exc:
107 print " exception html ", exc, exc.__class__, "\t -- ", url
108 error.append (url)
109 f = open ("c:\\temp\\html_err" + str (errfile) + ".html", "w")
110 f.write (whole)
111 f.close ()
112 errfile += 1
113 continue
114
115 return res, error, len (adr)
116
117
118
119 if __name__ == "__main__" :
120 # choix d'un nom de fichier
121 url = "http://www.lemonde.fr/"
122 # on appelle la fonction process_file pour récupérer les informations
123 # inscrites dans le fichier XML
124 s = ".*Kerry.*"
125 ex = re.compile (s, re.IGNORECASE)
122
126 li,error,nb = process_file (url, ex, 3, -10)
127
128 print "--------------------------------------------------------------------"
129 print "--------------------------------------------------------------------"
130 print "nombre d'adresses explorées :\t", nb
131 print "nombre d'adresses sélectionnées :\t", len (li)
132 print "nombre d'adresses non ouvertes ou mal lues :\t", len (error)
133 print "--------------------------------------------------------------------"
134 print "--------------------------------------------------------------------"
135 if len (li) > 0 :
136 print "url contenant l'expression ", s
137 for l in li :
138 print " --------- " , l
139
140 if len (error) > 0 :
141 print "url n'ayant pas pu être ouverts ou mal lus "
142 for l in error :
143 print " --- erreur ", l
Ce �chier inclus la classe HTMLParserScript. Elle adapte la classe HTMLParser du module a�n de lire unformat HTML plus évolué que la version 2.01. En revanche, elle ne déchi�re pas tout script inclus dansune page HTML.
1 # -*- coding: cp1252 -*-
2 """recherche de mot-clés dans des pages HTML,
3 ce programme ne peut lire pour l'instant que le format HTML 2.0
4 et pas HTML 4.01, format utilisé par la plupart des sites."""
5
6 import HTMLParser # parcourir un fichier HTML
7 import re
8 import markupbase
9
10 starttagopen = re.compile('<[a-zA-Z]')
11
12 attrfind = re.compile(
13 r'\s*([a-zA-Z_][-.:a-zA-Z_0-9]*)(\s*=\s*'
14 r'(\"[a-z]+\"#[a-zA-Z. ]+[.][a-zA-Z]+|\"[0-9]+\"\"|\'[^\']*\'|"[^"]*"'\
15 '|([a-zA-Z_:.]+\s*\([0-9/a-zA-Z\"\',. &;éèàùûâêîô\-_\?:!=@]*\))'\
16 '(;void\(0\);)?|\"\"|[-a-zA-Z0-9./,:;+*%?!&$\(\)_#=~]*))?')
17
18 # si locatestarttagend est modifié, il faut penser à modifier
19 # également attrfind
20 locatestarttagend = re.compile(r"""
21 <[a-zA-Z][-.a-zA-Z0-9:_]* # tag name
22 (?:\s+ # whitespace before attribute name
23 (?:[a-zA-Z_][-.:a-zA-Z0-9_]* # attribute name
24 (?:\s*=\s* # value indicator
25 (?:([a-zA-Z_:.]+\s*\([0-9/a-zA-Z\"',. &;éèàùûâêîô\-_\?:!=@]*\))(;void\(0\);)? #
26 |\"[0-9]+\"\" # colspan = "2""
27 |\"[a-z]+\"\#[a-zA-Z. ]+[.][a-zA-Z]+ # "rect"#Le Monde.fr
123
28 |\"\" # alt = ""
29 |\"[^\"]*\" # LIT-enclosed value
30 |'[^']*' # # LITA-enclosed value
31 |[^'\">\s]+ # bare value
32 )
33 )?
34 )
35 )*
36 \s* # trailing whitespace
37 """, re.VERBOSE)
38
39 entityref = re.compile('&([a-zA-Z][-.a-zA-Z0-9]*)[^a-zA-Z0-9]')
40 charref = re.compile('&#@(?:[0-9]+|[xX][0-9a-fA-F]+)[^0-9a-fA-F]')
41 incomplete = re.compile('&[a-zA-Z#]')
42
43 commentclose = re.compile(r'--\s*>|/\s*>|-- /\s*>|-\s*>')
44
45
46 class HTMLParserScript (HTMLParser.HTMLParser) :
47
48 def parse_comment(self, i, report=1):
49 rawdata = self.rawdata
50 #assert rawdata[i:i+4] == '<!--', 'unexpected call to parse_comment()'
51 match = commentclose.search(rawdata, i+4)
52 if not match:
53 print "-------------------------------------------------------"
54 print rawdata[i:i+250]
55 print "-------------------------------------------------------"
56 print end
57 print "-------------------------------------------------------"
58 return -1
59 if report:
60 j = match.start()
61 self.handle_comment(rawdata[i+4: j])
62 j = match.end()
63 return j
64
65 def _scan_name(self, i, declstartpos):
66 rawdata = self.rawdata
67 n = len(rawdata)
68 if i == n:
69 return None, -1
70 m = markupbase._declname_match(rawdata, i)
71 if m:
72 s = m.group()
73 name = s.strip()
74 if (i + len(s)) == n:
75 return None, -1 # end of buffer
76 return name.lower(), m.end()
77 else:
124
78 self.updatepos(declstartpos, i)
79 print "-------------------------------------------------------"
80 print rawdata[i:i+250]
81 print "-------------------------------------------------------"
82 print end
83 print "-------------------------------------------------------"
84 self.error("expected name token")
85
86 def parse_starttag(self, i):
87 self.__starttag_text = None
88 endpos = self.check_for_whole_start_tag(i)
89 if endpos < 0:
90 return endpos
91 rawdata = self.rawdata
92 self.__starttag_text = rawdata[i:endpos]
93
94 # Now parse the data between i+1 and j into a tag and attrs
95 attrs = []
96 match = HTMLParser.tagfind.match(rawdata, i+1)
97 assert match, 'unexpected call to parse_starttag()'
98 k = match.end()
99 self.lasttag = tag = rawdata[i+1:k].lower()
100
101 while k < endpos:
102 m = attrfind.match(rawdata, k)
103 if not m:
104 break
105 attrname, rest, attrvalue = m.group(1, 2, 3)
106 if not rest:
107 attrvalue = None
108 elif attrvalue[:1] == '\'' == attrvalue[-1:] or \
109 attrvalue[:1] == '"' == attrvalue[-1:]:
110 attrvalue = attrvalue[1:-1]
111 attrvalue = self.unescape(attrvalue)
112 attrs.append((attrname.lower(), attrvalue))
113 k = m.end()
114
115 end = rawdata[k:endpos].strip()
116 if end not in (">", "/>"):
117 lineno, offset = self.getpos()
118 if "\n" in self.__starttag_text:
119 lineno = lineno + self.__starttag_text.count("\n")
120 offset = len(self.__starttag_text) \
121 - self.__starttag_text.rfind("\n")
122 else:
123 offset = offset + len(self.__starttag_text)
124 print "-------------------------------------------------------"
125 print rawdata[i:i+250]
126 print "-------------------------------------------------------"
127 print end
125
128 print "-------------------------------------------------------"
129 self.error("junk characters in start tag: %s"
130 % `rawdata[k:endpos][:20]`)
131 if end.endswith('/>'):
132 # XHTML-style empty tag: <span attr="value" />
133 self.handle_startendtag(tag, attrs)
134 else:
135 self.handle_starttag(tag, attrs)
136 if tag in self.CDATA_CONTENT_ELEMENTS:
137 self.set_cdata_mode()
138 return endpos
139
140 def check_for_whole_start_tag(self, i):
141 rawdata = self.rawdata
142 m = locatestarttagend.match(rawdata, i)
143 if m:
144 j = m.end()
145 next = rawdata[j:j+1]
146 if next == ">":
147 return j + 1
148 if next == "/":
149 if rawdata.startswith("/>", j):
150 return j + 2
151 if rawdata.startswith("/", j):
152 # buffer boundary
153 return -1
154 # else bogus input
155 self.updatepos(i, j + 1)
156 self.error("malformed empty start tag")
157 if next == "":
158 # end of input
159 return -1
160 if next in ("abcdefghijklmnopqrstuvwxyz=/"
161 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"):
162 # end of input in or before attribute value, or we have the
163 # '/' from a '/>' ending
164 return -1
165 #if next in "'" :
166 # return -1
167 print "------------------------------------"
168 print next
169 print m.groups ()
170 print "------------------------------------"
171 print rawdata [i: i + 250]
172 print "...................................."
173 print rawdata [j: j + 30]
174 self.updatepos(i, j)
175 self.error("malformed start tag")
176 raise AssertionError("we should not get here!")
177
126
178 def goahead(self, end):
179 if not self.__dict__.has_key ("_script") :
180 self._script = False # ajout
181 self._nb_script = 0 # ajout
182 rawdata = self.rawdata
183 i = 0
184 n = len(rawdata)
185 while i < n:
186 match = self.interesting.search(rawdata, i) # < or &
187 if match:
188 j = match.start()
189 else:
190 j = n
191 if i < j: self.handle_data(rawdata[i:j])
192 i = self.updatepos(i, j)
193 if i == n: break
194 startswith = rawdata.startswith
195
196 if self._script : # ajout
197 if startswith('</script>', i): # ajout
198 k = i + len ('</script>') # ajout
199 self._script = False # ajout
200 i = self.updatepos(i, k)
201 elif startswith('</SCRIPT>', i): # ajout
202 k = i + len ('</SCRIPT>') # ajout
203 self._script = False # ajout
204 i = self.updatepos(i, k)
205 else:
206 k = i + 1
207 i = self.updatepos(i, k)
208 elif startswith('<', i):
209 if startswith("<script", i):
210 self._nb_script += 1
211 k = i + len ("<script")
212 self._script = True
213 elif startswith("<SCRIPT", i):
214 self._nb_script += 1
215 k = i + len ("<SCRIPT")
216 self._script = True
217 elif starttagopen.match(rawdata, i): # < + letter
218 k = self.parse_starttag(i)
219 elif startswith("</", i):
220 k = self.parse_endtag(i)
221 elif startswith("<!--", i):
222 k = self.parse_comment(i)
223 elif startswith("<!-", i):
224 k = self.parse_comment(i)
225 elif startswith("<!/", i):
226 k = self.parse_comment(i)
227 elif startswith("<!-- /", i):
127
228 k = self.parse_comment(i)
229 elif startswith("<?", i):
230 k = self.parse_pi(i)
231 elif startswith("<!", i):
232 k = self.parse_declaration(i)
233 elif (i + 1) < n:
234 self.handle_data("<")
235 k = i + 1
236 else:
237 break
238 if k < 0:
239 if end:
240 print "######################################### (1)"
241 print rawdata [i:i+250]
242 self.error("EOF in middle of construct")
243 break
244 i = self.updatepos(i, k)
245 elif startswith("&#", i):
246 match = charref.match(rawdata, i)
247 if match:
248 name = match.group()[2:-1]
249 self.handle_charref(name)
250 k = match.end()
251 if not startswith(';', k-1):
252 k = k - 1
253 i = self.updatepos(i, k)
254 continue
255 else:
256 break
257 elif startswith('&', i):
258 match = entityref.match(rawdata, i)
259 if match:
260 name = match.group(1)
261 self.handle_entityref(name)
262 k = match.end()
263 if not startswith(';', k-1):
264 k = k - 1
265 i = self.updatepos(i, k)
266 continue
267 match = incomplete.match(rawdata, i)
268 if match:
269 # match.group() will contain at least 2 chars
270 if end and match.group() == rawdata[i:]:
271 print "######################################### (2)"
272 print rawdata [i:i+250]
273 self.error("EOF in middle of entity or char ref")
274 # incomplete
275 break
276 elif (i + 1) < n:
277 # not the end of the buffer, and can't be confused
128
278 # with some other construct
279 self.handle_data("&")
280 i = self.updatepos(i, i + 1)
281 else:
282 break
283 else:
284 assert 0, "interesting.search() lied"
285 # end while
286 if end and i < n:
287 self.handle_data(rawdata[i:n])
288 i = self.updatepos(i, n)
289 self.rawdata = rawdata[i:]
�n correction TD 12 ut
129
26 Correction du TD 13, page 56
Le programme décrit l'ensemble du programme partiellement dévoilé lors de l'énoncé de ce TD 13. Ladernière partie contient la boucle qui modi�e à chaque itération la position des masses ponctuelles dela corde. Une seule instruction a été ajoutée (question 3) dep = c.iteration(dt) qui lance le calcul desforces exercées en chaque masse et la mise-à-jour des positions qui en découle.
Il peut être amusant de jouer avec les paramètres, le poids des masses ou encore la vitesse de freinage.Une vitesse de frottement nulle empêche le système de converger puisqu'il n'y a aucune perte d'énergie.Les masses ne cessent de s'agiter dans les airs. Une faible raideur des ressorts reliant chaque masse ralentitégalement la convergence et peut accessoirement allonger la longueur de la corde. Ce petit modèle desimulation permet de véri�er des intuitions physiques relatives au problème.
1 # -*- coding: cp1252 -*-
2 import pygame # pour les affichages
3 import math # pour les racines carrées
4
5
6 class point (object) :
7 """définition d'un point : deux coordonnées et une masse"""
8 __slots__ = "x","y","m"
9
10 def __init__ (self, x,y,m) :
11 """définit un point de la corde, de coordonnées (x,y) et de masse m"""
12 self.x, self.y, self.m = float (x), float (y), float (m)
13
14 def deplace_point (self, dep, dt) :
15 """déplace un point, le vecteur de déplacement est dp * dt
16 où dep est aussi un point"""
17 self.x += float (dep.x) * dt
18 self.y += float (dep.y) * dt
19
20 def difference (self, p) :
21 """retourne le vecteur qui relie deux points, retourne un point"""
22 return point (p.x - self.x, p.y - self.y, 0)
23
24 def norme (self) :
25 """retourne la norme du vecteur (x,y)"""
26 return math.sqrt (self.x*self.x + self.y*self.y)
27
28 def __str__ (self) :
29 """afficher le point"""
30 return "(x,y) = (%4.2f,%4.2f) masse %f" % (self.x,self.y,self.m)
31
32 class corde (object) :
33 """définition d'une corde, une liste de points"""
34
35 def __init__(self, nb, p1, p2, m, k, g, f, l) :
36 """initialisation d'une corde
37 @param nb nombre de points
130
38 @param p1 = x1,y1 coordoonnées du premier point (fixe)
39 @param p2 = x2,y2 coordoonnées du dernier point (fixe)
40 @param m masse de la corde,
41 répartie entre tous les pointstous les points
42 @param k raideur de l'élastique
43 @param g intensité de l'apesanteur,
44 valeur positive
45 @param f vitesse de freinage
46 @param l longueur de la corde"""
47 x1,y1 = p1[0], p1[1]
48 x2,y2 = p2[0], p2[1]
49 self.list = []
50 self.vitesse = []
51 for i in range (0,nb) :
52 x = x1 + float (i) * (x2 - x1) / float (nb - 1)
53 y = y1 + float (i) * (y2 - y1) / float (nb - 1)
54 self.list.append ( point (x,y, float (m) / nb))
55 self.vitesse.append (point (0,0,0))
56 self.k = k * nb
57 self.g = g
58 self.l = float (l) / (nb-1)
59 self.f = f
60
61 def display (self, screen) :
62 """affichage de la corde à l'aide du module pyagame"""
63 x,y = screen.get_size ()
64 color = (0,0,0)
65 for p in self.list :
66 pygame.draw.circle (screen, color, (int (p.x), int (y - p.y)), int (p.m+1))
67 for i in xrange (0,len (self.list)-1) :
68 pygame.draw.line (screen, color, \
69 (int (self.list [i].x), int (y - self.list [i].y)), \
70 (int (self.list [i+1].x), int (y - self.list [i+1].y)))
71
72 def force_point (self, i) :
73 """calcule les forces qui s'exerce en un point, retourne un point x,y"""
74 x,y = 0,0
75 # poids
76 y -= self.g * self.list [i].m
77 # voisin de gauche
78 dxdy = self.list [i].difference (self.list [i-1])
79 d = dxdy.norme ()
80 if d > self.l :
81 dxdy.x = (d - self.l) / d * dxdy.x
82 dxdy.y = (d - self.l) / d * dxdy.y
83 x += self.k * dxdy.x
84 y += self.k * dxdy.y
85 # voisin de droite
86 dxdy = self.list [i].difference (self.list [i+1])
87 d = dxdy.norme ()
131
88 if d > self.l :
89 dxdy.x = (d - self.l) / d * dxdy.x
90 dxdy.y = (d - self.l) / d * dxdy.y
91 x += self.k * dxdy.x
92 y += self.k * dxdy.y
93 # freinage
94 x += - self.f * self.vitesse [i].x
95 y += - self.f * self.vitesse [i].y
96
97 return point (x,y,0)
98
99 def iteration (self, dt) :
100 """calcule les déplacements de chaque point et les met à jour,
101 on ne déplace pas les points situés aux extrémités,
102 retourne la somme des vitesses et des accélérations au carré"""
103 force = [ point (0,0,0) ]
104 for i in xrange (1, len (self.list)-1) :
105 xy = self.force_point (i)
106 force.append (xy)
107 force.append (point (0,0,0))
108
109 # déplacement
110 for i in xrange (1, len (self.list)-1) :
111 self.vitesse [i].deplace_point ( force [i], dt )
112 self.list [i].deplace_point ( self.vitesse [i], dt )
113
114 d = 0
115 for f in force :
116 d += self.vitesse [0].x ** 2 + force [i].x ** 2
117 d += self.vitesse [1].y ** 2 + force [i].y ** 2
118
119 return d
120
121 def attendre_clic (screen,x,y):
122 """dessine un rectangle rouge sur l'écran et
123 attend la pression d'un clic de souris"""
124 color = 255,0,0
125 pygame.draw.line (screen, color, (10,10), (x-10,10), 2)
126 pygame.draw.line (screen, color, (x-10,10), (x-10,y-10), 2)
127 pygame.draw.line (screen, color, (x-10,y-10), (10,y-10), 2)
128 pygame.draw.line (screen, color, (10,y-10), (10,10), 2)
129 pygame.display.flip ()
130 reste = True
131 while reste:
132 for event in pygame.event.get():
133 if event.type == pygame.MOUSEBUTTONUP :
134 reste = False
135 break
136
137 if __name__ == "__main__" :
132
138
139 # initialisation du module pygame
140 pygame.init ()
141 size = width, height = x,y = 800, 500
142 white = 255,255,255
143 screen = pygame.display.set_mode(size)
144 # création de la corde
145 nb = 10
146 c = corde (nb, (100,450), (700,450), \
147 m = 400, k = 0.4, g = 0.1, f = 0.05, l = 800)
148 dt = 0.1
149
150 iter = 0 # numéro d'itération
151 dep = len (c.list) * (x*x + y*y) # continue tant que dep n'est pas proche de 0
152 while True and dep > 1e-4 :
153
154 # on peut stopper temporairement le programme d'une pression
155 # du bouton gauche de la souris
156 for event in pygame.event.get():
157 if event.type == pygame.QUIT: sys.exit()
158 if event.type == pygame.MOUSEBUTTONUP:
159 attendre_clic (screen,x,y)
160
161 # on affiche régulièrement la corde, ici toutes les dix itérations
162 if iter % 10 == 0 :
163 screen.fill (white)
164 c.display (screen)
165 pygame.display.flip ()
166
167 # on incrémente le nombre d'itérations
168 iter += 1
169
170 # on fait une pause dès la première itérations pour voir la corde
171 # dans sa position initiale
172 if iter == 1: attendre_clic (screen,x,y)
173
174 ##############################################################"
175 # unique instruction ajoutées par rapport à l'énoncé
176 dep = c.iteration (dt)
177 ##############################################################"
178
179 # on met à jour l'écran
180 pygame.display.flip ()
181
182 # le programme est terminé, on fait une pause pour voir le résultat final
183 attendre_clic (screen,x,y)
�n correction TD 13 ut
133
Index
Aaccent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61accélération . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56Algorithme
mouvement d'une corde. . . . . . . . . . . . . . . . . . . . .57portrait . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16tracé d'une ellipse (Bresenham) . . . . . . . . . . . . . 13tracé d'une ligne (Bresenham) . . . . . . . . . . . . . . 10
arborescence. . . . . . . . . . . . . . . . . . . . . . . . . . . . .36, 39, 48
Bbalise . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49, 54bouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40Bresenham . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10, 13, 85
Cchaîne de caractères
accent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61classe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
close. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .48ContentHandler . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50�le . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48FileSelection. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43HTMLParser . . . . . . . . . . . . . . . . . . 54, 55, 120, 123object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7xml.sax.ContentHandler . . . . . . . . . . . . . . . . . . . . 50
commentaireaccent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
connexité4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10, 13
copie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36, 39, 48, 49, 52corde suspendue . . . . . . . . . . . . . . . . . . . . . . . . . . . 56, 130correction
TD 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61TD 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115TD 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117TD 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120TD 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130TD 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62TD 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68TD 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74TD 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80TD 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85TD 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105TD 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109TD 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Ddensité. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5droite
tracé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Eellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85Excel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5expression régulière. . . . . . . . . . . . . . . . . . . . .37, 54, 120
Ffacette . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18fenêtre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39, 48fenêtre graphique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39�chier . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
copie . . . . . . . . . . . . . . . . . . . . 36, 39, 48, 49, 52, 117�ltre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37fonction
cmp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7compile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37, 55copy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38, 52edge_style . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9exists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4isdir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38is�le . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38join. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55listdir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38makedirs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38match . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37, 55mkdir . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38node_style . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9pprint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7randint. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3, 5raw_input . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3replace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6, 52round. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4split . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6sqrt. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5urlopen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55xrange. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10
Ggraphe XY. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Graphviz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Hhistogramme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
134
HTML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49, 54, 120HTMLParser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123hyperlien . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54, 120
Iimage de synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18intensité lumineuse . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105interface graphique. . . . . . . . . . . . . . . . . . . . . . . . .48, 115
Llancer de rayon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18lien hypeertexte . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54, 120ligne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85loi
Bernouilli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4binomiale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4normale . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Mmasse ponctuelle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .56module
biggles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65�le_selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43gplt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64GraphDot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8graphlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8HTMLParser . . . . . . . . . . . . . . . . . . 54, 55, 120, 123IaGraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64math . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5Numeric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64os . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38os.path . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38pprint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7psyco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17pygame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10, 17random. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3�5re . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37, 55, 120sax.xml . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .50Scienti�cPython . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64SciPy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .64shutil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38, 52string . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6Tkinter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39urllib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55, 120urlparse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55, 120
modèleillumination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
mot-clé . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54méthode
__dict__. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7__init__. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .7
__str__ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7con�g . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40delete . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42get . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42grid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40insert . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42mainloop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
Oobjet
Button . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39Entry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39, 42Label . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39Tk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Pparser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52parseur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52pentium . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86Phong . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19poids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56portrait . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16, 18Python
dictionnaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5
Qquadrilatère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
Rrayon
ré�échi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18rayon incident . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105remarque
accent . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53version du langage HTML . . . . . . . . . . . . . . . . . . 55
repère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18ressort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56répertoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36, 39, 48
Ssphère . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
TTD
TD 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3TD 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48TD 11 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49TD 12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54TD 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56TD 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4TD 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
135
TD 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7TD 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10TD 6 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15TD 7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18TD 8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36TD 9 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
tension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56théorème central limite. . . . . . . . . . . . . . . . . . . . . . . . . . .4tracé d'une ellipse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13tracé d'une ligne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10tracé d'une ligne (Bresenham) . . . . . . . . . . . . . . . . . . 10TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
UUSB. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .36, 39, 48
Vvariable aléatoire. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4voyageur de commerce. . . . . . . . . . . . . . . . . . . . . . .15�17
Wwidget . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
XXML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49, 117
Zzone de saisie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40zone de texte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
§§
Algorithme13.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 575.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
136