GRASS GIS : géométries, topologies et conséquences pratiques (vecteurs, rasters, volumes)

 

Après avoir examiné la structure d'une base de données GRASS, il est intéressant d'examiner comment sont représentés les objets spatiaux dans cette base, leurs géométries, et les relations entre ces géométries, qui sont du domaine de la topologie.

Encore une fois, une recherche de ce terme sur le Net, appliqué aux SIGs,  aboutira, dans la majorité des cas, aux explications dans le monde ESRI.  Bien qu'elles soient généralement très claires et très bien faites, elles ne s'appliquent pas de cette manière à GRASS GIS.

Topologie

La topologie est une branche des mathématiques qui s'intéresse aux propriétés qualitatives des objets (mathématiques), indépendamment de toute mesure. Le tout se fait dans un espace topologique qui s'oppose à un espace métrique (quantitatif, où, par exemple, des distances sont définies). C'est un sujet très complexe que le monde des SIGs ne fait qu'effleurer. Je ne peux que vous conseiller la lecture de « Topologicon », de Jean-Pierre Petit, l'astrophysicien pédagogue, dans la série en bande dessinée « Les aventures d'Anselme Laturlu » (www.savoir-sans-frontieres.com/JPP/telechargeables/Francais/LE%20TOPOLOGICON.pdf)...

Le ruban de Möbius est souvent cité comme un objet topologique remarquable. Le voici réalisé avec GRASS.

image provenant de grass.fbk.eu/grass63/screenshots/vector.php     

Il est cependant nécessaire de préciser quelques notions fondamentales à l'aide de deux figures.

Équivalence topologique ou homéomorphisme

La topologie se retrouve en géométrie dans les transformations par des déformations continues (sans déchirement, « trou » ni collage dans les structures) d'objets. Dans la figure suivante, adaptée d'une de celles du livre « Gis: A computing perspective », les 4 formes suivantes sont analysées qualitativement :

• 

image adaptée de la fig. 3.24 de « Gis; A computing perspective »

Il est intuitivement possible d'imaginer :

• qu'en étirant, contractant ou tordant la forme B, il est possible de retrouver la forme A (un cercle, quelque soit sa dimension) ;
• que pour passer de C à A, il faudra percer (ou reboucher) le trou (déformation non continue) ;
• la forme D a été obtenue en collant le ruban sur lui même à un point de jonction. Pour passer de D à A, la déformation n'est donc pas continue.

On dit que les formes A et B sont topologiquement compatibles ou homéomorphes. Aucune n'est topologiquement équivalente à C (trou) et D (collage).  C et D ne sont pas non plus homéomorphes.

Extension à la notion de voisinage et de limites.

Cette équivalence topologique a été, depuis longtemps, étendue aux notions de limites et de voisinages. Dans la figure suivante, adaptée de www.gitta.info/Spatial_Cpts/fr/html/Topology_learningObject1.html, les trois représentations sont aussi équivalentes du point de vue topologique.

Dans le domaine des Sigs

Cette notion de voisinage est aussi une notion spatiale. Les SIGs vont donc faire appel à une topologie pour rendre compte de façon sommaire, mais synthétique de la proximité entre les entités. Les relations topologiques exploitées dans ce contexte seront l'adjacence (voisinage), la connectivité, l'inclusion et l'intersection, le tout dans un espace topologique. Mais ces objets ont aussi une géométrie simple ou complexe dans un espace métrique (ils ont des dimensions physiques).

En résumé (pour les SIGs)

• ce qui relève de l'espace topologique :
  • un point est situé à l'extrémité d'une ligne ;
  • un point est situé sur le contour d'un polygone ;
  • un point est situé à l'intérieur d'un polygone ou d'une région ;
  • un polygone est connecté à une ligne ;
  • une aire est simple, non trouée ;
  • etc.
• ce qui relève de l'espace métrique :
  • la distance entre deux points ;
  • la longueur d'une ligne ;
  • l'angle d'une ligne entre deux points ;
  • le périmètre ou la surface d'une aire ;
  • etc.

Mais un espace métrique peut être muni d'une topologie induite par les distances. C'est la topologie qui est utilisée dans les SIGs.

Géométries vectorielles

Examinons donc tout d'abord comment sont encodées les géométries vectorielles dans GRASS (espace métrique euclidien). Les divers types sont résumés dans la figure suivante.

