Acquérir les bases de la géométrie linéaire dans le plan et dans l'espace. Maîtriser la composition de transformations géométriques pour être capable de développer une application pour la 3D à l’aide d’OpenGL. Introduction à la géométrie algorithmique dans le plan en terme méthodologique et d’algorithmes robustes.

Présentation des transformations géométriques de base, de leurs propriétés, de leur composition en coordonnées homogènes. Présentation des équations générales et paramétriques des droites et des plans. Rappel sur les vecteurs, produits scalaires et vectoriels, conditions de colinéarité, coplanarité, orthogonalité. Positions relative d’un point et d’une droite, de deux droites, d’une droite et d’un plan ou leurs restrictions à un segment ou un triangle. Présentation des coordonnées barycentriques. Tests et calculs d’intersection des éléments linéaires. Présentation des polygones. Introduction des bases de la géométrie algorithmique à travers quelques algorithmes dans le plan comme le calcul d’aires, le problème de la galerie d’art, l’enveloppe convexe, la triangulation etc. Evocation de Voronoï. Durant cette UE, les étudiants mettent en pratique via une application 3D à l'aide d'OpenGL.

À l'issue de cette UE un étudiant saura :
- Reconnaître et retrouver les transformations de base comme les translations, homothétie, rotation 2D et 3D.
- Décomposer une transformation géométrique complexe en une séquence de transformations géométriques simples.
- Ecrire les matrices des transformations géométriques de base en coordonnées homogènes.
- Déterminer les diverses équations des droites et des plans à partir des données les décrivant.
- Passer des coordonnées cartésiennes aux coordonnées barycentriques et l’inverse.
- Ecrire des algorithmes robustes d’intersection des éléments linéaires, droites, segments, plans, triangle etc.
- Localiser un point par rapport à une droite par la méthode des aires (orientation).
- Localiser un point par rapport à un polygone par la méthode des angles et des indices.
- Retrouver les conditions de colinéarité, coplanarité, orthogonalité entre vecteurs.
- Ecrire un algorithme géométrique robuste et efficace pour des problèmes simples de géométrie.

Références :
- Mark de Berg, Marc van Kreveld, Mark Overmars, Otfried Schwarzkopf, Computational Geometry, Algorithms and Applications, Second, Revised Edition, Springer, 2000 (ISBN 3-540-65620-0)
- Joseph O'Rourke, Computational Geometry in C, Second Edition, Cambridge University Press, 1994.
- Informatique Graphique, Modélisation Géométrique et Animation, Série Traitement du signal et de l'image (Traité IC2), sous la direction de D. Bechmann, B. Péroche, Hermès ISBN : 978-2-7462-1514-6.
- Informatique Graphique et Rendu, Série Traitement du signal et de l'image (Traité IC2), sous la direction de B. Péroche, D. Bechmann, Hermès ISBN : 978-2-7462-1515-3.
- Computer graphics : principles and practice, FOLEY J. & al., Addison-Wesley, 1990.

À l'entrée de cette UE, un étudiant devrait savoir :
- compétence avancées en algorithmique et programmation
- connaissance des structures de données classiques (listes, arbres, graphes)
- des éléments de base en géométrie.