Les Newsletters Interstices
    Niveau facile
    Niveau 1 : Facile

    Manipulation informatique des objets géométriques

    Culture & Société
    Algorithmes
    Dans la vie courante, on a le plus souvent affaire à des objets tridimensionnels. On s'intéresse à leur forme, à leur orientation, etc. Pour les traiter informatiquement, on développe des algorithmes où les objets manipulés ne sont pas directement des nombres, mais plutôt des objets géométriques, des points, des surfaces, des volumes…

    Comment représenter ces objets ? Avec des nombres qui caractérisent leur taille, leur forme, etc. Pour un nombre entier ou rationnel, la représentation informatique est facile. Pour un nombre réel, c’est déjà beaucoup plus difficile. Le lien entre géométrie et nombre est fort : rappelons par exemple que c’est un problème géometrique, déterminer la diagonale du carré, qui a montré aux Pythagoriciens qu’il existait des nombres irrationnels.

    Manœuvres d’approche

    La représentation d’une surface, à condition de connaître son équation avec des coefficients qui sont des nombres représentables, est également facile. Mais la plupart des objets géometriques ne se laissent pas représenter par une équation, et on ne peut les appréhender que comme assemblages de surfaces ou de volumes élémentaires représentables mathématiquement et informatiquement. En général, il faut beaucoup d’objets élémentaires pour représenter un objet réel : une molécule peut être composée de dizaines de milliers d’atomes, une pièce mécanique d’un grand nombre de facettes.

    Les différentes étapes de la modélisation de la main.

    Les différentes étapes de la modélisation de la main.

    Un environnement naturel ne pourra être qu’approché par un grand nombre de primitives simples. L’objet géométrique est alors composé à la fois d’un ensemble d’objets élémentaires (des facettes triangulaires par exemple) et d’une structure combinatoire donnant les relations d’incidence entre ces objets élémentaires. Trouver les bonnes structures combinatoires et les algorithmes efficaces pour les manipuler est au coeur de la géométrie algorithmique.

    Placement géométrique des antennes d'un satellite.

    Placement géométrique des antennes d’un satellite.

    Pour aménager l’espace

    Un problème typique récurrent, utilisant ces fondements, concerne l’aménagement optimal de l’espace. On peut ainsi définir un algorithme permettant de disposer au mieux des antennes dans le volume restreint d’un satellite de télécommunications, en tenant compte de leur encombrement et en évitant les interférences dues au recouvrement de leurs zones d’émission.

     

    Pour reconstruire un objet

    D’autres problèmes pratiques relèvent de la reconstruction de surface ou de volume à partir d’un ensemble de points. L’idée est de disposer d’un modèle 3D d’une maquette ou d’un objet qu’on a devant soi, afin de pouvoir le manipuler sur ordinateur, l’agrandir, l’observer sous tous les angles, le modifier à loisir, l’envoyer par Internet, etc.

    Il faut déterminer les points de l’objet dont on a besoin de connaître la position précise, pour interpoler géométriquement le reste de l’objet. La mesure de ces points peut s’effectuer à l’aide de capteurs disposés sur l’objet, ou par des techniques de scanner. Il faut alors trouver une triangulation (ou maillage) qui relie ces points en une structure 3D cohérente, pour construire un objet géométrique décrivant convenablement l’objet initial. L’algorithmique intervient pour reconstruire de manière systématique et efficace l’objet désiré.

    Un tel outil de reconstruction peut servir dans des domaines aussi divers qu’inattendus.

    coupe géologique
    reconstruction volumique de terrain
    De la coupe géologique… …à la reconstruction volumique de terrain.

     

    Pour le tracé d’un tunnel sous les Alpes, un algorithme géométrique a permis d’obtenir un modèle raisonnable du sous-sol et des zones à éviter, à partir d’un nombre réduit de sondages, qui sont très onéreux.

    En médecine, la constitution de modèles 3D d’organes ou du squelette d’un patient à partir de quelques points offre des avantages considérables.

    simulation d'une endoscopie

    Simulation d’une endoscopie.

    Un tel modèle peut en particulier être transmis sur Internet, pour une analyse, voire une manipulation à distance par un chirurgien.

    Des applications plus quotidiennes encore des algorithmes géométriques concernent la vente par correspondance de prêt-à-porter, d’outils, ou de meubles sur mesure, que l’on peut positionner virtuellement dans un modèle de son appartement.

     

    Pour transmettre des données

    compression de maillages

    Compression géométrique de maillages.

    De manière générale, sur Internet, entre les entreprises, ou avec les clients, on partage de moins en moins des images des objets sur lesquels on travaille, qui sont par nature figées, mais plutôt des modèles géométriques 3D, que chacun peut manipuler à sa guise. Si les objets sont représentés de manière astucieuse, des algorithmes de compression des données géométriques peuvent alors apporter d’importants gains de temps lors des transmissions électroniques, et de volume pour le stockage.

    Newsletter

    Recevez chaque mois une sélection d'articles

    Niveau de lecture

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

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

    Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !

    Étienne Parizot

    Journaliste scientifique.
    Voir le profil

    Jean-Daniel Boissonnat

    Directeur de recherche Inria et responsable de l'équipe GEOMETRICA.
    Voir le profil