Graphe, profils et itinéraires

Une personne utilisant JaVelo a pour but de se déplacer à vélo entre un point de départ et un point d'arrivée, en passant éventuellement par un ou plusieurs points intermédiaires. En fonction de ces points, que nous nommerons points de passage (waypoints), JaVelo détermine l'itinéraire idéal, d'après ses critères.

Étant donné que JaVelo représente le réseau routier par un graphe, un itinéraire n'est rien d'autre qu'une succession d'arêtes permettant de se rendre du nœud le plus proche du point de départ au nœud le plus proche du point d'arrivée, en passant par des nœuds aussi proches que possible des points intermédiaires. La première arête d'un itinéraire part donc du nœud de départ, tandis que sa dernière arête se termine au nœud d'arrivée.

La figure ci-dessous montre un exemple d'itinéraire. Le point de départ y est représenté par l'épingle verte, celui d'arrivée par l'épingle rouge, et l'unique point intermédiaire par l'épingle bleue. L'itinéraire est composé d'un total de sept arêtes, reliant huit nœuds et annotées avec leur longueur en kilomètres. La longueur totale de l'itinéraire est de 16.5 km.

L'itinéraire ci-dessus est ce que nous nommerons un itinéraire multiple, composé de deux itinéraires simples ou segments. Le premier segment, de 7 km, va du nœud de départ au nœud intermédiaire ; le second, de 9.5 km, du nœud intermédiaire au nœud final.

En plus de l'itinéraire lui-même, la figure 1 montre un point P situé dans son voisinage. Le point de l'itinéraire le plus proche de P se trouve au milieu de l'avant-dernière arête et est indiqué en rouge. Ce point rouge se trouve donc à une position de 1.5 km sur l'avant-dernière arête, à une position de 6.5 km sur le second segment, et à une position de 13.5 km sur l'itinéraire complet. La distance entre le point P et l'itinéraire — et donc le point rouge — est notée d.

Nous verrons dans une étape ultérieure qu'il est utile de pouvoir déterminer le point d'un itinéraire le plus proche d'un point donné, comme dans la figure 1. Cela permet de mettre en évidence le point de l'itinéraire le plus proche du pointeur de la souris lorsque l'utilisateur l'approche de l'itinéraire.

Lors de l'étape précédente, vous avez écrit des classes donnant accès aux différents éléments du graphe JaVelo — nœuds, arêtes, etc. Ces classes reçoivent une ou plusieurs mémoires tampons (buffers) contenant les attributs de ces éléments les uns à la suite des autres. Il reste donc à savoir comment obtenir ces mémoires tampons.

Comme vous le verrez ci-dessous, nous mettons à votre disposition un certain nombre de fichiers dont le contenu correspond exactement à celui des mémoires tampons. Par exemple, un des fichiers que nous vous fournissons, nommé nodes.bin, contient les attributs de tous les nœuds du graphe JaVelo, dans le même format que celui décrit à la §3.2 de l'étape 3.

Il serait donc techniquement possible de charger le contenu de ce fichier et de le placer dans une mémoire tampon, qui serait ensuite passée à la classe GraphNode. Cette solution aurait toutefois l'inconvénient d'être relativement lente, la quantité de données à charger étant assez importante.

Heureusement, une solution plus efficace existe, le « mappage » de fichier en mémoire (memory mapping). Cet anglicisme désigne la possibilité de faire apparaître le contenu d'un fichier en mémoire, comme s'il avait effectivement été chargé, mais sans qu'il ne le soit réellement. Au lieu de cela, le contenu du fichier est chargé lorsqu'on accède aux données, et seules les parties effectivement nécessaires de ce contenu sont chargées.

Cette possibilité est très intéressante pour JaVelo, car elle nous permet d'écrire le programme comme si la totalité des données du graphe avait été chargée en mémoire, alors qu'en réalité seules les parties effectivement utilisées le sont, au moment de leur première utilisation.

Le « mappage » de fichiers en Java se fait au moyen de classes du paquetage java.nio qui n'ont pas été présentées au cours. Leur utilisation est néanmoins extrêmement simple, puisqu'on peut « mapper » un fichier en :

