Etape 5 – Lecture de données OSM

Le format des fichiers OSM étant basé sur le format XML, il importe de rapidement présenter ce dernier.

XML est un format standardisé permettant de décrire, sous forme textuelle, un ensemble d'éléments organisés en hiérarchie. C'est-à-dire qu'un élément peut avoir un ou plusieurs sous-éléments, que l'on nomme ses fils et qui peuvent eux-même avoir des fils, et ainsi de suite. En plus de ses fils, chaque élément peut posséder un ensemble d'attributs, composés d'un nom et d'une valeur associée.

Syntaxiquement, chaque élément dans un fichier XML est délimité par une balise ouvrante — composée du nom de l'élément entouré des chaînes < et > — et une balise fermante — composée du nom de l'élément entouré des chaînes </ et >. Les éventuels attributs d'un élément sont placés dans la balise ouvrante, après le nom de l'élément. Il est important de noter que ni les noms des éléments, ni ceux de leurs attributs, ne sont définis pas le standard XML, rendant ainsi ce format utilisable dans des situations diverses.

Par exemple, on peut imaginer utiliser le format XML pour décrire un carnet d'adresses. Dans ce cas, l'élément principal du fichier pourrait être nommé addressbook et ses fils seraient les personnes stockées dans le carnet. Une personne pourrait être représentée par un élément person et avoir pour fils des éléments décrivant ses caractéristiques, comme son nom de famille, son prénom, son (ou ses) adresses, etc. Etant donné qu'une personne peut avoir plus d'une adresse ou plus d'un numéro de téléphone, on pourrait imaginer que chaque élément représentant l'un ou l'autre possède un attribut tag permettant de les différencier.

Un exemple très simple d'un fichier XML représentant un carnet d'adresse organisé de la sorte est donné ci-dessous.

<addressbook>
  <person>
    <firstname>Marie</firstname>
    <middlename>Jeanne</middlename>
    <middlename>Karine</middlename>
    <lastname>Dupond</lastname>
    <phone tag="landline">032 123 45 67</phone>
  </person>
  <person>
    <lastname>Durand</lastname>
    <firstname>Paul</firstname>
    <address tag="home">
      <street>Avenue du Léman</street>
      <number>12</number>
      <postcode>1000</postcode>
      <city>Lausanne</city>
    </address>
    <address tag="work">
      <street>Avenue des Alpes</street>
      <number>13</number>
      <postcode>1000</postcode>
      <city>Lausanne</city>
    </address>
  </person>
</addressbook>

Il faut noter que certaines caractéristiques des personnes qui sont ci-dessus stockées dans des fils de l'élément person pourraient très bien être stockées dans ses attributs. Souvent, lorsqu'on définit un format basé sur XML, il est difficile de décider si une caractéristique doit être représentée comme un attribut ou comme un élément fils, et en conséquence ce choix est souvent fait de manière arbitraire.

Les données de la carte mondiale OpenStreetMap sont stockées dans un (énorme) fichier au format OSM, basé sur le format XML décrit ci-dessus. De ce fichier unique peuvent être extraits de plus petits fichiers contenant, par exemple, uniquement les entités se trouvant dans une zone géographique déterminée. Dans le cadre de ce projet, vous ne travaillerez qu'avec de tels extraits, qui vous sont fournis dans cette étape.

Pour mémoire, une carte OSM est formée uniquement de trois types d'entités : des nœuds, des chemins et des relations. Dans un fichier OSM, ces trois types d'entités apparaissent toujours dans le même ordre : les nœuds viennent en premier, suivis des chemins et finalement des relations. Ces trois types d'éléments sont tous des fils d'un unique élément dont le nom est osm.

L'exemple ci-dessous est un fichier OSM valide décrivant le pourtour du bâtiment BC de l'EPFL. Etant donné ce que vous savez au sujet des entités OSM et du format XML, vous devriez être capables de le comprendre en grande partie, mais des informations détaillées concernant les différents types d'éléments qu'il contient sont données plus bas.

A noter que la première ligne de ce fichier ne décrit pas un élément mais donne simplement la version du format XML et l'encodage des caractères utilisés.

<?xml version="1.0" encoding="UTF-8"?>
<osm version="0.6">
  <node id="1" lat="46.5182404" lon="6.5616727"/>
  <node id="2" lat="46.5188218" lon="6.5616658"/>
  <node id="3" lat="46.5188294" lon="6.5621886"/>
  <node id="4" lat="46.5182432" lon="6.5621964"/>
  <way id="5">
    <nd ref="1"/>
    <nd ref="2"/>
    <nd ref="3"/>
    <nd ref="4"/>
    <nd ref="1"/>
    <tag k="building" v="yes"/>
    <tag k="name" v="BC"/>
  </way>
</osm>

