Données OpenStreetMap

La totalité des données OSM est constituée de trois types d'éléments :

• les nœuds (nodes), qui représentent des points à la surface de la Terre,
• les « voies » (ways), qui représentent des séquences ordonnées de nœuds,
• les relations (relations), qui représentent des séquences ordonnées de nœuds, de chemins ou d'autres relations.

Les nœuds sont généralement utilisés pour représenter des objets dont la dimension physique n'est pas importante, comme les arbres, les fontaines, les feux de signalisation, etc. Ils servent de plus d'éléments de base pour les voies, utilisées elles pour représenter soit des données « unidimensionnelles » comme les routes ou les frontières, soit des données bidimensionnelles simples, comme certains bâtiments. Finalement, les relations sont utilisées pour représenter des groupes d'autres éléments liés entre eux, comme l'ensemble des routes formant un itinéraire cyclable ou une ligne de bus.

Chaque élément est identifié par son identité (identity), un entier positif. Il ne peut exister qu'un seul élément d'un type donné ayant une identité donnée, mais il peut très bien exister deux éléments de types différents, p. ex. un nœud et une voie, ayant la même identité.

Les trois types d'éléments ont un petit nombre d'attributs fondamentaux qui leur sont associés et qui sont obligatoires. Par exemple, un nœud possède une position à la surface de la Terre, donnée par sa longitude et sa latitude, une voie possède un ensemble de nœuds, etc. En plus de ce petit nombre d'attributs fondamentaux, il est possible d'attacher à n'importe quel élément OSM un nombre quelconque d'attributs additionnels, qui sont des paires clef/valeur textuelles. La clef et la valeur de chaque paire sont séparées par le signe « égal » (=). Par exemple, l'attribut dont la clef est surface et la valeur asphalt s'écrit surface=asphalt.

Il n'y a aucune restriction quant aux clefs et aux valeurs qu'il est autorisé d'attacher à un élément OSM. Au cours du temps, des conventions sont toutefois adoptées par consensus et ce sont ces conventions qui sont utilisées pour dessiner les cartes présentées plus haut, et que nous utiliserons dans JaVelo.

Par exemple, une convention utilisée depuis le début du projet est que l'attribut dont la clef est highway est attaché aux voies qui représentent des routes. La valeur de cet attribut décrit le type de route dont il s'agit. Ainsi, la valeur motorway est utilisée pour les autoroutes, dessinées en rouge sur la carte OSM standard. Les attributs les plus fréquemment utilisés sont répertoriés sur la page Éléments cartographiques du Wiki OSM, auquel les personnes intéressées peuvent jeter un bref coup d'œil si elles le désirent.

Les sections suivantes décrivent plus en détail les trois types d'éléments OSM, et donnent un exemple de chacun d'entre eux.

Un nœud (node) est un point dont la position à la surface de la Terre est donnée par sa longitude et sa latitude, exprimées dans le système WGS84.

Par exemple, le nœud dont l'identité est 5981854153 représente le « Chêne de Napoléon », un arbre célèbre qui se trouve sur le campus de l'UNIL. Un certain nombre d'attributs sont attachés à ce nœud, p. ex. natural=tree qui l'identifie comme étant un arbre, ou name=Chêne de Napoléon qui donne son nom.

Il est possible de connaître la totalité des attributs d'un nœud OSM dont on connaît l'identité en suivant un lien ayant la forme suivante :

https://www.openstreetmap.org/node/<id>

où <id> est l'identité du nœud. Par exemple, pour connaître la totalité des attributs du nœud mentionné ci-dessus, il suffit de suivre le lien https://www.openstreetmap.org/node/5981854153

Une « voie » (way) est une séquence ordonnée de nœuds OSM.

Par exemple, la voie dont l'identité est 88954910 représente un bout de l'avenue Auguste-Piccard sur le campus de l'EPFL. Elle est composée de 7 nœuds et dotée d'un certain nombre d'attributs. Parmi ceux-ci, on trouve maxspeed=30, qui donne la vitesse maximale à laquelle il est autorisé de rouler sur cette route, et oneway=yes, qui signifie qu'il s'agit d'une route à sens unique.

Comme cet exemple l'illustre, il peut être nécessaire de tenir compte de l'ordre des nœuds d'une voie pour interpréter correctement certains attributs. Ainsi lorsque l'attribut oneway=yes est attaché à une voie, cela signifie qu'elle représente une route à sens unique et que le sens de circulation est identique à l'ordre des nœuds de la voie. Ce même attribut peut avoir la valeur -1 (oneway=-1), qui signifie que le sens de circulation est l'inverse de l'ordre des nœuds.

Comme pour les nœuds, il est possible de connaître la totalité des attributs d'une voie OSM en suivant un lien ayant la forme suivante :

