Points et intervalles
Etape 2

De nos jours, un des systèmes de référence géodésique le plus courant est WGS 84. Il est utilisé par exemple par les récepteurs GPS, qui fournissent des coordonnées exprimées dans ce système, et par les systèmes cartographiques en ligne comme OpenStreetMap, Google Maps, Bing Maps, etc. Les modèles du terrain que nous utiliserons dès la prochaine étape sont eux aussi exprimés dans ce système.

WGS-84 est un système ellipsoïdal, qui approxime la forme de la Terre par un ellipsoïde de révolution. Or pour ce projet nous désirons utiliser un système sphérique afin de simplifier les calculs. Dès lors, nous devrions normalement effectuer une conversion entre les coordonnées WGS 84 et celles de notre système.

Toutefois, au vu du faible applatissement de la Terre et de la précision limitée dont nous avons besoin, nous nous permettrons de ne pas faire de conversion et d'admettre que les coordonnées WGS 84 sont des coordonnées à la surface d'une Terre sphérique d'un rayon de 6371 km. Même si cela est rigoureusement faux, les erreurs que cela implique sont négligeables pour notre usage¹.

Sur une sphère, l'angle \(\alpha\) correspondant à l'arc de grand cercle reliant deux points de coordonnées \((\lambda_1, \varphi_1)\) et \((\lambda_2, \varphi_2)\) est donné par la formule suivante :

\[ \newcommand{\haversin}{\mathop{\rm haversin}\nolimits} \alpha = 2 \arcsin\left(\sqrt{\strut\haversin(\varphi_1 - \varphi_2) + \cos\varphi_1\cos\varphi_2\haversin(\lambda_1 - \lambda_2)}\right) \]

A partir de cet angle, il est trivial de déterminer la distance en mètres séparant deux points à la surface de la Terre supposée sphérique, au moyen de la formule donnée à l'étape précédente.

Par exemple, le centre de Lausanne se trouve approximativement aux coordonnées (6.631°, 46.521°) et celui de Moscou aux coordonnées (37.623°, 55.753°). En convertissant ces valeurs en radians et en les insérant dans la formule ci-dessus, on obtient :

Cet angle peut être converti en distance en km à la surface de la Terre au moyen de la formule donnée à l'étape précédente :

\[ l = \alpha\cdot R = 0.37157\cdot 6\,371 \approx 2\,370\,\mathrm{km}\]

valeur qui correspond à celle donnée à l'étape précédente.

Dans quelle direction un observateur placé au centre de Lausanne doit-il se tourner pour regarder en direction de Moscou ? Pour répondre à cette question, il faut déterminer l'azimut du centre de Moscou dans le système de coordonnées horizontales correspondant à l'observateur.

A la surface d'une sphère, la formule permettant de calculer l'angle mathématique correspondant à cet azimut est :

\[ \beta = \arctan\left( \frac{\sin(\lambda_1 - \lambda_2)\cos\varphi_2} {\cos\varphi_1\sin\varphi_2 - \sin\varphi_1\cos\varphi_2\cos(\lambda_1 - \lambda_2)} \right) \]

où \((\lambda_1,\varphi_1)\) est la position de l'observateur et \((\lambda_2,\varphi_2)\) celle du point observé.

Cette formule produit un résultat compris entre \(-\pi\) et \(\pi\) et croissant dans le sens antihoraire. Une conversion est donc nécessaire pour obtenir un azimut.

En insérant dans cette formule les valeurs correspondant aux centres de Lausanne et de Moscou, on obtient :

\[\beta \approx -52.95° \]

Cet angle « mathématique », exprimé dans le sens antihoraire, correspond à un azimut canonique de 52.95°. Du centre de Lausanne, il faut donc se tourner approximativement en direction du nord-est pour regarder vers Moscou.

