Algorithmes géométriques, théorie et pratique

Master IFI-VIM


 2011-2012
  • salle 309 (sauf 23 janvier salle 318, 6 février salle 108, et 27 février salle 303) - L'emploi du temps à l'EPU
  • Merci d'apporter règle, stylos de plusieurs couleurs, compas si possible, ordinateur portable pour les TD machines (avec CGAL installé).
  • 9-1 Enveloppes convexes + Triangulation de Delaunay [Cours, exercices] [OD]
  • Avant le 16 janvier
    • installer CGAL avec Qt4 (voir ci-dessous)
    • pour tester cette installation, compiler et exécuter les démos des modules Triangulation_2 et Triangulation_3 de CGAL
  • 16-1 Triangulation de Delaunay + Randomisation [Cours, exercices] [OD]
  • 23-1 (salle 318) Initiation à la bibliothèque CGAL [Cours + TD machine : énoncé - fichiers - corrigé] [MT]
  • 30-1 Exemple d'application : maillage 2D par raffinement de Delaunay, maillage de surface, maillage 3D. [Cours] [PA]
  • 6-2 (salle 108) Triangulation de Delaunay 3D avec CGAL [Cours+TD machine : énoncé - fichiers - corrigé] [MT]
  • 13-2 Robustesse des algorithmes et précision numérique [Cours] [OD]
  • 20-2 Maillage (suite) [Cours+ TD machine raffinement de Delaunay 2D] [PA]
  • du 16 au 21 soutenance des micro-projets à l'inria, sur rendez-vous (planning).
  • 27-2 14h exam ecrit (2h) (salle 303)

La notation

  • 15%. TD machines notés.
  • 15%. Exercices notés au fil des cours.
  • 30%. Micro-projet, distribué en semaine 4 à rendre à la dernière séance .
  • 40%. Examen individuel écrit en fin de période.
  • Modalités:
    • les TD machines notés ne devraient pas poser de problèmes si vous avez installé CGAL au préalable sur votre portable.
    • Lors des cours, en particulier des cours non suivis d'un TD machine, il y aura des exercices "d'entrainement à l'examen final" dont certains seront notés.
    • Le micro-projet est "un gros TD CGAL" en binome. Vous devez préparer un mini-rapport de 2 pages et un exposé/démo de 20 mn Le sujet doit être choisi dans la liste disponible ici.
    • L'examen écrit est de 2h, les documents sont autorisés, mais pas les ordinateurs. Prévoyez des crayons de différentes couleurs, une règle et un compas. Les sujets des années précédentes sont disponibles ci dessous.

Voici quelques pages très utiles pour vous:

Objectif du module

Le but de ce module est de présenter les grandes tendances de la géométrie algorithmique actuelle, et en particulier son évolution vers ce que nous appellerons le calcul géométrique. Après plusieurs années où la géométrie algorithmique a connu des développements plutôt théoriques, une des grandes questions actuelles est «Comment passer à des algorithmes effectivement programmés ?» On explorerera les principaux problèmes de la géométrie et leurs solutions. On regardera les algorithmes classiques (plutôt théoriques) mais aussi les problèmes plus pratique posés par les incertitudes numériques ou la complication excessive de ces algorithmes classiques. On utilisera la bibliothèque CGAL (www.cgal.org) pour passer à la pratique. Les domaines d'applications sont extrêmement variés allant de la modélisation des sites archéologiques au placement d'antennes dans un réseau de téléphonie mobile en passant par la simulation d'écoulement de fluides.

Prérequis du cours

  • Il serait souhaitable de connaître un peu d'algorithmique. En particulier quelques algorithmes de tri (tri fusion, quick sort) et les arbres binaires équilibrés.
    Également un peu de C++ (    STL).
  • Pour installer CGAL
    • Liste des plate-formes possibles
    • Le manuel complet d'installation
    • MacOs
      • Installer Xcode depuis le site d'apple
      • Installer Qt depuis le site de nokia
      • Installer macport depuis le site de macport
      • Installer libQGLViewer depuis le site de libQGLViewer
        • tar -xzf libQGLViewer-2.3.8.tar.gz
        • cd libQGLViewer-2.3.8/QGLViewer
        • qmake -spec macx-g++
        • make
        • sudo make install
      • Avec port
        • sudo port selfupdate
        • sudo port install cmake
        • sudo port install boost (installer boost prend plusieurs heures)
        • sudo port install mpfr
      • Installer CGAL
        • Récupérer le tarball sur le site de cgal
        • tar -xzvf CGAL-3.9.tar.gz
        • mkdir builds/3.9-Debug builds/3.9-Release
        • cd builds/3.9-Release
        • cmake -DCMAKE_BUILD_TYPE=Release ../../CGAL-3.9
        • make
        • cd builds/3.9-Debug
        • cmake -DCMAKE_BUILD_TYPE=Debug ../../CGAL-3.9
        • make
        • export CGAL_DIR=~/CGAL/builds/3.9-Release
      • Tester votre installation sur les exemples
        • cd ../../CGAL-3.9/examples/Triangulation_2
        • cmake .
        • make
        • les examples devraient avoir été compilés et s'exécuter correctement
      • Tester votre installation sur les démos
        • cd ../../demo/Triangulation_2
        • cmake .
        • make
        • les démos devraient avoir été compilées et s'exécuter correctement, sinon il y a un problème avec Qt
        • cd ../Triangulation_3
        • cmake .
        • make
        • les démos devraient avoir été compilées et s'exécuter correctement, sinon il y a un problème avec QGLViewer
    • Linux : similaire à mac à part Xcode et macport.
      • remplacer port par yum ou votre gestionnaire de package préféré
      • ne pas utiliser l'option "-spec macx-g++" avec qmake ppour QGLViewer.
    • Windows :
      • Installer CMake
      • Installer Qt depuis le site de nokia et compiler avec ces instructions.
      • Installer libQGLViewer depuis le site de libQGLViewer et compiler.
      • Installer CGAL 3.9 depuis la page CGAL, lancer l'installeur Setup.exe. Installez aussi les composants GMP, MPFR, LAPACK, TAUCS.
      • Compilez avec Visual C++ ou Visual C++ express (2008-2010). Il faut passer par CMake en executant cmake-gui, et en faisant un glisser-deposer du fichier CMakeLists.txt present dans votre repertoire de CGAL. Indiquer par exemple un sous-repertoire /build pour compiler. Cmake vous demande de choisir un compilateur, et d'indiquer si vous souhaitez compiler les demos et examples (decocher pour le moment).
      • CMake genere une solution Visual C++ (fichier .sln) que vous pouvez ouvrir avec Visual C++. Compiler ensuite dans tous les modes (release, debug, etc).
      • Tester CGAL en compilant des exemples et demos comme indique ci-dessus pour MacOS (chaque demo vient avec un fichier CMakeLists.txt).
      • Faire un test de compilation du TP CGAL en lien au dessus.

    Contacter le responsable : Olivier.Devillers(at)inria.fr