https://www.openstreetmap.org/way/<id>

où <id> est l'identité de la voie.

Une relation (relation) est une séquence d'autres éléments OSM : nœuds, voies ou relations.

Par exemple, la relation dont l'identité est 28063 représente l'étape 6 de la route numéro 1 de « La Suisse à vélo », qui relie Montreux à Morges en passant devant l'EPFL. Parmi les attributs qui lui sont attachés, on trouve route=bicycle, qui déclare que la relation représente un itinéraire cyclable, ou encore network=ncn, qui nous apprend qu'il s'agit d'une route nationale, NCN signifiant national cycling network.

Sans surprise, il est possible de connaître la totalité des attributs de cette relation en suivant le lien https://www.openstreetmap.org/relation/28063, qui a une forme similaire à ceux présentés plus haut.

Pour JaVelo, les relations sont importantes car, comme l'exemple ci-dessus l'illustre, elles permettent d'identifier les itinéraires cyclables officiels. Par définition, ces itinéraires devraient être bien adaptés aux cyclistes, et donc favorisés par JaVelo.

Même s'il serait techniquement possible d'écrire un projet comme JaVelo en utilisant directement les données brutes d'OpenStreetMap, cela ne serait pas très efficace, pour deux raisons.

Premièrement, une grande partie des données OSM — p. ex. les contours des bâtiments — n'est d'aucune utilité pour choisir une route agréable à parcourir à vélo.

Deuxièmement, les données OSM ne sont pas organisées de manière à faciliter la recherche d'un itinéraire. Par exemple, étant donné un nœud OpenStreetMap, le seul moyen de déterminer toutes les voies dont ce nœud fait partie est de parcourir la totalité des voies, ce qui est bien entendu très inefficace.

Pour cette raison, les données OSM sont pré-traitées avant d'être utilisées dans JaVelo. Le but de ce pré-traitement est d'une part de ne garder que les données utiles au projet, et d'autre part de les organiser de manière à ce que la recherche d'un itinéraire puisse se faire aussi rapidement que possible. Ce pré-traitement est fait par un programme que vous n'aurez pas à écrire vous même, et seules les données pré-traitées vous seront fournies. Leur format sera décrit à l'étape suivante.

Comme son nom l'indique, le système Web Mercator a été développé à l'origine pour présenter des cartes sur le Web. Ces cartes peuvent être visualisées à différents niveaux de zoom (zoom levels), allant généralement de 0 à 19, voire 20.

Au niveau de zoom 0, la carte de la Terre entière est une image carrée de 256 pixels de côté, qui est celle visible dans les figures 1 et 2. A chaque passage d'un niveau de zoom au suivant, la largeur et la hauteur de cette image doublent. Ainsi, au niveau de zoom 1, la carte fait 512 pixels de côté ; au niveau de zoom 2, elle fait 1024 pixels de côté ; et ainsi de suite. De manière générale, au niveau de zoom \(z\), la carte de la Terre entière est une image de

\[ 256\cdot 2^z = 2^8\cdot 2^z = 2^{8 + z}\]

pixels de côté.

Sachant cela, il est très facile de connaître la position d'un point dont on connaît les coordonnées Web Mercator dans l'image de la carte à un niveau de zoom donné, puisqu'il suffit de multiplier ses coordonnées par la taille de l'image à ce niveau de zoom.

Par exemple, le Chêne de Napoléon a les coordonnées WGS 84 :

\[\lambda=6.5790772, \phi=46.5218976\]

et donc, d'après les formules plus haut, les coordonnées Web Mercator :

\[x=0.518275214444, y=0.353664894749\]

Au niveau de zoom 19, le Chêne de Napoléon se trouve donc à la position (arrondie) :

\[x_{19} = 69 561 722, y_{19} = 47 468 099 \]

dans l'image de 2²⁷ = 134 217 728 pixels de côté qui constitue la carte de la Terre entière à ce niveau de zoom.

Une première manière de représenter une différence d'altitude entre deux points serait d'utiliser un entier Java de type byte, et de l'interpréter comme d'habitude en complément à deux.

Pour mémoire, avec cette interprétation, une valeur de type byte peut représenter n'importe quel entier compris entre -128 et +127. En supposant que les différences d'altitudes soient exprimées en mètres, nous aurions ainsi la possibilité de représenter des différences d'altitudes entières comprises entre -128 m et +127 m.

Ce choix ne semble pas vraiment optimal, pour deux raisons : d'une part, seules les différences entières sont représentables, et d'autre part la plage couverte est bien trop importante. En effet, si la différence d'altitude entre deux points d'une route situés à 2 mètres l'un de l'autre est de -128 mètres, cela signifie que la pente de la route est de 6400% à cet endroit, or les pentes supérieures à 20% sont rares en pratique.

