Licence d'Informatique
Devoir 1 - à rendre le 4 avril 1995
Soit P un pixel de coordonnées (x, y). Les voisins de P sont les 4 pixels de coordonnées :
(x+1, y) (x, y+1)
(x-1, y) (x, y-1)
Un ensemble E de pixels est dit connexe si tout pixel P de E est voisin d'un pixel P' de E. On appelle région un ensemble connexe de pixels.
On appelle tâche associée à P la région contenant P et dont tous les pixels sont de même couleur que P.
Le devoir consiste à implémenter un algorithme de remplissage de tâche, c'est-à-dire un algorithme qui, étant donnés un pixel P0 de couleur C0 et une couleur C!=C0, affiche tous les pixels de la tâche associée à P0 avec la couleur C.
Un algorithme très simple est le suivant :
procedure RemplirTacheNaif (x, y : entier; C0 : Couleur; C : Couleur) {
SetPixel (x, y, C);
si GetPixel (x + 1, y) != C0 alors Remplir (x + 1, y, C0, C);
si GetPixel (x - 1, y) != C0 alors Remplir (x - 1, y, C0, C);
si GetPixel (x, y + 1) != C0 alors Remplir (x, y + 1, C0, C);
si GetPixel (x, y - 1) != C0 alors Remplir (x, y - 1, C0, C);
}
procedure TacheNaif (x, y : entier; C : Couleur) {
Remplir (x, y, GetPixel (x, y), C)
}
Cet algorithme est très inefficace du fait des nombreux appels récursifs, et des nombreux tests de pixels.
Pour améliorer l'efficacité, on décide de procéder par coloriage de bandes horizontales connexes plutôt que pixel par pixel :
Soit P (x, y) un pixel appartenant à la tâche. On appelle bande associée à P l'intervalle [x0, x1] tel que x0 <= x <= x1 et tous les pixels Pi (xi, y) avec x0 <= xi <= x1 sont de couleur C0. Le principe de l'algorithme est le suivant :
Un programme Tache.c est disponible sur les mâchines bâtiment 308 dans le fichier
~mbl/INFOGRAPHIE/Tache.c.
Il permet de colorier des pixels en mode point à point ou en mode "peinture" (commande 'p'). L'image peut être sauvée dans un fichier (commande 's') puis rechargée (commande 'c').
L'algorithme naïf est lancé par la commande 'n'. Il demande de saisir un point, remplit la tâche associée à ce point en couleur gris clair et imprime sur la sortie standard :
L'algorithme amélioré est lancé par la commande 't'. Il vous faut compléter la procédure RemplirTache de Tache.c pour implémenter l'algorithme amélioré. Cette procédure est appelée par la procédure Tache qui imprime sur la sortie standard :
Ils vous appartient de mettre à jour les champs de la structure Stats pour que les valeurs imprimées soient correctes.
On pourra utiliser un tableau pour implémenter la pile de pixels de l'algorithme amélioré.
La bibliothèque Raster contient deux fonctions utiles qui ne sont pas dans la documentation qui vous a été distribuée :
RasterSetColorPixel (x, y, c) affiche le pixel (x, y) avec la couleur c.
RasterGetPixel (x, y) retourne la couleur du pixel (x, y), ou OUTSIDE s'il est en dehors de l'écran.
Les documents à rendre sont :
- un petit dossier à déposer au secrétariat de la Licence expliquant le fonctionnement de l'algorithme et son implémentation et comparant les performances de l'algorithme naïf et de l'algorithme amélioré.
- le source du programme à envoyer par courrier électronique à votre enseignant de TD (mountaz@lri.fr pour le groupe 1, mbl@lri.fr pour le groupe 2). N'oubliez pas d'indiquer votre nom dans un commentaire au début du programme.
La date limite pour rendre le dossier et le programme est le 4 Avril 1995.