Divagations

Petite mise en contexte : cet article va parler de l’application Hémisphère que j’ai récemment développée. Cet appli permet de calculer, s’il existe, un hémisphère comportant plusieurs points et pays sélectionnés par l’utilisateur sur un planisphère.

Vu que ça faisait un bon moment que je ne m’étais pas trituré les neurones à ce point là sur de l’algo, je ne peux m’empêcher de détailler un peu quelques opérations ici.

Calcul d’enveloppe convexe d’un ensemble de points formant un «polygone» sur une sphère

L’application permet de directement sélectionner des pays sur la carte. Mais dans les faits, sélectionner un pays revient à sélectionner les points le délimitant. On verra cependant dans la section suivante que la complexité du calcul d’hémisphère est en `O(n^3)` , ce qui signifie que le nombre d’opérations nécessaires au calcul est proportionnel au cube du nombre de points impliqués. On va donc tâcher de réduire le nombre de points sélectionnés. Pour cela, on va seulement garder les points composant l’enveloppe convexe de cet ensemble de points.

Les pays tracés sur la carte le sont via des ensembles de points nommés Polygon (voire plusieurs Polygon pour les pays en plusieurs «morceaux»), qui portent mal leur nom : les points sont en effet reliés suivant leur loxodromie et non leur orthodromie.

Instant définition : sur une sphère, le trajet le plus court entre deux points est l’orthodromie. Cette orthodromie suit le grand cercle passant par les deux points, ce grand cercle étant l’intersection de la sphère et du plan contenant nos deux points et le centre de la sphère. Si on trace cette orthodromie sur un planisphère, on observe une courbe, et non une droite. En traçant le segment reliant les deux points sur notre planisphère, on obtient la loxodromie, très utile aux navigateurs car il s’agit d’un trajet à cap constant mais plus long que l’orthodromie.¹

Une fois tout ceci précisé, on peut se lancer dans l’élimination successive de points de notre polygone jusqu’à arriver à notre enveloppe. Voici la liste des étapes.

• On récupère le point à la latitude la plus élevée (choix complètement arbitrairement, ça pourrait être la plus faible ou bien la longitude) : ce point appartient à l’enveloppe.
• On commence le parcours des autres points en partant du point suivant et, pour chaque point, on l’élimine si le milieu de la loxodromie reliant les deux points encadrant notre point se trouve hors du polygone.
• Si aucun point n’a été éliminé, on s’arrête. Sinon, bah, on recommence.

Algo très basique et qui serait sûrement facilement améliorable mais il fait ses preuves :D.

Calcul d’un hémisphère contenant N points

Une fois les pays convertis en ensemble de points formant une enveloppe convexe des dits pays, on se retrouve donc avec un ensemble de N points. Le but est maintenant de trouver un hémisphère contenant ces N points, si jamais un tel hémisphère existe.

Cette fois encore, une petite précision. On peut caractériser un hémisphère par, au choix :

• le plan passant par le centre de la sphère et séparant les deux hémisphères, d’équation `ax+by+cz=0` (précisons tout de même que l’on place le centre de la sphère à l’origine du repère, histoire de pas trop se faire chier, quand même);
• le vecteur `vec u=((a),(b),(c))`, vecteur normal du plan (en prenant garde au fait que `a²+b²+c²=1`);
• le point étant le pôle de cet hémisphère.

Une dernière remarque : si on prend un point `P` d’un hémisphère `vec u` de centre `O`, le produit scalaire de `vec u` et `vec (OP)` est positif ou nul.

Maintenant, place à l’algorithme.

• Pour chaque paire de points, on calcule le produit vectoriel des deux vecteurs entre le centre de la sphère et ces points.
  • On calcule ensuite, pour chaque point, le produit scalaire de ce vecteur avec le vecteur défini par ce point.
  • Si tous les produits scalaires sont de même signe, on sélectionne le vecteur précédemment calculé (ou son opposé si tous les produits scalaires sont négatifs).
• Une fois ce test réalisé pour toutes les paires de points possibles, on regarde l’ensemble des vecteurs sélectionnés.
  • Si cet ensemble est vide, on en conclut qu’aucun hémisphère ne peut être obtenu.
  • S’il n’est pas vide, on calcule le vecteur moyen de cet ensemble de vecteurs et on le normalise pour obtenir le vecteur définissant notre hémisphère. Pour tracer cet hémisphère sur la carte, on paramétrise l’intersection de la sphère et du plan dont ce vecteur est le vecteur normal (cette intersection étant un cercle).

Cet algorithme est une adaptation des travaux de Victor Davis.

 

¹ L’étude des loxodromies et orthodromies était le sujet de mon premier sujet de TIPE réalisé en CPGE. Comme indiqué précédemment, l’orthodromie est le trajet le plus court entre deux points mais la loxodromie est plus pratique car à cap constant. Le but était alors de trouver des points sur l’orthodromie permettant de parcourir des portions de loxodromie et ainsi de réduire la longueur du trajet en gardant des sections à cap constant et de programmer tout ça dans Mathematica.
Ce TIPE s’est brutalement interrompu suite à mon échec critique aux concours écrits. Du coup, cet article est l’occasion parfaite pour enfin le sortir quelque part, six ans plus tard (putain, je vieillis). Voici donc la dernière version encore en ma possession de mon document d’étude, en format pdf et nb (par contre, j’ai plus Mathematica pour vérifier que ça fonctionne bien…). Aucune modification n’a été apportée, je les ai sortis de la naphtaline dans cet état; du coup, c’est pas très beau… 😀