Navigation – Plan du site
1999
77

GenMNT : un outil simple pour la génération de modèles numériques de terrains

Christophe Poix et E. Sefiha

Résumés

Dans le cadre des travaux concernant les modélisations et les simulations paysagères, l’utilisation d’un modèle numérique de terrain est indispensable. Cependant, l’achat d’un tel modèle n’est pas toujours possible pour la zone et la précision souhaitées. Nous avons développé un logiciel simple permettant de fabriquer des modèles numériques à partir de mesures d’altitudes prises sur le terrain.
L’objet de cet article est de décrire le programme GenMNT distribué librement sur le site web de Cybergeo. Le mode d’emploi est accompagné d’une présentation rapide et non exhaustive des principales méthodes d’interpolation. Le fonctionnement de notre programme (basé sur la triangulation de Delaunay) est décrit pas à pas. Enfin, nous insistons sur la simplicité de mise en oeuvre du logiciel et sur son utilisation en amont du produit Vistapro pour construire des vues paysagères 3D réalistes.

Haut de page

Texte intégral

Introduction

1De plus en plus, les applications informatiques traitant des données géographiques nécessitent l’utilisation d’un modèle numérique de terrain (MNT). Bien que de tels modèles existent dans le commerce, leur utilisation n’est pas toujours aisée et l’échelle n’est pas toujours adaptée au problème que l’on souhaite résoudre. L’objectif de cet article est de présenter une méthode simple pour établir des MNT à partir de mesures d’altitude relevées sur le terrain ou sur des cartes. L’étude a été menée dans le but de réaliser des images paysagères réalistes à l’aide du logiciel Vistapro . Une application a été présentée dans [Michelin 1997]. Notre étude a abouti au développement du logiciel GenMNT [Poix 1997] qui est distribué librement sur le site Internet http ://www.cybergeo.presse.fr. GenMNT peut être facilement adapté pour d’autres logiciels de visualisation ou de traitement de données géographiques.