• point, point 3D : un simple point (x,y et x,y,z) ;
• ligne, ligne 3D : une séquence (orientée) de sommets connectés par des segments qui peut être une ligne simple (arc) ou une polyligne. Les points extrémités sont appelés noeuds ;
• contour : une ligne complètement fermée, c'est-à-dire un polygone ;
  • comme il n'y a plus de points extrémités, les sommets sont aussi des noeuds et les segments des arcs ;
  • ce contour (polygone) ne doit pas être confondu avec une aire ou une surface, qui sont définies dans GRASS par la topologie ;
    
• face : une aire 3D  ;
• les volumes sont en voie d'implémentation, sur base des faces et des kernels (centroïde 3D, définis par la topologie)

Les conversions entre ces divers types sont possibles (v.type, v.build.polylines etc.).

Topologie vectorielle et principales règles

Présentation

Certains affirment ou disent encore que GRASS GIS ne sait gèrer que les shapefiles (géométrie non topologique), mais c'est une opinion un peu surannée... Depuis longtemps (surtout à partir des versions 6.x), GRASS possède sa propre représentation vectorielle (qui n'a rien à voir avec les shapefiles) avec :

• une topologie de réseau (relations de connectivité), basée sur la DGLib (Directed Graph Library, ftp10.tw.freebsd.org/mirror/pub2/GIS/grass/dglib/index.html qui est une bibliothèque pour les Graphes orientés). Elle apporte tous les éléments de la théorie des Graphes. Il est possible de calculer des itinéraires, les chemins les plus courts, les sous-graphes dans un réseau, etc. ;
• une topologie de voisinage (relations d'adjacence / voisinage et d'intersection) qui permet, entre autres choses, de connaître les relations entre chaque polygone / surface à partir des segments / arcs et des sommets / noeuds ;
• une topologie d'inclusion (relations d'inclusion) qui permet de gérer le fait que la géométrie d'un objet peut contenir ou être contenue par un autre.

Principales règles

Ce que la communauté SIG appelle « construction d'une topologie » consiste à établir des règles d'encodage des objets pour ordonner les relations entre noeuds, arcs et polygones. Ces règles ont été formalisées par l'OGC et présentées (en partie) sur le Portail dans « Python: le module Shapely, géométries, prédicats spatiaux, analyse spatiale, matrices de Clementini (DE-9IM), traitements de shapefiles ou autres, et représentation avec matplotlib  ». La représentation de relations topologiques recommandées s’appuie sur un modèle composé de 8 prédicats binaires :

égalité, déconnexion, intersection, adjacence, connectivité, inclusion et chevauchement qui peuvent être combinées (inclusion et adjacence, par exemple).

GRASS, tout comme ESRI et autres, suit ces recommandations et cela se fait lors de la numérisation d'un objet ou postérieurement avec le module v.build. Les principales règles sont les suivantes :

• les arcs ne peuvent pas se croiser. Ils sont découpés à leur intersection avec un sommet commun pour former des segments distincts (intersection, connectivité) ;

• les lignes jointives (qui partagent un noeud) doivent être reliées par un noeud commun (adjacence, connectivité) ;

• les limites de polygones jointifs doivent être uniques (adjacence, connectivité) ;

• une entité surfacique ou aire est un ensemble topologique constitué par un centroïde (point situé à l'intérieur d'un contour) et un contour;
  • elle est identifiée par ce centroïde (topologie de type centroïde) ;
  • un centroïde est lié exclusivement à une entité surfacique ;
  • il est important de noter qu'une aire et son contour sont deux objets différents ;
  • un polygone sans centroïde n'est pas une entité surfacique.

• Les entités surfaciques situées à l'intérieur d'une autre entité (anneaux, « polygones troués ») sont appelées des îles (island, inclusion) ;

• les contours des entités surfaciques doivent être explicitement fermés (sinon ce sont des lignes). Les sommets sont aussi des noeuds et les segments des arcs. Cela signifie qu'il y a moyen de discriminer des aires jointives en fonction de leurs contours et des noeuds communs (adjacence, connectivité et inclusion) ;

• pour assurer la cohérence topologique, une couche vectorielle GRASS est composée de diverses sous-couches.
  • elles permettent la représentation des éléments géométriques de type différent (points, lignes, contours, surfaces) et/ou des éléments liés à des tables attributaires différentes ;
  • dans GRASS, ce sont les « layers » (0, 1...) ;
  • Il est possible, mais pas recommandé, de mélanger les géométries différentes dans une même sous-couche, mais toutes les règles précédentes devront être respectées et appliquées en spécifiant explicitement le type de géométrie d'un objet. Par exemple, dans le cas d'une route, ligne, qui constitue aussi la limite d'un champ, entité surfacique :
    • le champ doit être défini comme une aire;
    • la route doit être définie comme une ligne;
    • le segment commun doit être défini à la fois comme segment de la ligne et comme arc / segment du contour de l'aire.
  • lors de la structuration en sous-couches, ces relations sont ajustées automatiquement.

