 | |
| INFO2046-1 | Géométrie algorithmique
 |
|
| Durée : | 30h Th, 30h Pr |
|
| Crédits/ECTS : |
| Master en ingénieur civil en aérospatiale, à finalité approfondie, 2e année | | Toute l'année | | 5 |
|
| Master en ingénieur civil en informatique, à finalité approfondie, 2e année | | Toute l'année | | 5 |
|
| Master en sciences informatiques, à finalité approfondie, 2e année | | Toute l'année | | 6 |
|
| Master en ingénieur civil mécanicien, à finalité approfondie, 2e année | | Toute l'année | | 5 |
|
| Master en ingénieur civil physicien, à finalité approfondie, 2e année | | Toute l'année | | 5 |
|
|
|
| Titulaire(s) : | Eric Béchet |
|
| Langue : | Langue française |
|
| Aperçu général : | Dans un certain nombre de domaines des sciences appliquées, des problèmes d'ordre géométriques apparaissent naturellement, dont les solutions sont parfois non triviales. On peut citer par exemple la problématique de la détection de collision qui peut être résolue entre autre à l'aide d'une partition binaire de l'espace (B-space partition) , ou encore la construction d'une triangulation à partir de différents types de données en entrée (nuage de points, surface mathématique, etc..) qui apparaît dans les domaines du calcul scientifique, de la CAO, de l'infographie, et on pourrait trouver d'autres domaines plus éloignés des sciences appliqués tels que les systèmes d'information géographiques (SIG/GIS).
De façon générale, le cours concerne la géométrie discrète, c'est à dire que l'on ne s'intéresse pas ici à la notion de continuité, et l'on traite principalement des relations entre des entités géométriques telles que les points, droites, plans, polygones/polyèdres. |
|
| Objectif du cours : | Le but de ce cours est de familiariser le public avec les approches les plus courantes utilisées pour résoudre efficacement un certain nombre de problèmes tels que :
- Détection de collision
- Triangulation/pavage d'un domaine (ex: algorithmes de génération de maillages pour le calcul ou la visualisation scientifique)
- Recherche/calcul d'intersections de primitives (lignes, polygones/polyèdres)
- Recherche de voisins les plus proches (points ou autres)
- Calculs de prédicats robustes (ex: un point est-il dans un triangle ou non). Robuste signifie ici que le résultat du prédicat n'est pas sensible aux erreurs d'arrondi dues aux calculs faits en virgule flottante.
- Courbes de niveau (level-sets)
|
|
| Pré-requis : | Connaissances de niveau ingénieur en algorithmique et en géométrie. |
|
| Travaux pratiques : | La partie pratique est constituée de quelques séances de travaux pratiques et d'une partie projet où les étudiants travaillent de façon aussi autonome que possible, en groupes de 2. Le but des séances pratiques est double : d'une part de faire implémenter par les étudiants un certain nombre d'algorithmes fondamentaux sur une application pratique, d'autre part de les familiariser avec une librairie existante : CGAL. |
|
| Organisation : | Emploi du temps à déterminer avec le professeur. |
|
| Notes de cours : | M. de Berg, O. Cheong, M.van Kreveld, M. Overmars (2008). Computational Geometry (3rd revised edition ed.). Springer-Verlag. ISBN 3-540-77973-6 (Disponible sous forme électronique à la Bibiliothèque de l'ULg) |
|
| Evaluation : | Projet + examen de fin de session. |
|
| Contacts : | eric.bechet@ulg.ac.be |
|
| Remarques : | Cours exceptionellement étalé sur toute l'année académique |
|
|
| |