2Nous allons exposer brièvement les principales méthodes permettant d’établir une grille dans laquelle chaque noeud représente une valeur d’altitude, à partir d’un ensemble de relevés topographiques (nuage de points X,Y,Z). Il existe une littérature abondante sur le sujet, y compris des études comparant les différentes approches. De plus, une très bonne introduction est présentée dans [Burrough 1998]. L’excellent site web de Jo Wood (http ://www.geog.le.ac.uk/jwo/research) propose également des programmes de triangulation et d’interpolation.

3Nous détaillerons la méthode retenue pour la réalisation de GenMNT. Enfin, nous présenterons un mode d’emploi du logiciel en précisant notamment les formats des fichiers d’entrée et de sortie.

Méthodes d’interpolation

4Les méthodes les plus couramment utilisées consistent à calculer des valeurs d’altitudes par des moyennes pondérées des différents points de données [Woodwark 1988]. Nous avons comparé les méthodes "kriging", "distance inverse" et "triangulation".

5Leur performance étant proportionnelle à la difficulté de mise en oeuvre, nous avons cherché un compromis en donnant la priorité au " réalisme " du modèle de terrain obtenu.

Choix d’une méthode

6La méthode "kriging" est basée sur des techniques de géostatistique pour calculer l’autocorrélation entre les points de données. Elle recherche un estimateur non biaisé de la variance minimale. En théorie, cette méthode est optimale du point de vue de la précision obtenue. En pratique, les performances sont liées au choix judicieux de divers paramètres qui dépendent de la répartition des points de données. De plus, la mise en oeuvre peut impliquer des puissances de calcul qui dépassaient les moyens informatiques dont nous disposions pour cette étude.

7En effet, nous souhaitions obtenir des grilles 1 000 x 1 000 (un million de noeuds) à partir d’environ 800 points de mesure. C’est pourquoi nous avons écarté cette méthode.

8La méthode "distance inverse" est très simple à mettre en oeuvre. Elle consiste à calculer les altitudes des noeuds de la grille en utilisant une moyenne pondérée des altitudes des points de données. Les pondérations étant inversement proportionnelles aux distances séparant le noeud considéré et les différents points de données. Pour un noeud de coordonnées (x,y,z) et n points de coordonnées (xi, yi, zi) on utilise la formule suivante :

Valeur de Image7 trop faible Valeur de Image8 trop élevée

9La méthode "distance inverse" est adaptée quand la densité des points de mesure varie peu sur la zone étudiée. Les irrégularités du relief et les points particuliers du terrain (sommets, limites, clôtures, bâtiments) ne permettent pas toujours un tel type de relevé. Dans ce cas, le modèle de terrain obtenu est peu réaliste.

10La méthode par triangulation est basée sur l’idée qui consiste à n’utiliser que les points voisins du noeud considéré. Quand plus de trois points sont utilisés des problèmes de continuité de la surface résultante peuvent apparaître. Ils sont alors corrigés par l’utilisation d’une méthode de lissage appropriée. Lorsque trois points seulement sont utilisés, la méthode consiste à définir un maillage triangulaire sur la surface étudiée, les points de mesure étant les sommets des triangles. Des interpolations linéaires peuvent ainsi être calculées à l’intérieur de chaque facette triangulaire. Le modèle de terrain obtenu est assez proche de la réalité si le nombre de points de mesure est suffisant. Si nécessaire, les effets de " facettes " peuvent être atténués par un lissage.

Triangulation et interpolation linéaire

11A partir d’un nuage de points quelconque, il est possible de définir un grand nombre de maillages différents.

Fig. 2 : Il existe deux maillages possibles pour quatre points de données.

12L’objectif étant d’approximer l’altitude de noeuds qui se situent dans les triangles, il est souhaitable de choisir une triangulation qui minimise la "longueur" des facettes. Autrement dit, l’interpolation sera d’autant plus réaliste que les formes des facettes se rapprochent du triangle équilatéral. Ce critère est vérifié par la triangulation de Delaunay Delaunay 1934 qui a la propriété de maximiser le plus petit angle de tous les triangles du maillage. Cette triangulation particulière peut être réalisée très facilement en utilisant son "duel" mathématique appelé diagramme de Voronoï [ Voronoï 1908 ou encore tessellation de Dirichlet Dirichlet 1850 . La figure 3 montre la tessellation de Dirichlet et la triangulation de Delaunay associée pour un nuage de 15 points :

Fig. 3 : Tessellation de Dirichlet et triangulation de Delaunay pour un nuage de 15 points

13La tessellation de Dirichlet consiste en un découpage de l’espace en régions définies autour des points de données. Chaque point du plan est rattaché à la région associée au point de données le plus proche. Deux points de données sont reliés par un segment dans la triangulation de Delaunay, quand leur région respective dans la tessellation de Dirichlet ont une frontière commune.

14La triangulation étant réalisée, le calcul de l’interpolation linéaire est simple. Pour chaque noeud de la grille, il suffit de trouver le triangle concerné. L’altitude du noeud est calculée à l’aide de l’équation du plan portant la facette triangulaire.

Réalisation pratique

15La méthode décrite précédemment a été programmée et testée à l’aide du produit "Visual-Basic" de Microsoft. Bien que ce langage de programmation ne soit pas parmi les plus performants, sa souplesse d’utilisation nous a permis de développer rapidement les 60 lignes de code qui constituent le coeur de l’application GenMNT. L’algorithme utilisé se déroule en trois phases :

Tessellation de Dirichlet

16Cette étape est la plus coûteuse en temps de calcul. Chaque noeud de la grille est étiqueté en fonction du point de donnée le plus proche. La fonction de calcul de distance est appelée LxHxN fois si la grille est formée de LxH noeuds. N représente le nombre de points de données, L la largeur de la grille et H la hauteur de la grille.

Triangulation de Delaunay

17Des balayages verticaux et horizontaux de la matrice des noeuds permettent de détecter les régions mitoyennes et donc de trouver les segments constitutifs de la triangulation. Une liste des facettes triangulaires est ensuite établie à partir de la liste des segments.[Laurini 1989],[Gondran 1985].

Interpolation

18Cette phase est la plus rapide. Pour chaque noeud de la grille, on recherche la facette d’appartenance, puis l’altitude calculée grâce à l’équation du plan qui porte la facette. Si aucune facette n’est trouvée (noeud hors maillage) une constante est affectée à l’altitude du noeud.

Fig. 4a  : Tessellation de Dirichlet Fig. 4b  : Triangulation de Delaunay

19Le choix de la méthode et des algorithmes permet donc à chacun de disposer d’un logiciel d’interpolation en 3D pour les modèles numériques de terrain fonctionnant sur des ordinateurs relativement modestes. Ces mêmes algorithmes imposent quelques précautions lors de l’utilisation du programme.

  • Pour un fonctionnement correct de l’algorithme de triangulation, et notamment de la phase de constitution des triangles à partir des segments, il est indispensable que tous les points de données se trouvent à l’intérieur de la grille (zone de travail).

  • La présence de deux points de données ayant les mêmes coordonnées x,y implique la création d’une facette verticale. Cette situation est incompatible avec la méthode d’interpolation.

  • La mémoire (RAM) disponible limite la résolution de la grille. Chaque noeud occupe 4 octets, en plus de l’application et du système d’exploitation.

20Soit : 4 Mo supplémentaires pour une grille 1 000 x 1 000

2116 Mo supplémentaires pour une grille 2 000 x 2 000

22Des fonctions de lecture et écriture des données ont été ajoutées au programme que nous venons de décrire pour constituer GenMNT. Les coordonnées des points de mesure sont lues dans un fichier texte que nous décrivons au paragraphe suivant. L’application a été développée dans le cadre du calcul d’images de synthèses ; c’est pourquoi le modèle de terrain est sauvegardé dans un format BIN directement lisible par VistaproTM . Enfin, une interface utilisateur a été ajoutée pour faciliter l’ajustement des divers paramètres : résolution de la grille, taille des cellules, coordonnées, localisation des fichiers de données et de sauvegarde.

GenMNT : Mode d’emploi

23Le logiciel se présente sous forme d’un exécutable "GenMNT.exe" de très petite taille. Pour fonctionner, il fait appel à la bibliothèque "runtime" de Visual-Basic "VBRUN300.DLL", qui doit se trouver dans le même répertoire que l’exécutable ou dans le dossier "system" de Windows.

L’interface utilisateur

24Au lancement du programme, une fenêtre similaire à celle de la figure 5 apparaît à l’écran.

Fig. 5 : Interface utilisateur de GenMNT

  • La partie gauche de la fenêtre, intitulée Source permet de désigner le fichier d’entrée qui contient les points de données. Pour cela, l’utilisateur sélectionne le disque puis le répertoire où se trouvent les données. Enfin, il sélectionne le fichier d’entrée dont l’extension est nécessairement : "DAT".

  • La partie droite de l’écran intitulée Destination permet de préciser la localisation et le nom du fichier de sortie, créé par GenMNT. Si l’utilisateur sélectionne un fichier " .BIN " existant, celui-ci sera remplacé par la nouvelle version.

  • Avant de générer un modèle de terrain, il est nécessaire de préciser au logiciel la taille et la position de la grille par rapport aux points de données. Pour cela, l’utilisateur dispose des six cases situées dans la partie centrale de la fenêtre.

25- Origine : Les valeurs affectées à Xmin et Ymin indiquent le coin inférieur gauche de la grille. Ces valeurs sont indiquées en coordonnées réelles, c’est à dire dans le même système de coordonnées que les points de mesure. Xmin et Yminservent donc à positionner la grille par rapport aux données.

26Remarque : on veillera à ce que Xminsoit inférieur à toute valeur xi présente dans le fichier d’entrée. De même Ymin sera inférieure à tout yi, sans quoi des points de données se situeraient à l’extérieur de la grille.

27- Taille de la grille : Les valeurs nbcol et nblig permettent de dimensionner le fichier de sortie. Les tailles de modèles de terrain utilisées en standard par Vistapro sont : 258x258, 514x514 et 1026x1026. GenMNT permet de générer des modèles de toutes tailles, y compris des grilles rectangulaires.

28- Taille des cellules : largeur et hauteur permettent de donner l’échelle de la grille. Les valeurs indiquent l’espacement des noeuds horizontalement et verticalement. Les unités sont les mêmes que pour les xi, yi des points de données (coordonnées réelles).

29Pour qu’aucun point de donnée ne se trouve à l’extérieur de la grille, on vérifiera que :

  • tous les xi sont inférieurs à Xmin + nbcol x largeur

  • tous les yi sont inférieurs à Ymin + nblig x hauteur

30Après sauvegarde des résultats dans le fichier .BIN, la fenêtre disparaît et le programme s’arrête.

Formats des fichiers

31a) Le fichier d’entrée (.DAT) est un fichier texte qui pourra être établi à l’aide de n’importe quel éditeur ou d’une table. Le caractère " espace " est utilisé comme séparateur.
La première ligne du fichier contient le nombre de points de données.
Les lignes suivantes contiennent les coordonnées xi, yi, zi, des points (un point par ligne).
Les valeurs xi et yi sont des nombres décimaux (coordonnées réelles), alors que la valeur d’altitude zi est représentée par un nombre entier compris entre - 32 768 et + 32 767. On utilisera donc généralement des unités arbitraires permettant d’avoir une bonne dynamique sur la zone étudiée.

32b) Les fichiers .BIN acceptés par Vistapro se présentent sous forme d’une suite de valeurs d’altitude, qui sont des nombres entiers codés sur deux octets. La taille de ce fichier sera donc de 2 x nblig x nbcol octets.
Ce format rudimentaire a l’avantage d’être simple à utiliser De plus, il peut être converti dans les formats suivants : PCX (image), DEM (standard de modèle de terrain), DXF (modeleur).