L'intervalle d'entiers de \(a\) à \(b\), noté ici \( \newcommand{\iint}[2]{[#1\,{.\!.}\,#2]} \iint{a}{b} \), est l'ensemble de tous les entiers compris entre \(a\) et \(b\) (inclus). Formellement :

\[ \iint{a}{b} = \{ x\in\Bbb{Z}\>|\> a \le x \le b\} \]

Notez que, d'après cette définition, un intervalle ne peut pas être vide et contient donc au moins un élément.

Les intervalles d'entiers étant des ensembles, il est sensé de parler de leur intersection, de leur union, de leur différence, etc. Toutefois, certaines de ces opérations peuvent produire des ensembles qui ne sont pas eux-même des intervalles. Ainsi, ni l'intersection ni l'union des intervalles \(\iint{1}{3}\) et \(\iint{10}{10}\) ne produisent un intervalle, car :

et aucun de ces deux ensembles n'est un intervalle d'après la définition donnée plus haut.

Deux intervalles dont l'union produit un intervalle seront dits « unionables ». Ainsi, \(\iint{1}{3}\) et \(\iint{10}{10}\) ne sont pas unionables.

Lorsque l'union de deux intervalles produit un intervalle, nous dirons que ces intervalles sont « unionables ». Tous les intervalles n'étant pas unionables, nous définirons une notion généralisée d'union, l'union englobante, notée \(\cup^+\) et définie ainsi :

\[ \iint{a}{b}\cup^+\iint{c}{d} = \iint{\min(a,c)}{\max(b,d)} \]

On peut facilement vérifier que deux intervalles sont unionables si et seulement si l'union et l'union englobante produisent le même résultat. Il en découle que deux intervalles \(i_1\) et \(i_2\) sont unionables si et seulement si l'égalité suivante est satisfaite :

\[ |i_1\cup i_2| = |i_1\cup^+ i_2| \]

où \(|s|\) représente la taille de l'ensemble \(s\). Cette égalité est équivalente à celle ci-dessous, que nous utiliserons pour déterminer si deux intervalles sont unionables :

\[ |i_1| + |i_2| - |i_1\cap i_2| = |i_1\cup^+ i_2| \]

Les intervalles d'entiers étant des ensembles, il est possible d'en combiner deux au moyen du produit cartésien pour obtenir un ensemble de paires d'entiers :

\[ \iint{a}{b}\times\iint{c}{d} = \{ (x, y)\in\Bbb{Z}\times\Bbb{Z}\>|\> (a\le x\le b) \wedge (c\le y\le d) \} \]

Dans ce qui suit, nous appellerons intervalle bidimensionnel le produit cartésien de deux intervalles, et intervalle unidimensionnel un intervalle d'entiers « simple ».

Tout comme pour les intervalles unidimensionnels, il est sensé de parler de l'intersection, de l'union, de la différence, etc. de deux intervalles bidimensionnels. Néanmoins, une fois encore, il est possible que le résultat de ces opérations ne soit pas un intervalle bidimensionnel.

Il est également possible de définir une notion d'union englobante pour les intervalles bidimensionnels :

Nous dirons que deux intervalles bidimensionnels sont « unionables » si l'union de leurs éléments est un intervalle bidimensionnel. Une fois encore, cela n'est vrai pour deux intervalles bidimensionnels \(i_1\) et \(i_2\) que si l'égalité suivante est satisfaite :

\[ |i_1| + |i_2| - |i_1\cap i_2| = |i_1\cup^+ i_2| \]

Le calcul de l'azimut d'un point à un autre nécessite le calcul de l'arc tangente d'un rapport de deux valeurs. Pour l'obtenir, il faut utiliser la méthode atan2 de la bibliothèque Java, prévue pour cela.

La spécification de la méthode toString demande à ce que la longitude et la latitude soient représentés avec exactement 4 décimales. Pour ce faire, il faut utiliser la méthode statique format de la classe String. Cette méthode permet de formatter une chaîne en remplaçant certaines parties par des valeurs formattées.

La syntaxe des chaînes de formattage est bien expliquée dans la section Format String Syntax de la documentation de la classe Formatter. Ce document étant un peu long et difficile à comprendre, vous pouvez vous inspirer de l'exemple suivant :

Locale l = null;
String s = String.format(l, "[%.3f; %.3f]", 1.1, 3.4567);

qui affecte à s la chaîne [1.100; 3.457].

Le premier argument passé à la méthode format, de type Locale, permet de spécifier comment adapter le formattage aux conventions d'un pays donné. Ici, nous passons null pour éviter toute conversion, ce qui garantit que les nombres à virgule flottante seront formattés avec un point comme séparateur décimal.

Le second argument est ce qu'on appelle une chaîne de formattage (format string). Cette chaîne de formattage est une combinaison de caractères quelconques et de spécificateurs de format (format specifiers), qui commencent toujours par un signe pourcent (%). Chaque spécificateur de format décrit comment un des arguments qui suit la chaîne de formattage doit être formatté.

La chaîne de formattage de l'exemple ci-dessus comporte deux spécificateurs de format, qui sont tous les deux %.3f. Ils spécifient que l'argument qui leur correspond doit être formatté comme un nombre à virgule flottante (f) avec exactement 3 décimales (.3). Dès lors, le premier de ces spécificateur est remplacé par le nombre 1.1 formatté avec trois décimales (1.100) et le second est remplacé par le nombre 3.4567 formatté avec trois décimales également (3.457, notez l'arrondi !). Tous les autres caractères de la chaîne de formattage sont copiés tels quels, ce qui explique le résultat final.

Comme nous le verrons plus tard au cours, la méthode hashCode héritée de Object doit être redéfinie chaque fois que la méthode equals l'est, et inversément. La valeur retournée par hashCode est appelée la valeur de hachage de l'objet à laquelle on l'applique.

Pour des raisons qui deviendront claires plus tard, la valeur de hachage produite par hashCode doit impérativement satisfaire la contrainte suivante :

Deux objets pour lesquels la méthode equals retourne vrai doivent avoir la même valeur de hachage.

De plus, cette méthode doit essayer de faire en sorte que deux objets pour lesquels la méthode equals retourne faux n'aient pas la même valeur de hachage. Cela n'est bien entendu pas toujours possible dans le cas général, car il n'y a qu'un nombre fini de valeurs de type int en Java.

Les deux contraintes ci-dessus n'étant pas très faciles à satisfaire, il est généralement conseillé de confier la tâche du calcul de la valeur de hachage à la méthode statique hash de la classe Objects (avec un s), à laquelle on passe simplement la totalité des attributs utilisés par la méthode equals pour déterminer l'égalité. Dans le cas de la classe Interval1D, cela signifie que la méthode hashCode doit être redéfinie ainsi :

@Override
public int hashCode() {
  return Objects.hash(includedFrom(), includedTo());
}

Différents sites Web vous permettent de calculer des distances et/ou azimuts entre deux points à la surface de la Terre, ce qui peut être utile pour obtenir les valeurs attendues à insérer dans les tests. Attention toutefois : ces sites utilisent parfois un modèle ellipsoïdal de la Terre, ou une sphère de rayon légèrement différent du nôtre. Dès lors, ne vous attendez pas à obtenir exactement les mêmes valeurs qu'eux.

Parmi les sites à disposition, nous vous conseillons en particulier https://map.geo.admin.ch/ dont l'outil de mesure permet de connaître la distance et l'azimut entre deux points en Suisse. Vous pouvez ainsi l'utiliser pour déterminer que la distance entre le coin sud-ouest du Learning Center et le sommet de l'Eiger et d'environ 110.49 km et l'azimut du premier au second point d'environ 86.67°.

Si nous ne vous fournissons pas de tests JUnit, nous vous fournissons néanmoins une archive Zip à importer dans votre projet et contenant un fichier nommé SignatureChecks_02.java. La classe qu'il contient fait référence à la totalité des classes, interfaces et méthodes de cette étape, ce qui vous permet de vérifier que leurs noms et types sont corrects. Cela est capital, car la moindre faute à ce niveau empêcherait l'exécution de nos tests unitaires.

Nous vous fournirons de tels fichiers pour toutes les étapes jusqu'à la mi-semestre, et il vous faudra penser à vérifier systématiquement qu'Eclipse ne signale aucune erreur à leur sujet. Faute de cela, votre rendu se verra refusé par notre système.