une seule sous-couche                                     plusieurs sous-couches

Tout ça, c'est bien beau en théorie, mais comment cela s'applique-t-il en pratique ?

En pratique

Analysons le cas de l'importation d'un shapefile surfacique. Aprés la phase d'importation s.s. , v.build commence par le nettoyer (Passe 1) puis construit la topologie en plusieurs passes, si nécessaire.

Une fois encodé comme vecteur, avec ses aires, ses îles et la création des centroïdes attachés, comment se présente la topologie ?

représentation réelle de la topologie de voisinage

L'auteur de appuntigis.blogspot.com/2009/01/full-planar-topology-in-grass.html et appuntigis.blogspot.com/2009/01/full-planar-topology-in-grass-seconda.html (en italien) a décomposé la topologie complète d'un ensemble d'entités surfaciques représentées dans la figure suivante. Il fournit, de manière détaillée, toute la procédure, impressionnante, qui l'a conduit aux résultats.

• la topologie des arcs et des contours / polygones (figure reprise des articles cités)

• la topologie des noeuds (figure reprise des articles cités) :

• les tableaux de synthèse (fournis la démarche) :

an nIls l

représentation réelle de la topologie de réseau

Il a fait de même avec la topologie de réseau, appuntigis.blogspot.com/2009/02/random-network-analisys-in-grass.html. Après avoir généré un réseau, décomposé la topologie, il montre comment obtenir les divers éléments (voir aussi www.gdf-hannover.de/lit_html/grass60_v1.2_fr/node51.html). Les figures suivantes sont reprises de l'article cité :

Iso-distances (v.net.iso)                           Chemin le plus court (v.net.path, d.path)

arbres de Steiner de longueur minimale (v.net.steiner)                               sous-graphes (v.net.alloc)  

Si l'on veut vraiment comprendre les relations topologiques dans GRASS GIS, il est intéressant de refaire toutes les procédures des divers articles en les assimilant.

Représentation et topologie des rasters

Depuis le début de son histoire, la spécialité de GRASS a été le traitement des rasters.

• Ils sont tous représentés par un quadrillage matriciel (grille de points) qui contient implicitement des informations géométriques et topologiques ;
• l'unité fondamentale est la cellule (un pixel ou un voxel (pixel 3D)) dont les dimensions xy(z) définissent la résolution. A chaque pixels peuvent être associées 1 à n valeurs (matrices) ;
• ces matrices peuvent être codées sous forme de :
  • matrices bidimensionnelles avec des valeurs entières (CELL) ou décimales avec précision simple (FCELL) ou double (DCELL) ;
  • matrices tridimensionnelles (GRID3D) avec des valeurs décimales à précision simple ou double.

• les relations topologiques induites sont le voisinage / adjacence et la connectivité;

relations d'adjacence/voisinage dans un raster

• Grass permet de représenter :
  
  • les rasters 2D dont l'élement fondamental est le pixel x,y ;
  • les rasters dits 2.5D dont l'élement fondamental est toujours le pixel (x,y) mais où les valeurs z sont insérées comme valeurs dans la matrice ;
  • les véritables rasters et volumes 3D,  dont l'élément fondamental est le voxel (x,y,z) (z n'est plus une valeur comme un autre, mais une coordonnée) ;
  • un volume 3D est constitué d'une « pile » de rasters 2D ou 2.5D.

MNT 2D                                                                              MNT 2.5D

             

 

figures reprises de www.portailsig.org/content/grass-gis-et-paraview-la-modelisation-geologique-3d-pour-les-demunis-ou-les-enthousiastes (avec vecteur 3D en rouge)  et opengeology.pl/index.php

• Tous les outils pour l'analyse spatiale sont disponibles (r.reclass,r.resample, etc.), sans extension supplémentaire, de même que l'algèbre spatiale (r.mapcalc pour les rasters 2D et r3.mapcalc pour les rasters 3D) mais le sujet sera traité dans un autre article.

Conséquences pratiques

Vecteurs ou rasters ?