Conclusion

33Le logiciel GenMNT présenté dans cet article n’est qu’un prototype. Sa diffusion et son utilisation intensive nécessiteraient de nombreuses améliorations au niveau de la robustesse (détection automatique des points hors grille) et au niveau de l’optimisation des temps de calcul (utilisation d’un langage compilé du type C++). Néanmoins, il a permis de montrer qu’un choix judicieux des algorithmes permet de développer rapidement un outil pour générer des modèles numériques de terrain. L’utilisation de logiciels de visualisation paysagère et de Systèmes d’Information Géographique est incontournable. Pourtant elle soulève des problèmes d’interfaçage, de collecte des données et de leur mise en forme. Le développement d’outils pour résoudre ces problèmes est une solution qui permet une utilisation optimale des logiciels de traitement de données géographiques et qui favorise leur application à des cas concrets.

Haut de page

Bibliographie

Burrough 1998 : P.A. Burrough., R.A. McDonnell. Principles of Geographical Information Systems. Oxford University Press.

Delaunay 1934 : B. Delaunay. Sur la sphère vide. Bulletin of academy of sciences of the USSR, p. 793-800.

Dirichlet 1850 : G.L. Dirichlet. Über die reduction der positiven quadratischen formen mit drei unbestimmten ganzen zalen. J.Reine u. Angew. Math., 40 :209-227.

