Contact : Monique Teillaud
<Monique(dot)Teillaud(at)sophia.inria.fr>
L'extension des algorithmes géométriques au cas d'objets courbes est
un sujet de recherche très actif actuellement. Ce thème était au coeur
du projet européen
ECG et est de nouveau
central dans le projet ACS qui lui
succède.
Les applications sont nombreuses et variées, de la biologie moléculaire aux
circuits intégrés, en passant par l'usinage et les systèmes d'information
géographique...
L'un des aspects de ces recherches est l'étude des primitives de base
pour le traitement des arcs de coniques dans le plan, primitives
utilisées entre autres dans le calcul d'arrangements.
Un noyau géométrique pour les arcs de cercles est en cours
d'élaboration pour la bibliothèque CGAL.
Le but concret de ce stage est l'extension de ce noyau au cas des
arcs de coniques.
Ce travail se situe au carrefour de l'informatique et des mathématiques:
- géométrie, et manipulation d'arcs non bornés : comment les représenter ?
comment manipuler les extrémités et les points d'intersection ``à l'infini'' ?
(espace projectif ?) etc,
- filtrage géométrique (boîtes englobantes, polygones englobants),
- aspects arithmétiques,
- aspects algébriques, avec la manipulation de nombres algébriques,
- programmation, expérimentation en CGAL.
Ces recherches s'intègrent dans plusieurs collaborations, notamment au sein de l'ARC Arcadia et du projet européen ACS.
Pour en savoir plus :
noyau courbe CGAL
projet Open Source CGAL
Introduction à CGAL
Prérequis :
bonnes connaissances d'algorithmique de base,
goût pour les aspects mathématiques et la géométrie en particulier,
connaissance de C++ et STL,
goût pour le code de bonne qualité.
Financement : grille INRIA (680 à 960 euros selon les cas).
Possibilité de sujet de thèse.