From computational geometry to geometric calculus
De la géométrie algorithmique au calcul géométrique
Résumé
In this thesis, we define efficient and generic methods in order to solve
the robustness problems that arise in the field of computational geometry,
and we concentrate especially on the exact evaluation of the geometric
predicates.
We investigated methods based on modular arithmetic, which led us to
develop simple and efficient algorithms to reconstruct the sign in this
number representation.
We also developed new kinds of arithmetic filters,
which allow to speed up the exact computation of predicates, working
around the cost of traditionnal solutions based on generic
multiprecision computations.
Our methods are based on the use of interval arithmetic,
which allows an efficient and simple use, combined to an automatic
generation tool of the predicates code.
These solutions are now available in the CGAL library of geometric
algorithms.
the robustness problems that arise in the field of computational geometry,
and we concentrate especially on the exact evaluation of the geometric
predicates.
We investigated methods based on modular arithmetic, which led us to
develop simple and efficient algorithms to reconstruct the sign in this
number representation.
We also developed new kinds of arithmetic filters,
which allow to speed up the exact computation of predicates, working
around the cost of traditionnal solutions based on generic
multiprecision computations.
Our methods are based on the use of interval arithmetic,
which allows an efficient and simple use, combined to an automatic
generation tool of the predicates code.
These solutions are now available in the CGAL library of geometric
algorithms.
Dans cette thèse, nous définissons des méthodes efficaces et génériques
dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique,
en se concentrant principalement sur l'évaluation exacte des prédicats
géométriques.
Nous avons exploré des méthodes basées sur l'arithmétique
modulaire, ce qui nous a conduits à mettre au point des algorithmes simples
et efficaces de reconstruction du signe dans cette représentation des
nombres.
Nous avons également mis au point de nouveaux types de filtres
arithmétiques qui permettent d'accélérer
le calcul des prédicats exacts, en contournant le coût des solutions
traditionnelles basées sur des calculs multi-précision génériques.
Nos méthodes sont basées sur l'utilisation de l'arithmétique
d'intervalles, qui permet une
utilisation souple et efficace, combinée à un outil de génération
automatique de code des prédicats.
Ces solutions sont maintenant disponibles dans la bibliothèque
d'algorithmes géométriques CGAL.
dans le but de résoudre les problèmes de robustesse que pose la géométrie algorithmique,
en se concentrant principalement sur l'évaluation exacte des prédicats
géométriques.
Nous avons exploré des méthodes basées sur l'arithmétique
modulaire, ce qui nous a conduits à mettre au point des algorithmes simples
et efficaces de reconstruction du signe dans cette représentation des
nombres.
Nous avons également mis au point de nouveaux types de filtres
arithmétiques qui permettent d'accélérer
le calcul des prédicats exacts, en contournant le coût des solutions
traditionnelles basées sur des calculs multi-précision génériques.
Nos méthodes sont basées sur l'utilisation de l'arithmétique
d'intervalles, qui permet une
utilisation souple et efficace, combinée à un outil de génération
automatique de code des prédicats.
Ces solutions sont maintenant disponibles dans la bibliothèque
d'algorithmes géométriques CGAL.