Un des (rares) intérêts du format XML est qu'il existe beaucoup de bibliothèques permettant de lire assez facilement des fichiers de ce type. Pour des raisons historiques, la bibliothèque Java contient même deux ensembles de classes distincts permettant de les manipuler. Ici, seule la petite partie utile au projet du plus récent de ces ensembles de classe, qui se trouve dans le paquetage org.xml.sax, est rapidement décrite.

L'interface XMLReader représente un lecteur de document XML, c-à-d un objet capable de lire un fichier XML. XMLReader étant une interface, il n'est pas possible d'en créer une instance. Pour obtenir un nouveau lecteur de document XML, il convient donc d'appeler la méthode statique createXMLReader de la classe XMLReaderFactory qui, comme son nom l'indique, permet de fabriquer de nouveaux lecteurs de document XML.

Pour qu'un tel lecteur soit utile, il faut lui attacher un objet, nommé le gestionnaire de contenu (content handler), qui implémente l'interface ContentHandler. Ce gestionnaire est fourni par l'application désirant interpréter le contenu du fichier XML, ici notre projet.

Au fur et à mesure que le lecteur analyse le fichier XML qu'on lui fournit, il appelle des méthodes du gestionnaire de contenu pour l'avertir de différents événements (events). Par exemple, le fait que la balise ouvrante d'un élément XML ait été rencontrée constitue un événement, qui provoque l'appel de la méthode startElement du gestionnaire de contenu ; le fait que la balise fermante d'un élément XML ait été rencontrée constitue aussi un événement, provoquant quant à lui l'appel de la méthode endElement. Ces deux méthodes reçoivent des arguments donnant des détails au sujet de l'événement. Les deux seuls utiles à ce projet sont ceux donnant le nom de l'élément rencontré — qName dans la documentation — et les attributs attachés à cet élément — atts dans la documentation. Ces derniers sont une instance d'une classe implémentant l'interface Attributes, qui possède p.ex. la méthode getValue permettant d'obtenir la valeur d'un attribut étant donné son nom.

A noter que la manière la plus simple de créer un gestionnaire de contenu consiste à définir une sous-classe (anonyme) de la classe DefaultHandler, en réimplémentant uniquement les méthodes correspondant aux événements intéressants pour l'application.

Pour obtenir le contenu du fichier XML à lire, le lecteur XML utilise une source d'entrée (input source), qui est une instance de la classe InputSource. Cette classe possède un constructeur qui crée une telle source à partir d'un flot d'entrée Java de type InputStream et il est donc très simple de lire un document XML provenant d'un fichier. Cela reste vrai si celui-ci est compressé au moyen de gzip — ce qui est le cas d'une partie de ceux que nous vous fournissons — car il suffit alors d'utiliser le flot GZIPInputStream pour décompresser le contenu du fichier avant d'en faire une source d'entrée.

Comme l'ensemble de classes et d'interfaces décrit brièvement ci-dessus n'est pas forcément simple à comprendre, un petit programme d'exemple est donné ci-dessous. Ce programme lit un fichier nommé in.xml et affiche un message à l'écran chaque fois que la balise ouvrante ou fermante d'un élément est rencontré. Dans ce premier cas, il affiche également la valeur de l'attribut nommé lon attaché à l'élément, ou null si celui-ci n'existe pas.

import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStream;

import org.xml.sax.Attributes;
import org.xml.sax.InputSource;
import org.xml.sax.SAXException;
import org.xml.sax.XMLReader;
import org.xml.sax.helpers.DefaultHandler;
import org.xml.sax.helpers.XMLReaderFactory;

class XMLExample {
  public static void main(String[] args)
    throws IOException, SAXException {
    try (InputStream i = new FileInputStream("in.xml")) {
      XMLReader r = XMLReaderFactory.createXMLReader();
      r.setContentHandler(new DefaultHandler() {
          private int indentation = 0;

          @Override
          public void startElement(String uri,
                                   String lName,
                                   String qName,
                                   Attributes atts)
            throws SAXException {
            String lon = atts.getValue("lon");
            printIndented("start " + qName
                          + " (" + lon + ")");
            indentation += 2;
          }

          @Override
          public void endElement(String uri,
                                 String lName,
                                 String qName) {
            indentation -= 2;
            printIndented("end " + qName);
          }

          private void printIndented(String m) {
            for (int i = 0; i < indentation; ++i)
              System.out.print(" ");
            System.out.println(m);
          }
        });
      r.parse(new InputSource(i));
    }
  }
}

Par exemple, si le fichier in.xml est celui décrivant le bâtiment BC présenté ci-dessus, ce programme affiche :

