Etape 8 – Cartes en tuiles

Comme cela a été expliqué dans l'énoncé de l'étape 1, les services cartographiques en ligne comme OpenStreetMap permettent de visualiser des cartes du monde entier jusqu'à des échelles très petites.

A la plus grande échelle, qui correspond au niveau de zoom 0, le monde entier est représenté par une carte carrée de 256 pixels de côté. A chaque niveau de zoom successif, la taille de cette carte double dans chaque dimension. Ainsi, au niveau de zoom 1, le monde est représenté sur une carte de 512 pixels de côté. De manière générale, au niveau de zoom \(z\), le monde est représenté sur une carte carrée de \(2^{z+8}\) pixels de côté.

La plupart des systèmes cartographiques en ligne permettent de descendre jusqu'à un niveau de zoom proche de 20. OpenStreetMap, par exemple, permet actuellement d'aller jusqu'au niveau 19. A cette échelle, le monde est représenté par une carte de 2²⁷ = 134'217'728 pixels de côté, soit un total de (2²⁷)² pixels — un peu plus de 18 péta-pixels !

Il va sans dire qu'il n'est pas imaginable de transférer via le réseau une telle image, d'autant plus que seule une toute petite partie sera examinée par l'utilisateur. Pour cette raison, les systèmes cartographiques découpent les images des cartes en petites images de 256 pixels de côté, appelées tuiles. Lorsqu'un utilisateur désire consulter une zone d'une carte à une échelle donnée, seules les tuiles visibles dans cette zone lui sont transmises et assemblées au moment de l'affichage.

Les tuiles sont identifiées par trois coordonnées : leur niveau de zoom, leur position x et leur position y. La figure ci-dessous montre l'unique tuile de niveau 0 et les quatre tuiles de niveau 1, avec leurs coordonnées. (Les images ont été redimensionnées).

Ces trois coordonnées correspondent de manière très directe aux coordonnées OSM. Ainsi, étant donné un point dont on connaît les coordonnées OSM \((x, y)\) au niveau de zoom \(z\), les coordonnées \((x_t, y_t)\) et le niveau de zoom \(z_t\) de la tuile qui le contient s'obtiennent très facilement au moyen des formules suivantes :