Pour résoudre ces problèmes, une solution simple est de changer d'unité. On peut ainsi décider de représenter la différence d'altitude en seizièmes de mètres plutôt qu'en mètres. Cela augmente la précision, qui passe à 6.25 cm (1/16 m), tout en permettant encore de représenter des pentes allant jusqu'à 400%, ce qui reste largement suffisant.

Plutôt que de changer d'unité, il est aussi possible de changer la manière dont la valeur de type byte est interprétée. Pour mémoire, nous avons vu au cours que l'interprétation en complément à deux d'une valeur de type byte (8 bits) consiste à associer à chacun des bits un poids dépendant de sa position, poids qui est positif pour tous les bits sauf celui de poids le plus fort, comme illustré ci-dessous :

Par exemple, avec cette interprétation, les 8 bits 10011100 représentent l'entier \(-100\) (car \(-128 + 16 + 8 + 4 = -100\)).

Dans l'interprétation en complément à deux, le poids du bit \(p\) vaut \(±2^{p}\), et le bit 0 a donc un poids de 1. En conséquence, cette interprétation ne permet pas de représenter des valeurs non entières. Pour permettre la représentation de valeurs non entières avec une précision de 1/16, il suffit de décider que le bit 0 a un poids de 1/16 et d'ajuster les autres poids en conséquence :

Avec cette nouvelle interprétation, le poids du bit \(p\) vaut \(±2^{p - 4}\). Ainsi, les mêmes 8 bits que ci-dessus (10011100) représentent désormais la valeur \(-6.25\) (car \(-8 + 1 + \tfrac{1}{2} + \tfrac{1}{4} = -6.25\)).

Cette manière d'interpréter les bits est tout à fait équivalente à la manière d'interpréter les chiffres d'un nombre écrit dans la notation décimale positionnelle à laquelle nous sommes habitués. La seule différence est que les ordinateurs travaillent en base 2, alors que nous travaillons en base 10. Par exemple, le nombre noté \(3.14\) vaut \(3\cdot 10^0 + 1\cdot 10^{-1} + 4\cdot 10^{-2}\).

Dans la notation décimale usuelle, on utilise le point décimal (ou la virgule décimale) pour séparer les chiffres dont le poids correspond à une puissance de dix positive ou nulle de ceux dont le poids correspond à une puissance de dix négative. Dans l'interprétation des valeurs de type byte présentée ci-dessus, on peut donc imaginer qu'un « point binaire » est placé après le bit 4. En d'autres termes, on pourrait noter la valeur \(-6.25\) comme 1001.1100.

Étant donné que le « point binaire » se trouve toujours à la même position dans une telle interprétation, on dit que les nombres que l'on interprète de la sorte sont à virgule fixe. Pour connaître le nombre de bits utilisés à gauche et à droite du point, on utilise souvent la « notation Q ». Par exemple, l'interprétation ci-dessus serait notée Q4.4, ce qui signifie qu'elle comporte 4 bits à gauche du point, et 4 à droite. Dans cette notation, la lettre Q peut être précédée d'un U si les nombres sont interprétés de manière non signée plutôt qu'en complément à deux.

Dans JaVelo, nous utiliserons des nombres à virgule fixe pour représenter les données suivantes :

• les altitudes, représentées en mètres au format UQ12.4, qui couvre une plage allant de 0 à 4095.9375 m (inclus)¹,
• les différences d'altitudes entre deux points successifs d'une route, représentées en mètres, au format Q0.4 (de -0.5 m à +0.4375 m), ou au format Q4.4 (de -8 m à +7.9375 m),
• les longueurs des segments de routes, représentées en mètres au format UQ12.4 (de 0 à 4095.9375 m),
• les coordonnées suisses (est/nord) des points, représentées en mètres au format Q28.4, qui permet de couvrir (largement) la totalité du territoire suisse.

Sachant que toutes ces données sont en mètres et que nous utilisons systématiquement 4 bits après la virgule, la précision est de 6.25 cm dans tous les cas.

Notez que, comme l'exemple plus haut l'a illustré, notre utilisation des nombres à virgule fixe est totalement équivalente à un changement d'unité. Il est donc tout à fait correct de considérer que les données mentionnées ci-dessus sont toutes exprimées sous forme entière mais en seizième de mètres. N'hésitez pas à adopter ce point de vue s'il vous paraît plus simple à comprendre.

Les méthodes xAtZoomLevel et yAtZoomLevel doivent transformer les coordonnées « normales » du point, comprises entre 0 et 1, en coordonnées de l'image de la carte au niveau de zoom donné. Comme nous l'avons vu à la §2.3.1, cela peut se faire au moyen d'une simple multiplication par une puissance de deux entière, qui dépend du niveau de zoom.