• ouvrant un canal de communication avec ce fichier au moyen de la méthode open de FileChannel, opération très similaire à la création d'un flot d'entrée au moyen d'une instance de FileInputStream,
• appelant la méthode map sur ce canal afin de « mapper » le contenu du fichier en mémoire — en lecture seule (read only) — et d'obtenir une mémoire tampon de type ByteBuffer dont le contenu est celui du fichier,
• appelant au besoin une méthode as…, comme asLongBuffer, afin d'obtenir une mémoire tampon d'un autre type.

L'extrait de programme ci-dessous illustre cette procédure en « mappant » le contenu du fichier nodes_osmid.bin en mémoire puis en en extrayant l'identité OSM du nœud JaVelo d'index 2022 :

Path filePath = Path.of("lausanne/nodes_osmid.bin");
LongBuffer osmIdBuffer;
try (FileChannel channel = FileChannel.open(filePath)) {
  osmIdBuffer = channel
    .map(FileChannel.MapMode.READ_ONLY, 0, channel.size())
    .asLongBuffer();
}
System.out.println(osmIdBuffer.get(2022));

Notez bien que la mémoire tampon contenant le contenu du fichier reste utilisable même après que le canal ait été fermé via un appel à sa méthode close. Dans l'extrait de programme ci-dessus, cet appel est fait implicitement à la sortie du bloc try-with-resource, à l'avant-dernière ligne.

L'extrait de programme ci-dessus affiche 310876657, ce qui vous permet de savoir que, dans les données de la région lausannoise, le nœud JaVelo d'identité 2022 correspond au nœud OSM d'identité 310876657. Pour tout savoir à son sujet, il vous suffit de suivre le lien :

https://www.openstreetmap.org/node/310876657

ce qui peut se révéler utile lors du débogage.

La classe Graph du paquetage ch.epfl.javelo.data, publique et immuable, représente le graphe JaVelo.

Elle offre une méthode statique permettant de charger le graphe depuis un répertoire :

• Graph loadFrom(Path basePath) throws IOException, qui retourne le graphe JaVelo obtenu à partir des fichiers se trouvant dans le répertoire dont le chemin d'accès est basePath, ou lève IOException en cas d'erreur d'entrée/sortie, p. ex. si l'un des fichiers attendu n'existe pas.

Les fichiers utilisés par loadFrom portent le même nom que ceux que nous vous fournissons, p. ex. nodes.bin contient les nœuds, edges.bin les arêtes, etc. Le chemin d'accès passé à loadFrom est celui du répertoire contenant ces fichiers, qui pourrait être lausanne pour charger les données fournies à cette étape. Consultez les conseils de programmation plus bas pour voir comment obtenir le chemin d'accès à passer à la méthode open à partir du chemin d'accès au répertoire et d'un nom de fichier.

La classe Graph possède un constructeur public, utilisé par la méthode loadFrom :

• Graph(GraphNodes nodes, GraphSectors sectors, GraphEdges edges, List<AttributeSet> attributeSets), qui retourne le graphe avec les nœuds, secteurs, arêtes et ensembles d'attributs donnés.

Graph offre les méthodes publiques suivantes qui, pour la plupart, ne font rien d'autre qu'appeler des méthodes des classes écrites à l'étape précédente :

• int nodeCount(), qui retourne le nombre total de nœuds dans le graphe,
• PointCh nodePoint(int nodeId), qui retourne la position du nœud d'identité donnée,
• int nodeOutDegree(int nodeId), qui retourne le nombre d'arêtes sortant du nœud d'identité donnée,
• int nodeOutEdgeId(int nodeId, int edgeIndex), qui retourne l'identité de la edgeIndex-ième arête sortant du nœud d'identité nodeId,
• int nodeClosestTo(PointCh point, double searchDistance), qui retourne l'identité du nœud se trouvant le plus proche du point donné, à la distance maximale donnée (en mètres), ou -1 si aucun nœud ne correspond à ces critères,
• int edgeTargetNodeId(int edgeId), qui retourne l'identité du nœud destination de l'arête d'identité donnée,
• boolean edgeIsInverted(int edgeId), qui retourne vrai ssi l'arête d'identité donnée va dans le sens contraire de la voie OSM dont elle provient,
• AttributeSet edgeAttributes(int edgeId), qui retourne l'ensemble des attributs OSM attachés à l'arête d'identité donnée,
• double edgeLength(int edgeId), qui retourne la longueur, en mètres, de l'arête d'identité donnée,
• double edgeElevationGain(int edgeId), qui retourne le dénivelé positif total de l'arête d'identité donnée,
• DoubleUnaryOperator edgeProfile(int edgeId), qui retourne le profil en long de l'arête d'identité donnée, sous la forme d'une fonction ; si l'arête ne possède pas de profil, alors cette fonction doit retourner Double.NaN pour n'importe quel argument.

