Géométrie Algorithmique et Calcul Géométrique

Introduction à CGAL

Pierre Alliez, INRIA Sophia-Antipolis

Ce cours complemente le cours d'Olivier Devillers sur la geometrie algorithmique et le calcul geometrique. Le but consiste a se familiariser avec quelques algorithmes et structures de donnees utilises pour le calcul geometrique, en utilisant la bibliothèque C++ d’algorithmes géométriques CGAL. Cette bibliotheque offre de plus une excellente illustration des possibilités de programmation générique de C++, de l’utilisation des templates, et de traits class.

Apres une introduction generale et un cours d'introduction a la bibliotheque standard STL , nous passerons en revue les enveloppes convexes en 2D, les triangulations en 2D et 3D, et les surfaces polyedriques (illustrations ci-dessous). Chaque cours comprend une presentation d'un module (1h), et des travaux sur machine (2h, sous windows avec MS Visual C++ .NET).

Le contrôle des connaissances sera effectué sous la forme d’un mini-projet a choisir dans une liste d'une dizaine de projets.

Supports de cours

27 octobre apres-midi:

• Introduction
• STL
• Enveloppes convexes [TD, lire le fichier readme]

3 novembre apres-midi:

• Triangulations 2D [TD]

1er decembre apres-midi (salle 302, puis 226)

• Triangulations 3D

8 decembre apres-midi (salle 226, a partir de 16h15 - apres l'examen avec Olivier Devillers)

• Poursuite du TD sur les triangulations en 2D.

15 decembre apres-midi (salle 302, puis 226)

• Polyedres 3D

22 decembre apres-midi (salle 226 - 4H de TD)

• TD sur les triangulations 2D et 3D

12 janvier apres-midi (salle 226 - 4H de TD)

• TD sur les polyedres

19 janvier apres-midi (salle 226 - 4H de TD)

• suite du TD sur les polyedres

Examen (mini-projets):
- mini-projets
- fichiers terrains: rivers, dem
- documentation et donees pour la subdivision de Loop

Configuration pour les TD:
Verifiez que CGAL 3.1 est deja installe (vous devez avoir une variable d'environnement CGALROOT), sinon installez CGAL 3.1
Si non deja presents, copiez les fichiers *.lib dans le répertoire CGAL-3.0.1\lib\msvc7
Les 4 fichiers correspondent aux combinaisons mono vs multi-thread et debug vs release mode. les applications MFC / OpenGL utilisées pour les TD nécessitent les versions multi-thread cgal_mt_debug.lib et cgal_mt_release.lib
La documentation est accessible sur le site de CGAL

Sous .NET 2003:
Pour une meilleure lisibilite, configurez l'éditeur avec deux espaces par tabulation: menu Outils / Options / Editeur de texte/ C/C++ / Tabulations taille des tabulations: 2, taille du retrait: 2