Le calcul géométrique


L'objet du calcul géométrique est de représenter, calculer et manipuler les objets géométriques. Le calcul géométrique remonte aux origines des mathématiques et a été développé avec des points de vue très différents selon les époques et les cultures, pratique chez les arpenteurs égyptiens qui évaluaient des aires et des volumes, plus abstrait chez les grecs avec les constructions à la règle et au compas. Les premiers se souciaient principalement de calculs numériques et connaissaient des approximations assez précises de Pi. Les seconds inventaient une démarche algorithmique sans se préoccuper de la précision de leurs tracés. Ces deux points de vue se retrouvent aujourd'hui alors que l'ordinateur a renouvelé le calcul géométrique et lui donne un rôle clé dans de nombreuses applications.


Les premiers objets géométriques qui ont été créés et manipulés sur un ordinateur étaient des objets manufacturés, à la géométrie complexe mais à la construction relativement simple : on pouvait les dessiner sur un écran d'ordinateur avec un système de CAO.

L'intérêt pour les questions combinatoires est apparu plus récemment quand il a fallu représenter des objets de grandes tailles : objets naturels (organes, molécules, surfaces géologiques), scènes complexes comportant des millions de facettes des mondes réels ou virtuels de l'infographie, objets plongés dans des espaces de grandes dimensions comme les espaces de configuration de robots.


Le calcul géométrique a ainsi évolué et l'étude traditionnelle des courbes et des surfaces s'est vue complétée par l'analyse des aspects algorithmiques. La géométrie algorithmique est ainsi devenue à la fin des années 70 une nouvelle branche de l'informatique qui étudie la conception et l'analyse des algorithmes géométriques : calcul d'intersections, problèmes de visibilité, planification de trajectoires, optimisation géométrique etc. La résolution de ces problèmes s'appuie souvent sur la construction d'un petit nombre de structures de données géométriques fondamentales : arbres de recherche multidimensionnelle, triangulations, cartes, polyèdres, arrangements, diagrammes de Voronoï. Pour en savoir plus....


Les domaines d'application de la géométrie algorithmique sont nombreux : l'informatique graphique, la robotique, les maillages pour le calcul scientifique, la modélisation en chimie structurale, la conception de circuits VLSI, la cartographie, l'imagerie médicale, pour n'en citer que quelques uns .

Au delà des grands domaines d'application, le point de vue, les concepts et les techniques développés dans le cadre de la géométrie algorithmique s'avèrent utiles dans des contextes extrêmement variés.


La géométrie algorithmique a au début surtout insisté sur les aspects combinatoires et ignoré les problèmes numériques. Le livre de F. Preparata et M. Shamos sur le sujet propose, pour analyser les algorithmes, un modèle de machine qui effectue toutes les opérations élémentaires sur les nombres réels exactement et en un coût unitaire. Ce modèle simplifie beaucoup les analyses en évacuant les questions arithmétiques et il a permis de concentrer les premières études sur la structure combinatoire des objets géométriques.

Ce modèle a cependant révélé ses limites en pratique. Les ordinateurs ne sachant représenter que des nombres de précision finie, l'implantation naïve des algorithmes utilisant la représentation flottante des nombres réels peut conduire à un comportement anormal des programmes, erreurs grossières, boucles infinies ou terminaisons catastrophiques. Si ces comportements sont bien connus, ils sont difficiles à maîtriser.

Une part importante de la recherche récente en géométrie algorithmique porte sur le calcul fiable. La double nature numérique et combinatoire des objets géométriques permet d'aborder ce problème en distiguant les prédicats qui permettent de calculer la structure de l'objet (par exemple les faces d'un diagramme de Voronoï et leurs relations d'incidence) et les constructions qui calculent le plongement de cet objet. Les prédicats jouent un rôle critique car ils conditionnent le déroulement d'un programme. Il est donc essentiel de les évaluer exactement mais en revanche leur valeur est discrète, typiquement c'est un signe +, - ou 0. On dispose maintenant de méthodes très performantes qui permettent de faire du calcul géométrique fiable sans pénaliser sérieusement les temps de calcul (Thèse de Sylvain Pion).


Le projet de développer une bibliothèque regroupant sous une forme cohérente les algorithmes de géométrie algorithmique est né en 1995. Depuis, six universités en Europe et en Israël travaillent avec le projet Prisme de l' INRIA sur CGAL, la Computational Geometry Algorithms Library. Ce projet est partiellement financé par la Communauté Européenne. Cette bibliothèque écrite en C++ est paramétrable (représentation des objets géométriques, types de nombres), modulaire (avec une séparation nette entre la représentation des objets et les prédicats, et les algorithmes) et robuste. Elle propose des modules pour les principales structures de données géométriques et les algorithmes d'optimisation géométrique.



Last modified: Tue Apr 11 10:10:45 MET DST 2000
Jean-Daniel Boissonnat     Accueil PRISME same page in english