La valeur Double.NaN (pour not a number) est une valeur spéciale retournée par les opérations sur les nombres à virgule flottante qui ne sont pas définies mathématiquement, comme 0/0. Nous l'utilisons ici pour représenter des données manquantes, ce qui est un peu discutable mais assez courant.

La classe ElevationProfile du paquetage ch.epfl.javelo.routing, publique et immuable, représente le profil en long d'un itinéraire simple ou multiple.

Cette classe offre un unique constructeur public :

• ElevationProfile(double length, float[] elevationSamples), qui construit le profil en long d'un itinéraire de longueur length (en mètres) et dont les échantillons d'altitude, répartis uniformément le long de l'itinéraire, sont contenus dans elevationSamples ; lève IllegalArgumentException si la longueur est négative ou nulle, ou si le tableau d'échantillons contient moins de 2 éléments.

En plus de ce constructeur, ElevationProfile possède les méthodes publiques suivantes :

• double length(), qui retourne la longueur du profil, en mètres,
• double minElevation(), qui retourne l'altitude minimum du profil, en mètres,
• double maxElevation(), qui retourne l'altitude maximum du profil, en mètres,
• double totalAscent(), qui retourne le dénivelé positif total du profil, en mètres,
• double totalDescent(), qui retourne le dénivelé négatif total du profil, en mètres,
• double elevationAt(double position), qui retourne l'altitude du profil à la position donnée, qui n'est pas forcément comprise entre 0 et la longueur du profil ; le premier échantillon est retourné lorsque la position est négative, le dernier lorsqu'elle est supérieure à la longueur.

La raison pour laquelle elevationAt accepte également des positions qui ne sont pas comprises entre 0 et la longueur du profil est que cela la rend tolérante aux imprécisions résultant des arrondis.

Le dénivelé positif total est égal à la somme de toutes les différences positives entre un échantillon et son prédécesseur. Le dénivelé négatif total est défini de manière similaire, et est également positif ou nul.

L'enregistrement Edge du paquetage ch.epfl.javelo.routing, public, représente une arête d'un itinéraire.

Notez bien que cet enregistrement est uniquement destiné à être utilisé pour représenter les arêtes appartenant à un itinéraire, et non la totalité des arêtes du graphe. Son but est de collecter toutes les informations relatives à une arête d'itinéraire, qui pourraient être obtenues par des appels aux méthodes de Graph mais qu'il est plus commode d'avoir à disposition directement dans un objet.

L'enregistrement Edge possède les attributs suivants :

• int fromNodeId, l'identité du nœud de départ de l'arête,
• int toNodeId, l'identité du nœud d'arrivée de l'arête,
• PointCh fromPoint, le point de départ de l'arête,
• PointCh toPoint, le point d'arrivée de l'arête,
• double length, la longueur de l'arête, en mètres,
• DoubleUnaryOperator profile, le profil en long de l'arête.

et offre une méthode statique facilitant la construction d'une instance :

• Edge of(Graph graph, int edgeId, int fromNodeId, int toNodeId), qui retourne une instance de Edge dont les attributs fromNodeId et toNodeId sont ceux donnés, les autres étant ceux de l'arête d'identité edgeId dans le graphe Graph.

De plus, Edge offre les méthodes publiques suivantes :

• double positionClosestTo(PointCh point), qui retourne la position le long de l'arête, en mètres, qui se trouve la plus proche du point donné,
• PointCh pointAt(double position), qui retourne le point se trouvant à la position donnée sur l'arête, exprimée en mètres,
• double elevationAt(double position), qui retourne l'altitude, en mètres, à la position donnée sur l'arête.