Une telle multiplication pourrait théoriquement se faire en combinant l'opérateur de multiplication (*) avec la méthode pow de Math, qui permet d'élever une valeur à une certaine puissance. Il est toutefois possible de faire mieux ici, grâce à la méthode scalb(x,y) de Math, qui calcule \(x\cdot2^y\) de manière très efficace².

La méthode scalb accepte également des valeurs négatives en second argument, ce qui permet de diviser très efficacement une valeur par une puissance de deux entière. Cela est très utile pour écrire la méthode of.

Une manière simple et efficace d'extraire une séquence de bits consiste à effectuer deux décalages successifs :

1. un premier décalage à gauche afin d'éjecter tous les bits de poids supérieur à ceux qu'on désire extraire,
2. un second décalage à droite afin d'éjecter tous les bits de poids inférieur à ceux qu'on désire extraire et, dans le même temps, de placer les bits à extraire à la bonne position.

Par exemple, imaginons que l'on désire extraire des 32 bits ci-dessous, stockés dans un entier de type int, les 4 bits mis en évidence, à savoir ceux d'index 8 à 11 :

11001010111111101011101010111110

On commence par effectuer un décalage à gauche pour éjecter tous les bits se trouvant à gauche du premier que l'on désire conserver. Il y en a 20, et après avoir décalé la valeur ci-dessous de 20 bits à gauche, on obtient :

10101011111000000000000000000000

les bits soulignés étant ceux insérés par le décalage. Cette valeur peut maintenant être décalée à droite afin de simultanément éjecter les bits se trouvant à droite du dernier que l'on désire extraire et de ramener ceux-ci à la bonne position. Il y a 28 de ces bits, et après avoir décalé la valeur ci-dessus de 28 bits à droite, on obtient :

00000000000000000000000000001010

Une fois encore, les bits soulignés sont ceux insérés par le décalage.

Grâce à cette séquence de deux décalages, on a effectivement réussi à extraire les 4 bits désirés. Il faut noter que le décalage à droite utilisé ci-dessus était un décalage logique. Si on avait utilisé un décalage arithmétique, alors les bits insérés auraient été des copies du bit de poids fort de la valeur avant décalage, 1 ci-dessus. On aurait alors obtenu le résultat suivant :

11111111111111111111111111111010

qui correspond à une extraction de bits signée.

En d'autres termes, les méthodes extractSigned et extractUnsigned consistent toutes deux en un décalage à gauche suivi d'un décalage à droite. La seule différence est que dans le premier cas le décalage à droite est arithmétique, alors que dans le second il est logique.

Afin d'illustrer comment un objet de type DoubleUnaryOperator peut représenter une fonction mathématique des réels vers les réels, considérons la classe F ci-dessous qui implémente cette interface et fournit une définition pour sa seule méthode abstraite, applyAsDouble :

public final class F implements DoubleUnaryOperator {
  @Override
  public double applyAsDouble(double x) {
    return x * x;
  }
}

Une instance de cette classe se comporte de manière très similaire à la fonction mathématique d'élévation du carré définie ainsi :

\[ f(x) = x^2 \]

En effet, en appelant la méthode applyAsDouble d'une instance de F en lui passant un nombre quelconque, on obtient ce nombre au carré, exactement comme si on appelait la fonction (mathématique) \(f\) ci-dessus. Ainsi, l'extrait de code ci-dessous affiche 1.44 :

DoubleUnaryOperator f = new F();
System.out.println(f.applyAsDouble(1.2));

Comme cet exemple le suggère, les méthodes constant et sampled retournent simplement une instance d'une classe représentant un type de fonction particulier.

Ainsi, constant retourne une nouvelle instance d'une classe nommée Constant, privée et imbriquée statiquement dans Functions. Cette classe implémente bien entendu l'interface DoubleUnaryOperator et sa redéfinition de la méthode applyAsDouble retourne toujours la même valeur, passée au constructeur de Constant. En d'autres termes, la méthode constant et la classe Constant peuvent se définir ainsi :

public final class Functions {
  public static DoubleUnaryOperator constant(double y) {
    return new Constant(y);
  }

  private static final class Constant
      implements DoubleUnaryOperator {
    // … attribut(s) et constructeur
    // … méthode applyAsDouble
  }
}

Notez que la classe Constant pourrait même être un enregistrement, ce qui la rendrait encore plus concise.

La méthode sampled peut s'écrire de manière similaire, et simplement retourner une nouvelle instance d'une classe nommée Sampled, également privée et imbriquée statiquement dans Functions.

Nous verrons plus tard dans le cours le concept de lambda, qui permet d'écrire les méthodes constant et sampled de manière beaucoup plus concise. Les personnes qui connaîtraient déjà ce concept peuvent bien entendu l'utiliser si elles le désirent.