Licence d'Informatique
Documents autorisés : notes personnelles de cours et de TD uniquement.
Lisez l'ensemble de l'énoncé. Soyez clair, précis, concis. Justifiez vos réponses. Relisez-vous.
L'examen est constitué de 4 exercices indépendants.
On considère la fonction définie par l'équation suivante, dans laquelle r est une constante strictement positive et (x0, y0) un point quelconque :
y = y0 + r2 / (x - x0)
1. Etudier les symétries de la courbe définie par cette équation.
2. Donner une fonction implicite définissant cette courbe. Utiliser la technique du point médian pour calculer les différences du premier ordre.
3. En déduire un algorithme en nombres entiers permettant la rastérisation de cette courbe dans une fenêtre rectangulaire définie par les points (0, 0) et (w, h), w > 0 et h > 0.
On considère un polygone P rastérisé dans une fenêtre rectangulaire définie par les points (0, 0) et (w, h), w > 0 et h > 0, et M0 un point intérieur au polygone P. La fenêtre est initialiement blanche et les pixels du polygone sont tracés en noir. On suppose que les pixels intérieurs au polygone sont connexes.
On se propose de remplir le polygone avec la technique suivante : soit M un point intérieur à P ; on affiche M en noir, puis on itère l'algorithme pour chaque voisin de M de couleur blanche. Les voisins considérés sont les voisins immédiats dans les quatre directions Nord, Est, Sud et Ouest. Le premier point M considéré est le point M0.
1. Expliquer pourquoi cet algorithme colorie en noir tous les points intérieurs au polygone P, et seulement eux.
2. Ecrire l'algorithme en pseudo-Pascal ou pseudo-C, sous forme récursive.
3. P étant le polygone ci-contre (ou approchant), et M le point marqué d'une croix, numéroter les pixels dans l'ordre où ils sont coloriés par votre algorithme.
4. Combien de fois (au pire) chaque pixel est-il consulté par cet algorithme ? Cet algorithme vous paraît-il efficace ? Voyez-vous un moyen simple de l'améliorer ?
On considère un ensemble d'icones affichés sur un écran. Chaque icone est défini par une position, un type (qui détermine l'image affichée), un nom et un état de sélection (booléen). Les actions possibles sur les icones sont la sélection et le déplacement.
La sélection s'effectue par un clic sur un icone ou par entourage de plusieurs icones dans un rectangle élastique. Toute nouvelle sélection remplace la sélection précédente.
Le déplacement s'effectue par un "drag" de l'icone. Pendant le déplacement, si le curseur passe sur un icone, celui-ci indique s'il est prêt à recevoir l'icone déplacé en s'affichant en inversion vidéo. On dit que l'icone sous le curseur est sensible à l'icone déplacé. Lorsque l'on relâche le bouton de la souris, le déplacement est terminé et 3 cas sont possibles :
1. Donner une structure de données décrivant les icones, et les fonctions associées permettant leur gestion. On ne demande pas le corps de ces fonctions, simplement leur entête et une description informelle.
2. Donner la machine à états décrivant la sélection d'icone par clic et par rectangle.
3. Donner la machine à états décrivant le déplacement d'icone. On se donne une fonction Sensible (type1, type2) qui indique si un icone de type type2 est sensible lorsqu'un icone de type type1 passe au-dessus de lui.
4. Combiner les deux machines à état en une seule, en résolvant les ambiguïtés.
On considère un cube de côté r, dont l'un des coins est à l'origine. Le but de l'exercie est de transformer ce cube de telle sorte que l'origine (0, 0, 0) et le coin qui lui est diamétralement opposé (r, r, r) échangent leurs positions (voir figure ci-dessous).
|
Avant |
Après |
1. Donner la suite de rotations qui permet de passer du trièdre (i, j, k) au trièdre (i', j', k').
2. Insérer la ou les translations dans la suite de rotations de la question 1 afin que l'origine et le coin opposé échangent leurs positions. En déduire la matrice de transformation globale.
3. Calculer l'image par la transformation de la question 2 du point (r/2, r/2, r/2).