Graphe, profils et itinéraires
JaVelo – étape 4
1. Introduction
Le but principal de cette étape est de réaliser les classes représentant le graphe JaVelo et les profils en long, ainsi que des classes et interfaces utiles à la représentation des itinéraires.
2. Concepts
Deux des concepts importants à cette étape, le graphe JaVelo et les profils en long, ont déjà été décrits précédemment. Il reste donc à décrire la notion d'itinéraire, sujet de la section suivante, ainsi que celle de « mappage » de fichier en mémoire, qui nous permettra d'accéder efficacement aux données du graphe.
2.1. Itinéraire
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.
![route;64.png](i/route;64.png)
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.
2.2. « Mappage » de fichiers
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.
3. Mise en œuvre Java
Avant de commencer la mise en œuvre de cette étape, il vous faut télécharger une archive Zip contenant les données JaVelo pour la région lausannoise. Ces données couvrent le rectangle allant de E=2520000 N=1145000 à E=2550000 N=1165000, qui apparaît en bleu sur la carte ci-dessous.
Cette archive Zip contient un répertoire nommé lausanne
dans lequel se trouvent les fichiers suivants :
nodes.bin
, qui contient les nœuds du graphe JaVelo,edges.bin
, qui contient les arêtes du graphe JaVelo (premier ensemble d'attributs),profile_ids.bin
, qui contient les types et index de premier échantillon des profils des arêtes,elevations.bin
, qui contient les échantillons des profils,attributes.bin
, qui contient les ensembles d'attributs OSM des arêtes,sectors.bin
, qui contient les secteurs,nodes_osmid.bin
, qui contient les identités OSM des nœuds.
Vous devez extraire le contenu de cette archive dans le répertoire contenant votre projet, de manière à ce que le répertoire lausanne
se trouve au même niveau que le répertoire src
contenant votre code Java.
Tous les fichiers fournis sont destinés à être « mappés » en mémoire, en utilisant la technique expliquée à la section suivante, puis passés aux classes écrites à l'étape précédente et à cette étape — le premier à GraphNodes
, les trois suivants à GraphEdges
, et ainsi de suite.
Le dernier fichier (nodes_osmid.bin
) fait exception à cette règle puisqu'il contient des données qui ne sont pas nécessaires au bon fonctionnement du programme, mais qui peuvent faciliter son débogage. Ce fichier contient un tableau de valeurs de type long
, qui donnent l'identité OSM des nœuds JaVelo. Par exemple, à l'index 0 de ce tableau se trouve l'identité OSM du nœud JaVelo d'identité (et donc d'index) 0, et ainsi de suite.
3.1. « Mappage » de fichiers en Java
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
deFileChannel
, opération très similaire à la création d'un flot d'entrée au moyen d'une instance deFileInputStream
, - 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 typeByteBuffer
dont le contenu est celui du fichier, - appelant au besoin une méthode
as…
, commeasLongBuffer
, 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 :
ce qui peut se révéler utile lors du débogage.
3.2. Classe Graph
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 estbasePath
, ou lèveIOException
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 laedgeIndex
-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 retournerDouble.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.
3.2.1. Conseils de programmation
- Méthode
loadFrom
La méthode
loadFrom
reçoit en argument le chemin d'accès au répertoire contenant les différents fichiers du graphe JaVelo, sous la forme d'une valeur de typePath
. Pour charger les données de la région lausannoise fournies, le chemin à utiliser est celui du répertoire nommélausanne
, qui s'obtient ainsi :Path basePath = Path.of("lausanne");
À partir de ce chemin de base, la méthode
loadFrom
doit déterminer les chemins des différents fichiers à charger, afin de les passer à la méthodeopen
deFileChannel
. Cela peut se faire au moyen de la méthoderesolve
, comme l'illustre l'extrait de code suivant qui obtient le chemin d'accès au fichier contenant les nœuds :Path nodesPath = basePath.resolve("nodes.bin");
- Méthode
nodeClosestTo
La méthode
nodeClosestTo
se doit d'être efficace, car elle est destinée à être utilisée lorsque l'utilisateur clique sur la carte afin de placer un nouveau point de passage.Dès lors, pour trouver le point le plus proche, comparez les carrés des distances — obtenus au moyen de la méthode
squaredDistanceTo
dePointCh
— afin d'éviter de calculer inutilement des racines carrées.
3.3. Classe ElevationProfile
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 longueurlength
(en mètres) et dont les échantillons d'altitude, répartis uniformément le long de l'itinéraire, sont contenus danselevationSamples
; lèveIllegalArgumentException
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.
3.3.1. Conseils de programmation
Pour déterminer l'altitude minimum et maximum du profil, vous pouvez vous aider de la classe DoubleSummaryStatistics
qui calcule plusieurs statistiques — dont le minimum et le maximum — des valeurs de type double
passées à sa méthode accept
. L'extrait de test JUnit ci-dessous illustre son utilisation :
DoubleSummaryStatistics s = new DoubleSummaryStatistics(); s.accept(5.25); s.accept(-3.125); s.accept(0); assertEquals(-3.125, s.getMin()); assertEquals(5.25, s.getMax());
3.4. Enregistrement Edge
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 deEdge
dont les attributsfromNodeId
ettoNodeId
sont ceux donnés, les autres étant ceux de l'arête d'identitéedgeId
dans le grapheGraph
.
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.
3.4.1. Conseils de programmation
Pour déterminer la position le long de l'arête du point qui se trouve le plus proche du point qu'elle reçoit, la méthode positionClosestTo
utilise simplement la méthode projectionLength
de Math2
.
Remarquez que cette méthode peut très bien retourner une valeur négative ou supérieure à la longueur de l'arête, ce qui est tout à fait valide. Dans ces cas-là, la position retournée par positionClosestTo
ne se trouve pas sur l'arête elle-même, mais sur la ligne qui la prolonge.
3.5. Enregistrement RoutePoint
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
vautNaN
etdistanceToReference
vautPOSITIVE_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 retournethis
si sa distance à la référence est inférieure ou égale à celle dethat
, etthat
sinon,RoutePoint min(PointCh thatPoint, double thatPosition, double thatDistanceToReference)
, qui retournethis
si sa distance à la référence est inférieure ou égale àthatDistanceToReference
, et une nouvelle instance deRoutePoint
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.
3.6. Interface Route
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.
3.7. Tests
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.
4. Résumé
Pour cette étape, vous devez :
- écrire les classes
Graph
,ElevationProfile
,Edge
,RoutePoint
etRoute
selon les indications données ci-dessus, - tester votre code,
- documenter la totalité des entités publiques que vous avez définies,
- rendre votre code au plus tard le 18 mars 2022 à 17h00, via le système de rendu.
Ce rendu est un rendu testé, auquel 18 points sont attribués, au prorata des tests unitaires passés avec succès.
N'attendez surtout pas le dernier moment pour effectuer votre rendu, car vous n'êtes pas à l'abri d'imprévus. Souvenez-vous qu'aucun retard, aussi insignifiant soit-il, ne sera toléré !