# Introduction

De 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.

Nous 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.

Nous 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

Les 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".

Leur 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

La 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.

En 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.

La 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 :

Malheureusement, l’évaluation du paramètre est délicate, car sa valeur optimale dépend de la densité des points de données. Pour trois points les profils de terrain obtenus dépendent de .

<figure><img src="image_1.png" /></figure>

Fig. 1 : Variation des profils en fonction du paramètres.

Valeur de trop faible Valeur de trop élevée

La 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.

La 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

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

<figure><img src="image_2.png" /></figure>

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

L’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 :

<figure><img src="image_3.png" /></figure>

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

La 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.

La 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

La 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

Cette é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

Des 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

Cette 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.

<figure><img src="image_4.png" /></figure>

<figure><img src="image_5.png" /></figure>

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

Le 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.

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

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

Des 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

Le 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

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

<figure><img src="image_6.png" /></figure>

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.

- 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 Ymin servent donc à positionner la grille par rapport aux données.

Remarque : on veillera à ce que Xmin soit 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.

- 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.

- 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).

Pour 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

<figure><img src="image_7.png" /></figure>

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

## Formats des fichiers

a) 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.

b) 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

Le 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.