---

Module Géométrie algorithmique, FMIN215

M1 Informatique, M1 Math/Info

Annee 2014/2015

---

    Actualités:

Examen du 18 mai dernier: correction.
Un énoncé et une correction.

Controle continu du 23 mars dernier: correction.
Un énoncé et une correction.

    Planning 2014/2015:

Les créneaux de cours-td sont le lundi de 13h30 à 16h30, voir l'emploi du temps de la fac des sciences. Les tps ont lieu le le lundi de 16h45 à 18h15 au bâtiment 6.

    Contenu du cours:

15h de cours, 15h de tds, 15h de tps.

• Chapitre 1: Calcul d'intersections Intersections d'un ensemble de segments dans le plan, exemple d'algorithme par balayage. diagramme de Voronoi.
• Chapitre 2: Enveloppe convexe Enveloppe convexe d'un ensemble de points du plan: algorithmes de Graham et de Jarvis. Généralisation pour un ensemble de points de l'espace.
• Chapitre 3: Graphes planaires Lien avec les triangulations d'objet 3D. Formule d'Euler, encodage compact des graphes planaires. Localisation dans un graphe planaire.
• Chapitre 4: Triangulations Triangulation d'un ensemble de points du plan. Triangulation de Delaunay et diagramme de Voronoï. Algorithme par balayage de Fortune pour le calcul du diagramme de Voronoï.
• Chapitre 5: Applications et extensions selon le temps: alpha-shape et alpha-complexe (reconnaisances de forme), sommes de Minkowski (intersections de polygones) et BSP (algorithme du peintre).
  
  

Fiche contenant les algos vus en cours: algo.

    Fiches de TD:

• TD1: Calculs de base dans R²
• TD2: Intersections de segments et enveloppes convexes
  
• TD3: Graphes planaires
• TD4: Triangulations
• TD5: Extensions et applications

   Fiches de TP:

• TP1: Intersection de segments: énoncé en C (avec codes ci dessous) ou énoncé en java.
  Primitives de bases et trame de programme en C pour:
  - Recherche d'une intersection: Intersection.cc
  - Classe ARN pour gérer les arbres rouges et noir: ARN.h et ARN.cc.
• TP2: Calculs d'enveloppes convexes: énoncé en C (avec codes ci dessous) ou énoncé en java.
  Primitives de bases et trame de programme en C pour:
  - le parcours de Jarvis: Jarvis.cc
  - l'algorithme de Graham: Graham.cc
  
• TP3: Triangulations: énoncé en C (avec codes ci dessous) ou énoncé en java.
  Primitives de bases et trame de programme en C pour:
  - le calcul incrémental: Triangulation.cc
  - le passage à une triangulation de Delaunay: Delaunay.cc
  - tests: TestCercleCirc.cc
  
• TP4: Alpha-Complexe et alpha-shape: énoncé en C (avec codes ci dessous) ou énoncé en java.
  Primitives de bases et trame de programme en C pour: AlphaS.cc
  Echantillons de points:
  - Echantillon 1.
  - Echantillon 2.
  - Echantillon 3.
  

   Contrôle des connaissances

Sans document!
Il y aura un examen, et un controle continu (sur feuille pour ~15 points [le lundi 23 mars] + tp noté pour ~5 points [surement le 27 avril]) comptant pour un tiers dans la note finale (avec règle du max...).

   Bibliographie:

• Computational Geometry, M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf, Ed. Springer.
• Introduction à l'algorithmique, T. Cormen, C. Leiserson, R. Rivest, Ed. Dunod, chapitre 35.
• Computational Geometry, F.P. Preparata, M.I. Shamos, Ed. Springer.
• Géométrie algorithmique, J.D. Boissonnat, M. Yvinec, Ed. Ediscience.

---