De la recherche

Des arithmétiques pour la géométrie

La correction des algorithmes géométriques repose sur des théorèmes géométriques. Ces théorèmes sont vrais pour une géométrie réelle - euclidienne par exemple -, mais deviennent faux en général pour une géométrie approchée, telle celle fournie lorsqu'on utilise l'arithmétique flottante des ordinateurs. C'est pourquoi les chercheurs mettent en œuvre des filtres arithmétiques.

De nombreux algorithmes géométriques sont sensibles aux erreurs d'arrondis causées par l'arithmétique flottante des ordinateurs. Une analyse détaillée des raisons sous-jacentes à ces problèmes de non-robustesse peut être effectuée pour chaque algorithme, comme par exemple le calcul d'enveloppe convexe. Pour cet algorithme, des problèmes apparaissent lorsque des points sont presque alignés. Cet exemple est développé dans le document Un joli algorithme géométrique et ses vilains problèmes numériques.

exemple à problème
Exemple de problème rencontré lors du calcul d'enveloppe convexe.

Un algorithme géométrique se compose de propositions élémentaires appelées prédicats. Un prédicat est en fait l'équivalent d'une question dont la réponse peut être oui ou non. Cela revient à faire un calcul, et la proposition est vraie ou fausse selon que le résultat du calcul est positif ou négatif. Lorsqu'une erreur survient dans un prédicat, elle peut perturber l'algorithme dans sa globalité. En revanche, résoudre les problèmes au niveau des prédicats permet d'assurer la robustesse de l'algorithme.

Le paradigme du calcul géométrique exact

La première solution générale à avoir été utilisée pour résoudre ces problèmes a été de calculer les prédicats géométriques à l'aide d'une arithmétique exacte en lieu et place de l'arithmétique flottante fournie par les ordinateurs. Des entiers multiprécision sont ainsi représentés en mémoire par un tableau de mots, et les opérations arithmétiques sont définies sur cette représentation. Cette représentation est étendue aux rationnels multiprécision de manière évidente. Des bibliothèques comme GMP offrent ce type de fonctionalités.

Le principal problème de cette approche est son manque d'efficacité en pratique : elle peut facilement causer un ralentissement d'un facteur 100 à 1000 sur le temps de calcul d'un algorithme géométrique. En effet, les prédicats sont parfois de très petites routines en termes de lignes de code, comme le prédicat d'orientation de 3 points dans le plan qui n'est composé que de 5 soustractions, 2 multiplications et une comparaison, mais ils sont appelés des millions de fois au cours de l'exécution d'un algorithme.

Le calcul géométrique exact filtré

On utilise maintenant un moyen d'accélérer les calculs, tout en garantissant les propriétés d'exactitude des prédicats géométriques. L'idée générale est de considérer l'expression d'un prédicat dans son ensemble, et non pas les opérations arithmétiques qui la composent. On part de l'observation que le calcul flottant fournit généralement un résultat exact à un prédicat, mais qu'il échoue dans de très rares cas. L'idée des filtres arithmétiques consiste donc à fournir, en plus de l'évaluation en calcul flottant, un certificat qui permet de dire si le signe de la valeur approchée est le même que celui de la valeur exacte, ou s'il ne sait pas. Dans les cas où il ne sait pas certifier, on fait alors appel au calcul multiprécision coûteux, mais on espère que ce ne sera pas très souvent, et que donc le temps de calcul moyen des prédicats ne sera pas trop affecté. Si le certificat est rapide à calculer en comparaison de l'évaluation flottante du prédicat, et qu'il est suffisamment précis dans le sens où il sait certifier souvent, alors on peut espérer que le temps de calcul global sera bon.

Le type de filtres le plus facile à mettre en œuvre utilise l'arithmétique d'intervalles. Pour ce faire, on évalue le prédicat avec des intervalles, et si le signe de l'intervalle final n'est pas indéterminé (il ne contient pas zéro), alors on n'a pas à faire appel au calcul multiprécision. Ce type de filtre est très précis et fait partie de la classe des filtres dynamiques. Le temps de calcul d'un algorithme géométrique utilisant ce type de filtres est généralement environ 4 à 5 fois plus lent que lorsqu'on utilise du calcul flottant (non-robuste), ce qui est nettement meilleur que du calcul multiprécision.

D'autres types de filtres existent, dits statiques, qui sont encore plus rapides, car ils reposent sur une analyse fine des expressions des prédicats et des propagations d'erreurs d'arrondis. Expliquer en détail leur fonctionnement demanderait de faire appel à des notions plus ardues. Ces filtres sont néanmoins moins précis, et sont donc généralement couplés à de l'arithmétique d'intervalles, formant ce que l'on appelle des filtres en cascade. On arrive ainsi à des temps de calcul seulement 25 % plus lents que du calcul flottant non-certifié. Ce surcoût est variable, car il dépend par exemple du jeu de données sur lequel on applique l'algorithme : il peut contenir plus ou moins de cas qui posent problème, qui sont la cause de l'utilisation du calcul exact coûteux.

Le calcul utilisant des filtres est appelé calcul paresseux, parce qu'il essaie de n'évaluer que ce qui est nécessaire pour fournir le résultat voulu, en l'occurrence le signe d'une expression. On peut faire le parallèle avec l'effort nécessaire à l'homme pour déterminer l'orientation de 3 points dessinés sur une feuille : si les points ne sont pas presque alignés, alors la tâche est facile. Par contre, si les points sont presque alignés, il faut faire l'effort de porter sa vision proche de l'axe d'alignement des points (ou d'utiliser une règle) pour déterminer le résultat.

Cette animation Flash nécessite un plug-in Adobe Flash. Si l'animation ne s'affiche pas correctement

 

Ces techniques de filtres sont diffusées comme logiciels libres disponibles dans la bibliothèque C++ d'algorithmes géométriques CGAL.

Recherches en cours autour des problèmes de non-robustesse des algorithmes géométriques

Les prédicats étudiés en ce moment portent sur les calculs sur les objets courbes, plutôt que simplement des points ou des droites. Ce sont par exemple des calculs mettant en jeu des arcs de cercles ou d'ellipses.

Comment arrondir les points d'intersection de deux polygones sur la grille des coordonnées flottantes ?

Ils font intervenir des techniques non seulement du domaine de l'arithmétique, mais également du domaine du calcul algébrique effectif, parce que des nombres algébriques (racines de polynômes) interviennent dans les calculs.

Un autre volet de recherche actuelle concerne l'accélération des calculs spécifiques aux constructions géométriques (par opposition aux prédicats bien mieux étudiés). Ce travail est également plus proche des applications, où la sortie des algorithmes est souvent contrainte à être dans un format donné. Par exemple, en CAO (Conception Assistée par Ordinateur), on calcule souvent des intersections de polygones dont les sommets ont des coordonnées flottantes, mais ceux du résultat sont en général rationnels. Il faut donc les reconvertir en nombres flottants. C'est le problème des arrondis géométriques, où la difficulté essentielle réside dans la conservation de propriétés géométriques d'une structure (par exemple la convexité).

Niveau de lecture

Aidez-nous à évaluer le niveau de lecture de ce document.

Il vous semble :

Si vous souhaitez expliquer votre choix, vous pouvez ajouter un commentaire (qui ne sera pas publié).