Etape 1 – Points et systèmes de coordonnées

1 Introduction

Le but de cette étape est de définir des classes permettant de représenter des points dans les différents systèmes de coordonnées utilisés dans ce projet, et d'offrir des opérations permettant de passer de l'un à l'autre.

1.1 Systèmes de coordonnées

Pour dessiner une carte, il faut pouvoir spécifier la position des objets qui y figurent, ce qui implique l'utilisation d'un (ou plusieurs) systèmes de coordonnées. Dans ce projet, les systèmes de coordonnées suivants sont utilisés :

un système de coordonnées sphérique (généralisation à trois dimensions d'un système polaire), nommé WGS 84, qui est celui utilisé entre autres par les récepteurs GPS,
une famille de systèmes de coordonnées bidimensionnels cartésiens, nommés ici OSM (pour OpenStreetMap) et utilisés par les principaux systèmes cartographiques en ligne.

Le système tridimensionnel WGS 84 est idéal pour représenter la position des points dans l'espace et effectuer des calculs sur ces positions, p.ex. pour connaître la distance séparant deux points. Les systèmes OSM sont quant à eux utiles pour l'affichage de cartes à l'écran.

1.2 Le système WGS 84

Il existe un très grand nombre de systèmes de coordonnées terrestres permettant de déterminer la position d'un point à la surface de la Terre. Toutefois le système WGS 84 utilisé par les récepteurs GPS s'est imposé ces dernières années comme standard de facto pour de nombreuses applications. Il est donc utilisé comme système principal pour ce projet, p.ex. pour identifier la position des arrêts de transports en commun, ou encore pour calculer la distance séparant deux points.

Le système WGS 84 est tridimensionnel, c-à-d qu'un point dans ce système est identifié par trois valeurs, qui forment ses coordonnées géographiques :

la longitude \(\lambda\), qui est la distance angulaire du point à un méridien de référence—un méridien étant un cercle passant par les deux pôles,
la latitude \(\phi\), qui est la distance angulaire du point à l'équateur,
l'altitude, qui est la distance verticale entre le point et le niveau de la mer.

Etant donné que l'altitude ne joue pas un rôle important dans ce projet, elle est supposée nulle et les points WGS 84 sont simplement représentés par la paire \((\lambda, \phi)\) de leur longitude et leur latitude.

(Pour donner une idée des erreurs que cela peut induire dans la région, sachez qu'en mesurant la distance du lac de Sauvabelin au château d'Ouchy en ligne droite et en ignorant la différence d'altitude, on commet une erreur d'environ 0.3%).

Figure 1 : Latitude et longitude (image de Wikimedia Commons)

Le méridien de référence utilisé par le système WGS 84 est celui de Greenwich. La longitude est comprise entre -180° et +180°, les valeurs négatives étant à l'ouest de Greewich, les positives à l'est. La latitude est comprise entre -90° et +90°, les valeurs négatives étant au sud de l'équateur, les positives au nord.

Par exemple, dans le système WGS 84, le point de longitude +6.57° et de latitude +46.52° se trouve sur le campus de l'EPFL.

Distance entre deux points

Un des intérêts des systèmes de coordonnées géographiques comme WGS 84 est qu'il est relativement simple de calculer la distance séparant deux points.

En effet la distance \(d\) à la surface d'une sphère de rayon \(R\) entre deux points de coordonnées \((\lambda_1, \phi_1)\) et \((\lambda_2, \phi_2)\) peut s'obtenir au moyen de la formule suivante :

\begin{equation} \newcommand{\haversin}{\mathop{\rm haversin}\nolimits} \newcommand{\arsinh}{\mathop{\rm arsinh}\nolimits} d = 2 R \arcsin\left(\sqrt{\strut\haversin(\phi_1 - \phi_2) + \cos(\phi_1)\cos(\phi_2)\haversin(\lambda_1 - \lambda_2)}\right) \end{equation}

où la fonction \(\haversin\) est définie ainsi :

\[ \haversin(x) = \sin^2\left(\frac{x}{2}\right) \]

Si l'on fait l'hypothèse que la Terre est une sphère de rayon \(R=6378137\) mètres, on peut utiliser cette formule pour calculer la distance séparant deux points à sa surface. Le résultat ainsi obtenu n'est pas rigoureusement correct car la Terre n'est pas une sphère—sa forme est irrégulière mais plus proche d'un ellipsoïde que d'une sphère—mais l'erreur peut être considérée comme négligeable pour ce projet.

1.3 Les systèmes OSM

Les principaux systèmes cartographiques en ligne (OpenStreetMap, Google Maps, Bing, etc.) utilisent tous la même famille de systèmes de coordonnées cartésiens, appelés ici systèmes OSM.

Ces systèmes cartographiques permettent de visualiser l'image d'une carte du monde à différentes échelles, et chaque échelle possède son propre système de coordonnées. Les échelles sont identifiées par leur niveau de zoom, un entier compris entre 0—qui correspond à la plus grande échelle—et une valeur supérieure qui dépend du système mais est souvent aux alentours de 20.

A la plus grande échelle, c-à-d au niveau de zoom 0, la carte du monde est une image carrée de 256 pixels de côté. Le système de coordonnées OSM correspondant à ce niveau de zoom est simplement celui de l'image de la carte, c-à-d que son origine se trouve dans le coin supérieur gauche de l'image, et que chaque pixel correspond à une unité, comme illustré ci-dessous.

Figure 2 : Le système de coordonnées OSM au niveau de zoom 0

La totalité du monde n'apparaît pas sur cette carte puisqu'une partie des deux régions polaires n'y est pas représentée. Cela est dû à l'utilisation de la projection de Mercator, qui projette les pôles à l'infini. Les créateurs des systèmes cartographiques sus-mentionnés ont ainsi décidé de borner les latitudes de leurs cartes à l'intervalle [-85.051129°, 85.051129°], ce qui présente l'avantage de produire des cartes parfaitement carrées avec la projection choisie. Les parties du monde ainsi omises n'étant pas (ou peu) peuplées, la perte n'est généralement pas gênante en pratique.

Au niveau de zoom suivant, à savoir 1, la taille de la carte est simplement doublée. Le système de coordonnées OSM correspondant à ce niveau de zoom est celui de cette nouvelle image, deux fois plus grande (dans chacune des dimensions) que la précédente, comme illustré ci-dessous.

Figure 3 : Le système de coordonnées OSM au niveau de zoom 1

De manière générale, au niveau de zoom \(z\), la carte du monde est une image carrée de \(2^z\times 256 = 2^{z+8}\) pixels de côté. Le système de coordonnées OSM correspondant à ce niveau de zoom est celui de cette image.

1.4 Projection

Pour passer d'un système de coordonnées géographique tridimensionnel comme WGS 84 à un système cartographique bidimensionnel comme le système OSM, on utilise une projection cartographique. Il existe une très grande variété de telles projections, chacune ayant ses avantages et inconvénients, mais les systèmes cartographiques en ligne utilisent tous une projection de Mercator en faisant l'hypothèse (incorrecte, comme dit plus haut) que la Terre est une sphère parfaite. Les paramètres de cette projection sont choisis de telle manière que le point de coordonnées WGS 84 (0°,0°) se trouve au centre de la carte.

Au niveau de zoom \(z\), les coordonnées OSM d'un point de coordonnées WGS 84 \((\lambda, \phi)\), avec \(\lambda\) et \(\phi\) en radians, sont données par les formules suivantes :

\begin{aligned} x & = \frac{s}{2\pi}(\lambda + \pi)\\ y & = \frac{s}{2\pi}\left(\pi - \arsinh(\tan(\phi))\right) \end{aligned}

où \(s=2^{z + 8}\).

Ces formules s'inversent facilement pour obtenir celles permettant de transformer un point de coordonnées OSM \((x, y)\) au niveau de zoom \(z\) en coordonnées WGS 84 \((\lambda, \phi)\) :

\begin{aligned} \lambda & =\frac{2\pi}{s}x - \pi\\ \phi & = \arctan\left(\sinh\left(\pi - \frac{2\pi}{s}y\right)\right) \end{aligned}

où \(s=2^{z + 8}\).

A noter que ces formules ne peuvent s'inverser qu'en faisant l'hypothèse que tous les points sont à la surface de la sphère modélisant la Terre.

2 Mise en œuvre Java

Afin de mettre en œuvre les concepts décrits plus haut, il vous est demandé d'écrire trois classes Java :

les classes PointWGS84 et PointOSM, qui modélisent des points dans les systèmes de coordonnées WGS 84 et OSM, respectivement,
la classe Math, qui offre des méthodes statiques permettant de calculer des fonctions mathématiques diverses qui n'existent pas dans la bibliothèque standard Java, comme l'inverse du sinus hyperbolique.

Ces trois classes sont décrites en détail ci-dessous. Elles doivent toutes faire partie de sous-paquetages du paquetage ch.epfl.isochrone qui contiendra tout le code de ce projet.

2.1 Classe `Math`

La classe finale et publique Math du paquetage ch.epfl.isochrone.math est conçue pour contenir des fonctions mathématiques courantes sous forme de méthodes statiques.

Interface publique

Pour cette étape, la classe Math ne contient que les deux méthodes publiques et statiques suivantes :

double asinh(double x), qui retourne le sinus hyperbolique inverse de son argument, donné par la formule suivante :

\[ \arsinh(x) = \ln\left(x + \sqrt{1 + x^2}\right) \]

double haversin(double x), qui retourne le résultat de la fonction \(\haversin\) décrite plus haut.

Conseils de programmation

La classe Math ne doit pas pouvoir être instanciée, puisque son seul but est de fournir des méthodes statiques. Pour garantir qu'elle ne l'est effectivement jamais, équipez-la d'un constructeur par défaut privé (et vide).

Pour programmer cette classe, vous pouvez vous aider de la classe Math du paquetage java.lang, en particulier de ses méthodes statiques log (logarithme naturel), pow (élévation à la puissance), sin (sinus) et sqrt (racine carrée).

2.2 Classe `PointWGS84`

La classe finale et publique PointWGS84 du paquetage ch.epfl.isochrone.geo modélise un point dans le système de coordonnées WGS 84.

Interface publique

La classe PointWGS84 possède un unique constructeur public :

PointWGS84(double longitude, double latitude), qui construit un point de longitude et latitude données et exprimées en radians. Lève l'exception IllegalArgumentException si la longitude est invalide (c-à-d hors de l'intervalle \([-\pi;\pi]\)) ou si la latitude est invalide (c-à-d hors de l'intervalle \([-\tfrac{\pi}{2}; \tfrac{\pi}{2}]\))

Cette classe possède de plus les méthodes publiques suivantes :

double longitude(), qui retourne la longitude du point en radians.
double latitude(), qui retourne la latitude du point en radians.
double distanceTo(PointWGS84 that), qui retourne la distance, en mètres, séparant le récepteur (c-à-d le point auquel on l'applique) du point passé en argument.
PointOSM toOSM(int zoom), qui retourne le point dans le système de coordonnées OSM au niveau de zoom passé en argument. Lève l'exception IllegalArgumentException si le niveau de zoom est invalide, c-à-d négatif.
String toString(), qui retourne une représentation textuelle du point, qui doit être formée de la longitude et de la latitude en degrés, séparées par une virgule et entourées d'une paire de parenthèses. Par exemple, le point de longitude +6.57° et de latitude +46.52° doit être représenté par la chaîne (6.57,46.52). Redéfinit la méthode toString héritée de Object.

Conseils de programmation

Equipez votre classe de deux champs privés et finaux de type double, contenant la latitude et la longitude du point, en radians.

En rendant ces champs finaux, vous garantissez que les instances de cette classe sont immuables, c-à-d qu'elles ne peuvent pas être modifiées une fois créées. Comme nous le verrons, cette propriété facilite grandement l'écriture de programmes corrects, et nous tâcherons donc de rendre la plupart de nos classes immuables.

Pour programmer les méthodes décrites ci-dessus, vous pouvez également vous aider de la classe Math du paquetage java.lang, qui définit p.ex. la constante PI pour \(\pi\) et les méthodes statiques asin (sinus inverse), cos (cosinus), sqrt (racine carrée), tan (tangente) et toDegrees (conversion de radians en degrés). Il va de soi que la classe Math que vous venez d'écrire est également utile.

2.3 Classe `PointOSM`

La classe finale et publique PointOSM du paquetage ch.epfl.isochrone.geo modélise un point dans l'un des systèmes de coordonnées OSM.

Interface publique

La classe PointOSM possède la méthode publique statique suivante :

int maxXY(int zoom), qui retourne la taille de l'image de la carte du monde au niveau de zoom donné. Cette taille est également la plus grande coordonnée x ou y admissible à ce niveau de zoom, d'où le nom de la méthode. Lève l'exception IllegalArgumentException si le zoom est invalide, c-à-d négatif.

Elle est également équipée d'un unique constructeur public :

PointOSM(int zoom, double x, double y), qui construit un point de coordonnées x et y, au niveau de zoom donné. Lève l'exception IllegalArgumentException si le niveau de zoom est négatif, ou si l'une des deux coordonnées n'est pas dans l'intervalle admissible allant de 0 à la valeur maximale.

Enfin, cette classe est équipée des méthodes publiques suivantes :

double x(), qui retourne la coordonnée x du point.
double y(), qui retourne la coordonnée y du point.
int roundedX(), qui retourne l'entier le plus proche de la coordonnée x du point.
int roundedY(), qui retourne l'entier le plus proche de la coordonnée y du point.
int zoom(), qui retourne le niveau de zoom du système de coordonnées du point.
PointOSM atZoom(int newZoom), qui retourne ce même point mais au niveau de zoom passé en argument. Par exemple, le point de coordonnées (30,128) au niveau de zoom 0 a les coordonnées (60,256) au niveau de zoom 1, comme illustré plus haut. Lève l'exception IllegalArgumentException si le niveau de zoom passé est invalide, c-à-d négatif.
PointWGS84 toWGS84(), qui retourne le point dans le système de coordonnées WGS 84.
String toString, qui retourne une représentation textuelle du point, qui doit être formée du niveau de zoom, de la coordonnée x et de la coordonnée y, séparés par des virgules et entourés d'une paire de parenthèse. Par exemple, la représentation textuelle du point de coordonnées (102.2, 78.5) au niveau de zoom 3 est la chaîne (3,102.2,78.5). Redéfinit la méthode toString héritée de Object.

Conseils de programmation

Equipez votre classe PointOSM de trois champs privés et finaux, le premier de type int contenant le niveau de zoom et les deux autres de type double contenant les coordonnées du point. Ici encore, en rendant les champs finaux vous garantissez l'immuabilité des instances de cette classe.

Pour programmer les méthodes ci-dessus, utilisez encore la classe Math du paquetage java.lang, en particulier ses méthodes round et pow.

2.4 Tests

Afin de vous permettre de tester les classes écrites plus haut, nous vous fournissons trois classes de test : TestMathTrig, TestPointWGS84 et TestPointOSM. Ces classes se trouvent dans les mêmes paquetages que les classes qu'elles testent, ce qui est généralement une bonne idée car il est ainsi possible d'avoir accès aux éléments qui ne sont visibles que dans le paquetage.

Pour vous aider pour cette première étape, nous vous fournissons des tests très complets qui devraient vous permettre d'être raisonnablement sûrs que vos classes sont correctes.

Pour importer ces classes dans votre projet, procédez ainsi :

Téléchargez le fichier tests-e01.zip, qui est une archive Zip contenant les fichiers de tests que nous vous fournissons.
Dans Eclipse, sélectionnez votre projet dans l'explorateur de paquetages (Package Explorer) puis sélectionnez l'entrée Import… du menu File.
Dans la boîte de dialogue qui s'ouvre alors, déroulez la section General puis sélectionnez Archive File et cliquez sur le bouton Next.
Remplissez le champ From archive file avec le nom complet du fichier que vous avez téléchargé plus haut (un simple glisser-déposer devrait suffire).
Cliquez sur Finish.
En prenant garde à ce que votre projet soit toujours sélectionné dans l'explorateur de paquetage, sélectionnez l'entrée Properties du menu Project.
Dans la boîte de dialogue qui s'ouvre, sélectionnez l'entrée Java Build Path.
Activez l'onglet Source et cliquez sur Add Folder…. Dans la boîte de dialogue qui s'ouvre, choisissez le répertoire test qui vient d'être créé puis cliquez sur Ok.
Activez l'onglet Libraries et cliquez sur Add Library…. Dans la boîte de dialogue qui s'ouvre, choisissez JUnit, puis cliquez sur Next puis Finish.

Une fois cela fait, vous devriez avoir un nouveau répertoire nommé test dans votre projet. En le déroulant, vous devriez voir qu'il contient deux paquetages, ch.epfl.isochrone.geo et ch.epfl.isochrone.math. Le premier contient les classes TestPointWGS84 et TestPointOSM, tandis que le second contient la classe TestMathTrig. Pour exécuter tous les tests, vous pouvez simplement cliquer avec le bouton droit sur le répertoire test et sélectionner Run as puis JUnit test.

Il va de soi que vous n'avez pas le droit de modifier quoi que ce soit dans les tests fournis pour les faire s'exécuter avec succès !

2.5 Documentation

Une fois les tests exécutés avec succès, il reste à documenter la totalité des entités publiques (classes, champs et méthodes) définies dans cette étape, au moyen de commentaires JavaDoc.

Les commentaires JavaDoc sont des commentaires structurés que l'on peut attacher aux différentes entités d'un programme (classes, interfaces, champs et méthodes). On les reconnaît au fait qu'ils commencent par une barre oblique suivie de deux astérisques (/**).

Les commentaires JavaDoc peuvent inclure des étiquettes (tag), qui commencent par un arobas (@). Même s'il existe de nombreuses étiquettes, vous n'en utiliserez que quatre dans ce projet :

L'étiquette @author, qui est suivie du nom d'un des auteurs de la classe ou interface à laquelle elle est attachée. Peut apparaître plusieurs fois s'il y a plus d'un auteur.
L'étiquette @param, qui est suivie du nom d'un paramètre de l'entité à laquelle on l'attache (méthode ou constructeur) et d'une description de la signification de ce paramètre.
L'étiquette @throws, qui est suivie du nom d'une exception qui peut être levée par la méthode à laquelle on l'attache et d'une description des cas dans lesquels elle est levée.
L'étiquette @return, qui est suivie d'une description de la valeur retournée par la méthode à laquelle on l'attache.

Pour ce projet, vous avez l'obligation de lister la totalité des auteurs de chaque interface ou classe publique que vous rendez. Le prénom et le nom de chaque auteur doit être suivi de son numéro SCIPER, composé de six chiffres consécutifs (sans aucun caractère de séparation) entourés de parenthèses.

Attention à ne pas oublier ces numéros SCIPER et à les écrire correctement, car nous les utiliserons pour automatiquement attribuer les fichiers rendus à leur(s) auteur(s). Une erreur pourrait donc vous coûter des points.

Pour illustrer l'utilisation des différentes étiquettes mentionnées plus haut, voici ce à quoi la documentation de la classe PointWGS84 et l'une de ses méthodes pourrait ressembler :

/**
 * Un point dans le système de coordonnées WGS 84.
 *
 * @author Jean Dupond (123456)
 * @author Pierre Durand (654321)
 */
public final class PointWGS84 {
    // …

    /**
     * Retourne ce point mais dans un système de coordonnées OSM.
     *
     * @param zoom
     *         Le niveau de zoom du système de coordonnées OSM.
     * @throws IllegalArgumentException
     *         Si le zoom est négatif.
     * @return Le point dans le système de coordonnées OSM au
     *         niveau de zoom donné.
     */
    public PointOSM toOSM(int zoom) {
        // …
    }

    // …
}

Deux commandes Eclipse sont d'une grande aide lorsqu'on rédige des commentaires JavaDoc :

Dans le menu Source, l'entrée Generate Element Comment permet de générer un squelette de commentaire JavaDoc pour l'élément sous le curseur.
Dans le menu Source, l'entrée Format Element permet de reformatter l'élément sous le curseur. Lorsqu'on l'utilise dans un commentaire JavaDoc, celui est reformatté de manière plaisante.

3 Résumé

Pour cette étape, vous devez :

Ecrire les classes PointWGS84, PointOSM et Math en fonction des spécifications ci-dessus.
Exécuter les tests fournis et vérifier qu'ils s'exécutent sans erreur. Si les tests échouent, il vous faut déterminer pourquoi et corriger les erreurs dans votre code.
Documenter la totalité des entités publiques que vous avez définies.

Prenez bien garde à suivre à la lettre les indications données plus haut concernant les noms des différentes entités (paquetages, classes, méthodes, etc.) ainsi que leurs différents attributs (type, visibilité, « modifiabilité », etc.). Notez en particulier que les trois classes doivent être finales, de même que la totalité de leurs champs !

Etape 1 – Points et systèmes de coordonnées

1 Introduction

1.1 Systèmes de coordonnées

1.2 Le système WGS 84

Distance entre deux points

1.3 Les systèmes OSM

1.4 Projection

2 Mise en œuvre Java

2.1 Classe Math

Interface publique

Conseils de programmation

2.2 Classe PointWGS84

Interface publique

Conseils de programmation

2.3 Classe PointOSM

Interface publique

Conseils de programmation

2.4 Tests

2.5 Documentation

3 Résumé

2.1 Classe `Math`

2.2 Classe `PointWGS84`

2.3 Classe `PointOSM`