Présentation sur la robustesse en géométrie algorithmique
Résumé
Cette présentation vise à présenter sur un exemple les notions de robustesse, de
cas dégénérés, et le principe des solution de perturbation symboliques
appliquées pour résoudre ces problèmes. Les notions sont appliquées sur un code
jouet de calcul d'enveloppe convexe en 2D disponible dans le dossier Code. Il
est à noter que l'auteur n'est pas spécialiste du domaine, et que quelques
imprécisions ou erreurs peuvent subsister dans la présentation.
Code jouet
La présentation modifiait le code en direct petit à petit. Ici, différentes variantes du code sont présentées.
-
hull.cpp: le code initial non robuste -
hull_perturbation.cpp: ajout d'une perturbation dans le prédicat -
hull_permutation.cpp: indépendance vis à vis de l'ordre des paramètres -
hull_almost_exact.cpp: arithmétique exacte dans le prédicat
Il reste encore à modifier le prédicat pour prendre un paramètre supplémentaire, et éviter l'appel sur des résultats intermédiaires sujets à des arrondis.
Ces codes génèrent des fichiers svg dans le dossier /tmp. Si vous n'êtes pas
sous linux, il vous faudra probablement changer les chemins de ces fichiers.