• En général, GRASS a plus de potentialités dans le traitement les rasters que dans celui des vecteurs (histoire oblige). Cependant, il est très facile de transformer un vecteur en raster (v.to.rast) en conservant les spécificités  du vecteur dans la(les) matrice(s) du raster (ici, valeur unique de la table attributaire = CAT du raster), puis de le traiter comme un raster. Dans les figures suivantes, vecteur et rasters donneront les mêmes informations si je clique sur un point, que ce soit en 2D ou en 2.5D (avec en plus, le z) ;

vecteur                   v.to.rast    -->    raster résultant

raster 2.5 D (les valeurs z sont ajoutées, à partir d'un MNT, avec r.mapcalc)

• c'est surtout vrai pour les modélisations 3D avec les nombreux modules pour l'interpolation de surfaces ou de volumes. Il n'y a ainsi pas de module standard pour créer des TIN (Triangulated irregular Network), les résultats de l'interpolation par la méthode des splines (v.surf.xx, r.surf.xx) donnant de meilleurs résultats. Les modules v.delaunay et v.voronoi sont néanmoins présents et si l'on veut vraiment des TINs il faut consulter grass.osgeo.org/wiki/Triangle_Mesh. Des exemples ont été donnés dans « Grass Gis et Paraview:la modélisation géologique 3D pour les démunis, ou les enthousiastes... »

Lors de l'importation

• le module v.in.ogr va toujours essayer de construire une topologie pour le vecteur avec le module v.build et les paramètres « snap » ou « Min_area » dans v.in.ogr (en particulier lors de l'importation de shapefiles qui n'ont aucune topologie) ;
• si il y a des erreurs, elles peuvent être sélectionnées avec le paramètre « error » puis corrigées automatiquement (jusqu'à un certain point) avec le module v.clean ou manuellement avec le module v.digit ;
• dans certains cas, les vecteurs n'ont pas besoin d'une topologie (dans le cas de grandes quantités de données comme les données LIDAR). C'est pourquoi certains modules autorisent l'importation de valeurs sans topologie (exemple le module v.in.ascii avec l'attribut « -b ») . Ils sont classés comme vecteurs de niveau 1 par rapport à ceux avec topologie qui sont classés au niveau 2 ;
• quelque soit le type de raster (images satellites, etc.), les divers modules d'importation le feront toujours sous une forme matricielle ;
• ces rasters seront toujours décomposés en leurs éléments essentiels (fichiers .red, .green et .blue pour les rasters multibande, par exemple). Il y a toujours moyen de recomposer l'image avec r.composite.

Lors de l'exportation

• si un vecteur est exporté sous forme de shapefile, la représentation résultante perdra toutes ses relations topologiques. Malheureusement, il n'y a pas encore de format d'exportation qui les conserve ;
• c'est la même chose avec les rasters ...

Avec le plugin grass dans QGIS

• GRASS n'est pas QGIS (géométrie et topologie) et si l'on veut utiliser le plugin grass pour appliquer les modules de GRASS dans QGIS, il est toujours préférable d'importer préalablement les objets dans un secteur (LOCATION) pour réellement bénéficier de toutes les possibilités.

Conclusions

J'espère  avoir donné une idée des géométries et de leurs relations topologiques dans GRASS, tant pour les vecteurs que pour les rasters.

Encore une fois, ce n'est pas ArcGIS avec sa très belle interface, fonctionnelle, et sa simplicité apparente, le tout avec la solide expérience acquise, qui masque souvent les difficultés (quoique...).  Ici, il faut « mettre les mains dans le cambouis » et l'apprentissage est long, avec, malheureusement, relativement peu de documentation (il faut fouiller) . Mais on devient vite efficace, une fois ces concepts bien maitrisés.

Tous les traitements ont été effectués sur Mac OS X avec GRASS GIS 6.4.1 RC2 et Inkscape pour les figures.

Site officiel : Topologie
Site officiel : espace métrique
Site officiel : Gis: A computing perspective (livre)
Site officiel : Voxel
Autres Liens : Python: le module Shapely, géométries, prédicats spatiaux, analyse spatiale, matrices de Clementini (DE-9IM), traitements de shapefiles ou autres, et représentation avec matplotlib
Autres Liens : Grass Gis et Paraview: la modélisation géologique 3D pour les démunis, ou les enthousiastes...

licence Creative Commons Paternité-Pas d'Utilisation Commerciale-Partage des Conditions Initiales à l'Identique Commerciale 2.0 France