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

Master SSTIM (Signal pour la Santé, le Traitement des Images et le Multimédia) -VIM



 2012-2013

La notation

  • 20%. TD machines notés.
  • 10%. 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 cette liste.
    • 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

Install CGAL

  • Il est primordial que CGAL soit installé sur votre portable avant le premier cours de janvier. Le 17 décembre, un créneau est prévu pour débloquer ceux qui auraient des problèmes. Il est hors de questions de faire une install CGAL complète à ce moment car la compilation de CGAL (et de ses dépendances) est trop longue.
    • Ceux qui auront installé CGAL pourrons partir plus tôt le 17 décembre.
    • Ceux qui n'aurons pas installé CGAL avant le 7 janvier aurons 0 au premier TD.
  • Platformes
    • MacOs: sudo port install cgal
    • Linux: yum install cgal
    • Windows avec Visual Studio 2010 (prendre l'option 32 bits): les instructions sont là
  • Tester votre installation
    • télécharger les fichiers pour le premier TP. les compiler (cmake.; make;) et executer.
    • le programme devrait avoir été compilé et s'exécuter correctement, sinon il y a peut être un problème avec Qt
    • télécharger les fichiers pour le premier TP. les compiler (cmake.; make;) et executer.
    • le programme devrait avoir été compilé et s'exécuter correctement, sinon il y a un problème avec QGLViewer
  • Install à la main (MacOS mais ça doit pas être très différent pour linux)
    • 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

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