Par exemple, le coin sud-ouest du Learning Center de l'EPFL a les coordonnées (6.56726, 46.51775) dans le système WGS 84. Dans le système de coordonnées OSM, au niveau de zoom 17, cela correspond au point de coordonnées arrondies (17'389'328, 11'867'586). En appliquant les formules ci-dessus, on peut déterminer les coordonnées de la tuile contenant ce point, et on obtient les valeurs (67'927, 46'357). Comme nous le verrons, on peut directement connaître à partir de ces coordonnées l'adresse web (l'URL) de la tuile sur les serveurs du projet OpenStreetMap, qui est simplement :

http://a.tile.openstreetmap.org/17/67927/46357.png

Cette tuile contient bien le coin sud-ouest du Learning Center comme on peut s'en persuader en l'affichant :

La classe Tile du paquetage ch.epfl.isochrone.tiledmap, publique, finale et immuable, représente une tuile de carte. Ses attributs sont les coordonnées de la tuile (le niveau de zoom, la coordonnée x et la coordonnée y) et son image. L'image est représentée par une instance de la classe BufferedImage de la bibliothèque Java, déjà utilisée lors des exercices.

Les tuiles des cartes affichées dans le cadre de ce projet proviennent de différentes sources. Par exemple, celles qui constituent le fond de carte proviennent directement des serveurs du projet OpenStreetMap, tandis que celles qui affichent les isochrones sont dessinées à la volée par le programme, en fonction d'un arbre de trajets les plus rapides.

Afin de tenir compte de ces différents moyens d'obtenir des tuiles, il est intéressant de définir la notion de fournisseur de tuiles (tile provider en anglais), qui est un objet capable de fournir une tuile étant données ses coordonnées. Cette notion est exprimée en Java par l'interface TileProvider.

En plus de fournisseurs de tuiles capables de fournir directement des tuiles, nous en définirons également qui transforment d'autres fournisseurs de tuiles. Nous les appellerons transformateurs (de fournisseurs). Par exemple, un de ces transformateurs stocke en mémoire les tuiles fournies par le fournisseur qu'il transforme afin de pouvoir les fournir plus rapidement à son client à l'avenir, p.ex. en évitant les accès au réseau. Un autre transformateur rend partiellement transparentes les tuiles fournies par le fournisseur qu'il transforme, afin de pouvoir les afficher par dessus d'autres tuiles. Et ainsi de suite.

(Notez au passage que cette organisation des fournisseurs de tuiles et leurs transformateurs est très similaire à celle des images et transformateurs d'images du mini-projet images continues.)

L'interface TileProvider représente un fournisseur de tuile. Un tel fournisseur possède la seule méthode suivante :

• Tile tileAt(int zoom, int x, int y), qui fournit la tuile de coordonnées données.

Cette interface très simple sera implémentée par tous les fournisseurs de tuile ainsi que leurs transformateurs.

La classe OSMTileProvider est un fournisseur de tuiles qui obtient ces dernières depuis un serveur utilisant les conventions de nommage des tuiles du projet OpenStreetMap. Elle est paramétrée par l'adresse de base du serveur.

L'adresse web (l'URL) de l'image d'une tuile est composée de cinq parties qui sont, dans l'ordre :

1. l'adresse de base du serveur,
2. le niveau de zoom de la tuile,
3. la coordonnée x de la tuile,
4. la coordonnée y de la tuile,
5. l'extension .png qui décrit le format de l'image, ici PNG.

Les trois coordonnées sont séparées entre-elles par des barres obliques (/). Par exemple, si l'adresse de base du serveur est http://a.tile.openstreetmap.org/, alors l'URL de l'image PNG de la tuile de coordonnées (67'927, 46'357) au niveau de zoom 17 est :

http://a.tile.openstreetmap.org/17/67927/46357.png

L'adresse de base du serveur à utiliser est le seul paramètre de la classe OSMTileProvider. Pour effectuer vos tests, vous pouvez utiliser l'un des deux serveurs disponibles en accès libre, dont les adresses de base sont :

1. http://a.tile.openstreetmap.org/
2. http://b.tile.openstreetmap.org/

Attention toutefois, ces serveurs ne sont mis à disposition qu'à certaines conditions décrites dans les règles d'utilisation des tuiles d'OpenStreetMap que vous êtes priés de lire avant de continuer.

Une fois que l'adresse de l'image à obtenir est connue, il suffit d'en faire une instance de la classe URL et d'utiliser la méthode statique read de la classe ImageIO pour obtenir l'image sous la forme d'une instance de BufferedImage.

A noter qu'il est possible, et même relativement plausible, qu'une erreur se produise lors de l'obtention de l'image depuis le serveur. Dans ce cas, ce fournisseur doit produire une tuile dont l'image affiche un message d'erreur. Nous mettons à votre disposition une archive Zip contenant une telle tuile, que vous pouvez importer en suivant la même procédure que pour l'importation de fichiers d'horaire. Une fois cela fait, votre répertoire data devrait contenir un nouveau sous-répertoire nommé images dans lequel se trouve une image PNG nommée error-tile.png. Cette image peut être chargée au moyen du code ci-dessous, qui ignore les éventuelles erreurs. Tout comme pour les horaires, étant donné qu'il s'agit d'une ressource fournie avec le programme, ce comportement est raisonnable.

ImageIO.read(getClass().getResource("/images/error-tile.png"));

La classe CachedTileProvider est un transformateur de fournisseur de tuiles qui garde en mémoire un certain nombre de tuiles afin d'accélérer leur obtention.

La première fois qu'une tuile de coordonnées données lui est demandée, il l'obtient du fournisseur qu'il transforme. Toutefois, avant de la retourner, il la stocke également dans une table associative particulière — mise en œuvre par la classe TileCache décrite ci-dessous — afin de pouvoir répondre directement à une requête ultérieure pour la même tuile.

L'utilité de ce transformateur peut être illustrée au moyen de l'extrait de programme suivant :

TileProvider osmTP =
    new OSMTileProvider("http://a.tile.openstreetmap.org/");
Tile t1a = osmTP.tileAt(1, 0, 0);
Tile t2a = osmTP.tileAt(1, 0, 1);
Tile t1b = osmTP.tileAt(1, 0, 0);
Tile t2b = osmTP.tileAt(1, 0, 1);

L'exécution de cet extrait de programme provoquera quatre accès au réseau, puisque chaque appel à la méthode tileAt du fournisseur osmTP implique une requête au serveur pour obtenir la tuile.

Toutefois, en faisant l'hypothèse que les tuiles ne changent pas (ou en tout cas pas assez rapidement pour que ce soit un problème), il est clair que seules deux requêtes suffisent puisque seules deux tuiles différentes sont demandées, celles de coordonnées (0,0) et (0,1) au niveau de zoom 1.

Afin de gagner du temps et de ne pas surcharger le serveur de tuiles, il serait donc préférable de mémoriser les tuiles qu'il fournit et d'utiliser ces tuiles mémorisées pour répondre à des requêtes ultérieures. C'est le but du transformateur CachedTileProvider. On peut l'utiliser pour transformer le fournisseur de tuiles osmTP en lui ajoutant cette possibilité de mémorisation en récrivant l'extrait de programme ci-dessus ainsi :

TileProvider osmTP =
    new OSMTileProvider("http://a.tile.openstreetmap.org/");
TileProvider cTP = new CachedTileProvider(osmTP);
Tile t1a = cTP.tileAt(1, 0, 0);
Tile t2a = cTP.tileAt(1, 0, 1);
Tile t1b = cTP.tileAt(1, 0, 0);
Tile t2b = cTP.tileAt(1, 0, 1);

Etant donné que les requêtes (c-à-d les appels à tileAt) passent désormais par le fournisseur cTP, seules deux requêtes au réseau sont faites.

En effet, lors de la première requête, le fournisseur cTP constate que la tuile de coordonnées (0,0) au niveau de zoom 1 n'a pas encore été demandée, et il la demande donc au fournisseur qu'il transforme, osmTP, ce qui provoque une requête au serveur OpenStreetMap. Toutefois, le transformateur cTP mémorise la tuile obtenue en l'associant aux coordonnées (0,0) au niveau de zoom 1.

La seconde requête, celle qui demande la tuile de coordonnées (0,1), procède de même : cTP constate que c'est la première requête pour cette tuile, la demande à osmTP, qui l'obtient depuis le serveur. Le transformateur cTP la mémorise avant de la retourner.

Lors de la troisième requête, cTP consulte sa table de tuiles mémorisées et constate qu'elle contient déjà la tuile de coordonnées (0,0) au niveau de zoom 1. Dès lors, il retourne simplement cette tuile mémorisée, sans la demander à osmTP. L'accès réseau est ainsi évité ! Il en va de même pour la quatrième requête.

A noter que cette idée de mémoriser les résultats d'une opération coûteuse afin d'améliorer les performances est une technique fondamentale en informatique, appelée cacheing (ou memoization dans certains cas restreints) en anglais.

La classe TileCache représente un « cache » de tuiles, c-à-d une table associative associant des tuiles à leurs coordonnées. A la différence d'une table associative normale, un cache est de taille bornée et oublie certaines associations — généralement les plus anciennes — une fois que sa taille maximale a été atteinte.

Cette classe n'a pas besoin d'offrir la totalité des méthodes d'une table associative, puisque les seules opérations nécessaires ici sont celles permettant d'ajouter une association et d'obtenir une tuile à partir de ses coordonnées :

• void put(int zoom, int x, int y, Tile tile), qui ajoute au cache une association entre les coordonnées et la tuile,
• Tile get(int zoom, int x, int y), qui retourne la tuile associée aux coordonnées données, ou null si celle-ci n'est pas présente dans le cache — soit parce qu'elle n'y a jamais été ajoutée, soit parce qu'elle a été supprimée après que le cache ait atteint sa taille maximale.

Pour mettre en œuvre ce cache, la solution la plus simple consiste à utiliser une sous-classe de la classe LinkedHashMap de la bibliothèque Java. En effet, cette classe offre la méthode redéfinissable removeEldestEntry qui permet de garantir que la table associative ne contient pas plus d'un nombre maximum d'entrées donné. Cette méthode doit retourner vrai si et seulement si la taille maximale a été atteinte, ce qui provoque la suppression des plus anciennes associations.

La définition du champ cache de la classe TileCache peut se faire au moyen d'une sous-classe anonyme de LinkedHashMap, qui redéfinit simplement la méthode removeEldestEntry afin de borner la taille de la table :

private LinkedHashMap<Long, Tile> cache =
    new LinkedHashMap<Long, Tile>() {
        @Override
        protected boolean removeEldestEntry(Map.Entry<Long,Tile> e){
            return size() > MAX_SIZE;
        }
};

où MAX_SIZE est une constante donnant la taille maximale du cache, c-à-d le nombre maximal d'entrées contenues dans la table. Vous pouvez fixer cette valeur à 100 ou en faire un paramètre de la classe TileCache.

A noter que la définition ci-dessus créée une table associative dont les clefs ont le type Long. Or les clefs de cette table doivent être des coordonnées de tuile, à savoir un triplet (zoom, x, y). Il serait bien entendu possible de définir une classe pour représenter ces triplets, mais étant donné que ces trois valeurs ont une taille limitée — zoom est inférieur ou égal à 20, et dès lors x et y sont inférieurs à 2²⁰ — il est possible de les encoder dans un seul entier de type Long, d'une capacité de 64 bits, selon la même technique que celle utilisée pour encoder les trajets dans l'étape 4. C'est ce que nous vous conseillons de faire ici.