start osm (null)
  start node (6.5616727)
  end node
  start node (6.5616658)
  end node
  start node (6.5621886)
  end node
  start node (6.5621964)
  end node
  start way (null)
    start nd (null)
    end nd
    start nd (null)
    end nd
    start nd (null)
    end nd
    start nd (null)
    end nd
    start nd (null)
    end nd
    start tag (null)
    end tag
    start tag (null)
    end tag
  end way
end osm

Un graphe non orienté \(G = (V, E)\) est composé d'un ensemble \(V\) de sommets et d'un ensemble \(E\) de paires de sommets, nommées arêtes. Un tel graphe peut être visualisé en dessinant un cercle pour chacun de ses sommets et en reliant par une ligne toute paire de cercles représentant des sommets pour lesquels il existe une arête.

Par exemple, la figure ci-dessous montre une telle représentation d'un graphe \(G = (V, E)\) où l'ensemble des sommets \(V\) est \(\{a, b, c, d, e\}\) et l'ensemble des arêtes \(E\) est \(\{(a, b), (a, c), (a, e), (b, c), (b, e)\}\).

La représentation d'un graphe par un ensemble de sommets et un ensemble d'arêtes présentée ci-dessus est celle habituellement utilisée en mathématiques. Elle a l'avantage d'être simple, mais n'est pas forcément la plus adaptée à la représentation et à la manipulation efficace d'un graphe non orienté en informatique, pour différentes raisons.

De nombreuses autres représentations d'un graphe non orienté sont donc utilisées en pratique, dont une seule sera décrite ici, celle que vous mettrez en œuvre pour cette étape. Nous nommerons cette représentation table d'adjacence, et son idée consiste simplement à représenter un graphe sous la forme d'une table associative qui fait correspondre à chaque sommet du graphe l'ensemble de ses voisins. Ainsi, la table d'adjacence du graphe de la figure ci-dessus est :

Par rapport à la représentation mathématique habituelle, cette représentation a le petit inconvénient d'être redondante — puisqu'à une arête correspondent toujours deux entrées dans la table — mais l'avantage de permettre de trouver très rapidement les voisins d'un sommet. Etant donné que cette opération est fréquente, le jeu en vaut la chandelle.

La classe OSMMap du paquetage ch.epfl.imhof.osm, publique, finale et immuable, représente une carte OpenStreetMap, c'est-à-dire un ensemble de chemins et de relations. Les nœuds ne sont pas stockés dans la carte elle-même puisque, dans le cadre de ce projet, ils ne sont jamais utilisés individuellement mais servent uniquement à construire des chemins.

La classe OSMMap est dotée d'un unique constructeur public :

• OSMMap(Collection<OSMWay> ways, Collection<OSMRelation> relations), qui construit une carte OSM avec les chemins et les relations donnés.

Notez que la raison pour laquelle les chemins et les relations sont passés sous forme de collection à ce constructeur et pas sous forme de liste est que cela simplifie l'écriture du bâtisseur, comme vous le constaterez. Dans un soucis de cohérence, il aurait été plus propre de faire en sorte que tous les constructeurs similaires du projet acceptent aussi des collections, mais il est malheureusement trop tard pour changer cela.

A l'interne, ces collections doivent néanmoins être stockées sous forme de listes, comme d'habitude.

La classe OSMMap possède de plus les deux méthodes publiques ci-dessous :

• List<OSMWay> ways(), qui retourne la liste des chemins de la carte.
• List<OSMRelation> relations(), qui retourne la liste des relations de la carte.

La classe OSMMap.Builder, imbriquée statiquement dans la classe OSMMap, publique et finale, sert de bâtisseur à la classe OSMMap. Contrairement à la carte elle-même, qui ne stocke pas les nœuds, le bâtisseur les stocke. Cela permet aux utilisateurs du bâtisseur d'obtenir le nœud correspondant à un identifiant donné, ce qui est souvent utile.

La classe OSMMap.Builder ne possède pas d'autre constructeur que celui par défaut mais est dotée des méthodes publiques suivantes :

• void addNode(OSMNode newNode), qui ajoute le nœud donné au bâtisseur,
• OSMNode nodeForId(long id), qui retourne le nœud dont l'identifiant unique est égal à celui donné, ou null si ce nœud n'a pas été ajouté précédemment au bâtisseur,
• void addWay(OSMWay newWay), qui ajoute le chemin donné à la carte en cours de construction,
• OSMWay wayForId(long id), qui retourne le chemin dont l'identifiant unique est égal à celui donné, ou null si ce chemin n'a pas été ajouté précédemment au bâtisseur,
• void addRelation(OSMRelation newRelation), qui ajoute la relation donnée à la carte en cours de construction,
• OSMRelation relationForId(long id), qui retourne la relation dont l'identifiant unique est égal à celui donné, ou null si cette relation n'a pas été ajoutée précédemment au bâtisseur,
• OSMMap build(), qui construit une carte OSM avec les chemins et les relations ajoutés jusqu'à présent.