Dans la figure 1, la méthode positionClosestTo appliquée à l'objet représentant l'avant-dernière arête, avec le point P en argument, retournerait 1500 (mètres), car le point le plus proche de P le long de cette arête — le point rouge — se trouve à une position de 1.5 km.

Appliquée à ce même objet, la méthode pointAt retournerait le point rouge si on lui passait 1500 en argument.

L'enregistrement RoutePoint du paquetage ch.epfl.javelo.routing, public, représente le point d'un itinéraire le plus proche d'un point de référence donné, qui se trouve dans le voisinage de l'itinéraire. Le point rouge de la figure 1 est un tel point, car il est le point de l'itinéraire le plus proche de P, la référence dans ce cas.

RoutePoint possède les attributs suivants :

• PointCh point, le point sur l'itinéraire,
• double position, la position du point le long de l'itinéraire, en mètres,
• double distanceToReference, la distance, en mètres, entre le point et la référence.

Dans l'exemple de la figure 1, le point de référence est P et l'attribut point correspond donc au point rouge, position vaut 13500, et distanceToReference est égal à d.

RoutePoint offre une constante — un attribut public, statique et final — représentant un point inexistant :

• NONE, qui représente un point inexistant (point est nul, position vaut NaN et distanceToReference vaut POSITIVE_INFINITY).

RoutePoint offre les méthodes suivantes :

• RoutePoint withPositionShiftedBy(double positionDifference), qui retourne un point identique au récepteur (this) mais dont la position est décalée de la différence donnée, qui peut être positive ou négative,
• RoutePoint min(RoutePoint that), qui retourne this si sa distance à la référence est inférieure ou égale à celle de that, et that sinon,
• RoutePoint min(PointCh thatPoint, double thatPosition, double thatDistanceToReference), qui retourne this si sa distance à la référence est inférieure ou égale à thatDistanceToReference, et une nouvelle instance de RoutePoint dont les attributs sont les arguments passés à min sinon.

Notez que le but de la seconde variante de la méthode min est d'éviter la création d'une instance de RoutePoint lorsque cela n'est pas nécessaire. Assurez-vous donc que votre méthode ne crée une telle instance que dans le cas où cela est indispensable.

La méthode withPositionShiftedBy est quant à elle destinée à être utilisée pour transformer un point dont la position est exprimée par rapport au segment qui le contient en un point équivalent mais dont la position est exprimée par rapport à l'itinéraire complet.

L'interface Route du paquetage ch.epfl.javelo.routing, publique, représente un itinéraire. Elle sera implémentée par deux classes que vous écrirez ultérieurement, l'une représentant un itinéraire simple entre deux points de passage, et l'autre représentant un itinéraire multiple passant par au moins un point de passage intermédiaire.

L'interface Route offre les méthodes abstraites suivantes :

• int indexOfSegmentAt(double position), qui retourne l'index du segment à la position donnée (en mètres),
• double length(), qui retourne la longueur de l'itinéraire, en mètres,
• List<Edge> edges(), qui retourne la totalité des arêtes de l'itinéraire,
• List<PointCh> points(), qui retourne la totalité des points situés aux extrémités des arêtes de l'itinéraire,
• PointCh pointAt(double position), qui retourne le point se trouvant à la position donnée le long de l'itinéraire,
• double elevationAt(double position), qui retourne l'altitude à la position donnée le long de l'itinéraire,
• int nodeClosestTo(double position), qui retourne l'identité du nœud appartenant à l'itinéraire et se trouvant le plus proche de la position donnée,
• RoutePoint pointClosestTo(PointCh point), qui retourne le point de l'itinéraire se trouvant le plus proche du point de référence donné.

Notez que comme toutes ces méthodes sont abstraites, vous n'avez rien d'autre à écrire dans l'interface Route que leurs déclarations — aucun code n'est requis.

Comme pour l'étape précédente, nous ne vous fournissons plus de tests mais un fichier de vérification de signatures contenu dans une archive Zip à importer dans votre projet.