Gondran 1985 : Gondran M., Minoux M. Graphes et algorithmes. Paris EYROLLES. Collection de le direction des études et recherches d’Electricité De France, n°37, 586p.

Laurini 1989 : Laurini R., Milleret-Raffort F.. L’ingénierie des connaissances spatiales, Paris, HERMES 64 p.

Michelin 1997 : Y. Michelin, C. Poix, E. Josien, C. Cougoul. Pédogenèse en milieu volcanique complexe : l’estive expérimentale de Ternant (massif central français). Quatrième conférence internationale de géomorphologie. Bologne Italie.

Poix 1997 : C. Poix. GenMNT : logiciel pour établir des modèles numériques de terrains. ENITA de Clermont-Ferrand.

Voronoï 1908 : M.G. Voronoï. Nouvelles applications des paramètres continus à la théorie des formes quadratiques. J.Reine u. Angew. Math, 134 : 198-287.

Woodwark 1988 : J. Woodwark. Calcul de formes par ordinateur. Paris, Milan, Barcelone, Mexico, MASSON. 167 p.

Haut de page

Pour citer cet article

Référence électronique

Christophe Poix et E. Sefiha, « GenMNT : un outil simple pour la génération de modèles numériques de terrains », Cybergeo : European Journal of Geography [En ligne], Systèmes, Modélisation, Géostatistiques, document 77, mis en ligne le 10 février 1999, consulté le 27 avril 2017. URL : http://cybergeo.revues.org/5050 ; DOI : 10.4000/cybergeo.5050

Haut de page

Auteurs

Christophe Poix

ENITAC, Dépt sciences de l 'ingénieur, Marmilhat, F-63370 Lempdes, Tel. 04-73-98-13-61
poix@gentiane.enitac.fr

Articles du même auteur

E. Sefiha

ENITAC, Dépt sciences de l 'ingénieur, Marmilhat, F-63370 Lempdes, Tel. 04-73-98-13-61
sefiha@gentiane.enitac.fr

Haut de page

Droits d’auteur

© CNRS-UMR Géographie-cités 8504

Haut de page