La classe OSMMapReader du paquetage ch.epfl.imhof.osm, publique, finale et non instanciable — c-à-d que son constructeur par défaut est privé et vide — permet de construire une carte OpenStreetMap à partir de données stockées dans un fichier au format OSM. Cette classe est équipée d'une seule méthode publique et statique :

• OSMMap readOSMFile(String fileName, boolean unGZip), qui lit la carte OSM contenue dans le fichier de nom donné, en le décompressant avec gzip si et seulement si le second argument est vrai. Lève l'exception SAXException en cas d'erreur dans le format du fichier XML contenant la carte, ou l'exception IOException en cas d'autre erreur d'entrée/sortie, p.ex. si le fichier n'existe pas.

Il va sans dire que cette méthode doit utiliser les très nombreux bâtisseurs définis précédemment pour construire les entités qui constituent la carte, ainsi que la carte elle-même. De plus, comme cela a été dit plus haut, toute entité qui référence une autre entité non définie dans le fichier doit être considérée comme incomplète et ne doit pas être ajoutée à la carte. Les méthodes setIncomplete et isIncomplete des bâtisseurs d'entités peuvent être utilisées pour gérer ce cas.

Pour transformer les chaînes de caractères extraites du fichier XML et représentant les identifiants uniques et les longitudes/latitudes des nœuds, les méthodes parseLong et parseDouble — similaires à la méthode parseInt présentée à l'étape 3 — vous seront d'un grand secours. Vous pouvez dans tous les cas faire l'hypothèse (raisonnable) que les éléments et attributs censés contenir de tels nombres en contiennent effectivement, et ne pas traiter l'exception NumberFormatException levée par les méthodes susmentionnées.

La classe Graph du paquetage ch.epfl.imhof, publique, finale et immuable (ssi les nœuds sont eux-même immuables), représente un graphe non orienté. Il s'agit d'une classe générique dont le paramètre de type, N ci-dessous, représente le type des nœuds du graphe. Cette classe est dotée d'un unique constructeur public :

• Graph(Map<N, Set<N>> neighbors), qui construit un graphe non orienté avec la table d'adjacence donnée.

En plus de ce constructeur, la classe Graph possède les méthodes publiques suivantes :

• Set<N> nodes(), qui retourne l'ensemble des nœuds du graphe.
• Set<N> neighborsOf(N node), qui retourne l'ensemble des nœuds voisins du nœud donné. Lève l'exception IllegalArgumentException si le nœud donné ne fait pas partie du graphe.

La classe Graph.Builder, imbriquée statiquement dans la classe Graph, publique et finale, sert de bâtisseur à la classe Graph. Elle est bien entendu générique, tout comme la classe Graph. Elle ne possède pas d'autre constructeur que celui par défaut mais est dotée des méthodes publiques suivantes :

• void addNode(N n), qui ajoute le nœud donné au graphe en cours de construction, s'il n'en faisait pas déjà partie.
• void addEdge(N n1, N n2), qui ajoute une arête entre les deux nœuds donnés au graphe en cours de construction. En d'autres termes, cette méthode ajoute le premier nœud à l'ensemble des voisins du second, et vice versa. Lève l'exception IllegalArgumentException si l'un des nœuds n'appartient pas au graphe en cours de construction.
• Graph<N> build(), qui construit le graphe composé des nœuds et arêtes ajoutés jusqu'à présent au bâtisseur.

Comme précédemment, nous ne vous fournissons pas de tests unitaires pour cette étape mais uniquement un fichier de vérification de noms, contenu dans une archive Zip à importer dans votre projet.

En plus de ces tests, nous mettons à votre disposition trois fichiers OSM contenant des extraits de villes suisses et de leurs environs. Les données contenues dans ces extraits sont celles du 3 mars 2015, et nous les utiliserons jusqu'à la fin du projet. Ces fichiers, compressés avec gzip, sont très volumineux et vous êtes donc priés de les stocker de manière permanente après les avoir téléchargés :

1. Lausanne (29 Mo),
2. Berne (34 Mo),
3. Interlaken (22 Mo).

En plus de ces volumineux extraits, nous vous en fournissons deux plus petits, qui vous serviront de point de départ pour tester votre programme :

1. le bâtiment BC, bâtiment sans trou et donc décrit par un simple chemin (il s'agit du fichier donné plus haut en exemple),
2. le Learning center, bâtiment à trous et donc décrit par une relation de type multipolygone.

Attention, contrairement aux fichiers de données réelles, ceux-ci ne sont pas compressés avec gzip.

Si vous le désirez, vous pouvez ajouter ces fichiers et d'autres fichiers OSM de test à votre projet, sous forme de resources, afin d'y accéder facilement. Pour ce faire, suivez les indications données dans la page consacrée aux resources de notre guide Eclipse.