David Madore's WebLog: 2007-08

This WebLog is bilingual, some entries are in English and others are in French. A few of them have a version in either language. Other than that, the French entries are not translations of the English ones or vice versa. Of course, if you understand only English, the English entries ought to be quite understandable without reading the French ones.

Ce WebLog est bilingue, certaines entrées sont en anglais et d'autres sont en français. Quelques-unes ont une version dans chaque langue. À part ça, les entrées en français ne sont pas des traductions de celles en anglais ou vice versa. Bien sûr, si vous ne comprenez que le français, les entrées en français devraient être assez compréhensibles sans lire celles en anglais.

Note that the first entry comes last! / Notez que la première entrée vient en dernier !

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entries published in August 2007 / Entrées publiées en août 2007:

(Tuesday)

Converting latitude+longitude to Universal Transverse Mercator

[The following is a highly technical note (i.e, odds are you don't want to read it at all), which I'm writing in the form of a blog post mainly because I'm too lazy to start another Web page—but it might get copied elsewhere eventually (if someone wants to dump it on Wikipedia, feel free to).]

I've long been intrigued by the oft-used (especially in conjunction with GPS units) UTM coordinates: explanations as to how UTM coordinates are defined exactly is very hard to find (the spherical case is simple enough, but the ellipsoidal one is a much tougher nut), and although there are many online tools (such as this one) to convert from latitude+longitude to UTM and back, they use black box formulæ, converging power series, and looking at the source will give you very little insight on what is going on. So here is an attempt at a mathematically precise definition (it took me a whole day of angry formula-crunching before I came up with something entirely correct, so I won't spare the details).

First of all, what is a transverse mercator projection? It can be defined by starting from a central meridian (UTM uses 60 possible central meridians, one for each UTM zone) and constructing the mathematically unique projection from a spheroid (= rotation of an ellipse about one of its axes) to a plane which is conformal (= preserves angles) and maps the central meridian to a straight line with constant scale. So here are the defining features of Universal Transverse Mercator:

  • It divides the Earth in 60 longitude zones, each 6° wide: zone 1 ranges from 180° to 174°W, zone 2 from 174°W to 168°W and so on through zone 30 from 6°W to 0°, zone 31 from 0° to 6°E, up to zone 60 from 174°E to 180°. Each zone's central meridian is halfway between the limiting longitudes (e.g., zone 33's central meridian is 15°E). UTM coordinates are given relative to a longitude zone and a hemisphere (North or South).
  • In each zone, UTM is strictly conformal (= preserves angles). In practice, this means that it does not distort shapes anywhere, or that the UTM grid is a square grid everywhere, and it appears square when displayed on any conformal map projection. (Note that this does not imply that the lines of the grid are aligned north-south and east-west! But they are always perpendicular.)
  • Each zone's central meridian (which receives an easting coordinate of 500000, see below) is mapped to a vertical line along which the vertical (northing) coordinate is simply proportional to distance (on the ellipsoid) along that meridian; however,
  • the scale along the central meridian is not 1:1, it is 9996:10000. In other words, two points lying at 10km's distance from one another on the central meridian will have vertical (northing) coordinates differing by only 9996. The reason for this is that the map scale increases on either side of the meridian (as is unavoidable when mapping a curve surface) and the 0.04% decrease at the center is chosen to make the average scale on a 6°-wide zone roughly 1:1.
  • The two UTM coordinates, easting (given first) and northing (given second) are orthogonal and measured in meters (after the transverse mercator projection and the 9996:10000 scale are applied). Easting is measured horizontally, with the central meridian having value 500000 (in practice, it can take values from 166021 to 833979 at the equator, the range being more narrow at higher latitudes). Northing is measured vertically, with the equator having value 0 in the northern hemisphere and 10000000 in the southern hemisphere; in the northern hemisphere, it ranges from 0 at the equator to 9328094 at 84°N on the central meridian, or even 9997965 if used all the way to the pole (but this normally isn't supposed to happen: beyond 84°N, and beyond 80°S Universal Polar Stereographic coordinates should be used instead of UTM).
  • UTM is (nowadays) almost exclusively used with the WGS84 ellipsoid: this has a semimajor axis of a = 6378137m (exactly) and a flattening of f = 1 − b/a = 1/298.257223563 (exactly).

This is a complete definition, however it isn't a very usable one because it lacks a description of how to use the conformal part of the definition to actually convert geodetic coordinates to Universal Transverse Mercator. If we were to use a spherical Earth model, computations would be easy enough:

(samedi)

David découvre de nouveaux parcs

Armés d'un instrument me permettant de ne plus craindre de me perdre ☺, mon poussinet et moi nous sommes mis en quête de territoires inexplorés dans Paris. Aujourd'hui je suis allé visiter le square des Batignolles, que je ne connaissais pas du tout (OK, c'est un peu limité comme wild west, je fais ce que je peux). C'est tout petit comme parc, mais c'est très mignon : un jardin à l'anglaise aménagé en square parisien, avec un minuscule plan d'eau où s'ébattent des anatidés, une cabane où l'on vend des gaufres, des mômes qui jouent au manège, une allée Barbara (chanteuse française), et des trains estampillés Transilien qui passent en contrebas. (Car le square surplombe les voies partant de la gare Saint-Lazare ; et à proximité de là on trouve cette bizarrerie qu'est la station Pont Cardinet, la seule gare de train de banlieue située à Paris intra muros.)

Ensuite, alors que nous nous apprêtions à rentrer par un autre chemin, nous sommes tombés sur un autre jardin dont j'ignorais jusqu'à l'existence — ce qui est normal vu qu'il vient d'apparaître : le parc Clichy-Batignolles (juste de l'autre côté de la rue Cardinet). Il s'agit d'un de ces jardins dans le style moderne, comme le parc André Citroën (que j'aime beaucoup), les jardins de Bercy ou dans une moindre mesure le parc de la Villette. Celui-ci remplace des terrains de la SNCF (hangars ou voies de triage, je ne sais pas exactement) qui ne devaient plus beaucoup servir, il est encore en train d'être réalisé, et même inachevé il a l'air très réussi. À ce que je comprends, il était prévu que le village olympique de Paris-2012 soit situé là. À moins que ce soit un coup d'éclat de Madame de Panafieu. Ou les deux. Toujours est-il que c'est très joli : moins floral que Bercy, moins complexe que le parc André Citroën, mais totalement différent du square d'en face.

(jeudi)

David s'amuse avec un GPS

J'ai craqué pour le joujou de geek (ce sera mon cadeau d'anniversaire à moi-même) et je me suis acheté un récepteur GPS (portable, bien sûr, pas un truc pour voiture) : précisément, il s'agit d'un eTrex Venture CX de Garmin que j'ai eu pour environ 300€ au Vieux Campeur. La fonctionnalité de base que je voulais c'est simplement de pouvoir indiquer la position dans différents systèmes de coordonnées (latitude+longitude et UTM surtout) pour pouvoir la relever ensuite sur une carte ou Google Local, l'altitude et la vitesse approximatives, et l'heure précise. Ça ça s'obtient pour une centaine d'euros. Ensuite il y a pouvoir enregistrer des points marqués et un chemin, et les communiquer avec l'ordinateur.

En pratique ça fonctionne vraiment très bien. Le GPS était assez mauvais à ses débuts parce que le gouvernement américain le brouillait intentionnellement, mais maintenant (depuis la décision de Clinton de couper ce brouillage en 2000, et grâce aussi aux progrès techniques) on a assez facilement une précision de 3–5m en terrain dégagé (le facteur principal d'imprécision étant alors semble-t-il l'état de l'ionosphère). Et ça marche encore souvent assez bien même en ville ou dans des circonstances pas forcément optimales (depuis ma fenêtre, j'ai pu enregistrer le parcours du TGV entre Chambéry et Paris : et pour ce que j'ai contrôlé sur Google Local il est fiable — d'ailleurs je confirme que ces TGV font des pointes à 300km/h sur lignes à grande vitesse et à 160km/h sur d'autres lignes). Et c'est vraiment utile, quand on se promène, pour lire une carte IGN au 1:25000 (en supposant que celle-ci soit marquée compatible GPS, c'est-à-dire qu'elle ait la grille kilométrique UTM imprimée : on demande au GPS d'afficher les coordonnées UTM et on repère les derniers chiffres comme une position dans le carreau).

Le positionnement est un peu lent à la mise en route parce que pour chacun de la douzaine de satellites théoriquement visibles à un endroit donné il va falloir (avant de pouvoir s'en servir effectivement pour se localiser) acquérir un éphéméride, c'est-à-dire ses paramètres orbitaux extrêmement précis, valables pour quatre heures, et cela demande en gros[#] une dizaine de secondes de réception continue du satellite en question (ensuite, dès que le satellite sera visible, même brièvement, le récepteur pourra en tirer des informations utiles). Du coup, ça ressemble à un petit jeu : on voit les satellites d'abord clignotants sur l'écran (c'est-à-dire qu'on n'a pas leur éphéméride complet) et on se demande quand on va réussir à les avoir (ils sont alors marqués en bleu sur l'écran de mon récepteur).

Au niveau technique, je trouve que ce système est un exploit. C'est le genre de choses que j'aurais imaginées théoriquement possibles mais pratiquement irréalisables (se positionner au mètre près sur la Terre en mesurant la différence de temps de venue de signaux depuis des satellites qui tournent à 20000km d'altitude, surely you're joking), et c'est vraiment épatant de voir que ça fonctionne. Pour autant, il y a l'air d'avoir pas mal d'aspects bizarres ou mal pensés dans le système, et l'article Wikipédia donne parfois envie de se frapper la tête contre les murs : mais bon, vu que Galileo n'est pas encore à l'ordre du jour et que le système russe équivalent permet de se positionner à 100m et les jours pairs seulement, on s'en tient au GPS qui a le bon goût de marcher.

La communication avec l'ordinateur fonctionne plutôt bien[#2]. Par contre, là où je suis déçu, c'est pour ce qui est des cartes.

Je m'attendais, en achetant l'appareil, à pouvoir ensuite aller sur le site Web de l'IGN, choisir une région qui m'intéresse, payer une somme comme 10€ et avoir en échange un fichier à mettre sur la carte mémoire (µSD) du GPS contenant les informations géographiques et topographiques de la région en question. Las ! L'IGN ne vend que des CD à 100€ pièce (pour Windows uniquement, bien sûr) contenant des cartes pour ce GPS (et encore, ils n'étaient pas capables de m'assurer avec certitude que ça fonctionnerait bien avec ce modèle précis). Manifestement il y a des gens trop stupides pour comprendre que le principe de vendre des informations en ligne c'est justement de vendre ces informations, pas de vendre des CD contenant ces informations (ou en tout cas, pas d'obliger les gens à acheter obligatoirement de tels CD). Du côté du fabricant (Garmin), ce n'est guère mieux, c'est plus cher, et de toute façon il est américain alors l'Europe l'intéresse très peu. Je ne vais sûrement pas payer pour ces trucs sans une bonne assurance que je pourrai en faire quelque chose.

Tout espoir n'est pas perdu, cependant, parce que même si l'IGN échoue ici lamentablement dans sa mission de service public (je trouve que les cartes de la France produites par un organisme public de ce genre devraient être téléchargeables librement et sous un format ouvert, sans logique de rentabilité d'autant que le coût principal du relevé de la base doit déjà être amorti ; mais ce n'est pas demain la veille que ça se produira), d'autres, bénévolement, tâchent de s'y substituer[#3]. Je pense surtout au projet OpenStreetMap : il s'agit d'une sorte de Wiki sauf que cette fois le but est de cartographier le monde (je ne saurais dire si c'est plus ou moins ambitieux que Wikipédia…). Ce sont surtout des Anglais qui font ça : pour l'instant les données en France (même à Paris) sont pratiquement inexistantes (il n'y a que quelques rues du centre de Paris — et encore, sans les noms), mais à la limite les données ce n'est pas le plus important : le plus important c'est d'avoir mis au point un format de données et une infrastructure pour en faire quelque chose (produire des cartes avec Mapnik ou Osmarender, éditer les données en ligne ou avec JOSM, et il y a même un utilitaire, Mkgmap, pour convertir les données au format propriétaire de Garmin). Donc je devrais pouvoir avoir[#4] au moins les grands axes à Paris et surtout je vais pouvoir contribuer à y rajouter quelques données manquantes.

(L'ironie de l'histoire c'est qu'il y a déjà un plan libre de Paris beaucoup plus complet ici ; mais convertir le format SVG dans lequel il se trouve en de vraies données cartographiques risque d'être délicat. Au moins, je crois qu'il n'y a pas de problème gratuit d'incompatibilité de licence.)

[#] Plus exactement, si j'ai bien compris, il faut acquérir deux sous-trames (précises) complètes parmi les cinq qui composent le message de navigation : et chaque sous-trame prend six secondes à être transmise et est transmise toutes les trente secondes.

[#2] Précision technique, donc : sous Linux, j'utilise le module garmin-gps (généré par CONFIG_USB_SERIAL_GARMIN et qui fait apparaître un périphérique /dev/usb/ttyUSB0) et le logiciel gpsbabel (sur le périphérique en question) pour lire et sauvegarder les points (waypoints) et les routes (tracks). La lecture marche parfaitement, l'écriture échoue parfois aléatoirement (mais en insistant ça semble bien se passer).

[#3] Je propose d'ailleurs ça comme preuve qu'un service public à échoué : lorsque des gens se mettent à refaire bénévolement (et sans moyens) le boulot c'est vraiment qu'il y a un problème. Il serait intéressant de savoir ce qui se passerait si on commençait à demander des subventions publiques pour ça, d'ailleurs. Est-ce que c'est possible d'obtenir des subventions pour refaire correctement quelque chose qu'un service public existant fait trop mal ?

[#4] Je parle au futur (enfin, avec plein de modalités) parce que je n'ai pas encore acheté la carte µSD pour mettre les données sur le GPS. Mais quelqu'un a réussi à faire exactement ce que je veux faire, donc ça devrait marcher.

(mercredi)

Modem RTC, récepteur GPS

Mon poussinet va me traîner quelques jours dans les Alpes du côté de Saint-Jean-de-Maurienne. Comme je ne veux pas pour autant me couper de la civilisation, je ressuscite un vieux modem RTC série à commandes Hayes. (Mon portable a un modem interne, mais c'est un softmodem, ou winmodem, comme on qualifie ces modems qui, en fait, ne savent justement pas moduler et démoduler : il faut confier cette tâche à un logiciel et, sous Linux, il semble qu'il n'en existe pas, ou en tout cas pas de libre, de sorte qu'ils peuvent juste servir de répondeur téléphonique ou quelque chose de ce goût-là.) Pas de port série, non plus, donc je vais m'acheter un convertisseur USB-série et espérer que ce bricolage fonctionne pas trop mal. Mais ça fait si longtemps que je n'ai pas utilisé une connexion moins bien qu'ADSL, je risque d'être tout perturbé.

Encore dans le registre des geekitudes, je pense que je vais en profiter, aussi, pour m'acheter un récepteur GPS. Mais de poche : ce n'est plus très facile à trouver, en fait, maintenant que tous les récepteurs GPS semblent destinés aux voitures. (Et les rares récepteurs de poche qu'on trouve semblent souvent faire PDA en même temps : bof.)

(dimanche)

Affichage du nombre de commentaires

J'ai changé la façon dont s'affiche le nombre de commentaires des entrées de ce blog : maintenant ça devrait fonctionner sous un beaucoup plus grand nombre de navigateurs (et plus seulement les gros lézards verts qui ont muté en des renards enflammés).

(vendredi)

Jouons encore avec JavaScript

Ça fait longtemps que je cherche un langage de programmation dans lequel on puisse très facilement fabriquer des petits jeux d'aventure à la (Colossal Cave) Adventure ou à la Zork. Après avoir beaucoup considéré des langages très variés (notamment SmallTalk, Ruby, Pike, Java et encore d'autres), je me dis que c'est peut-être encore JavaScript le plus approprié (l'autre possibilité étant d'écrire moi-même un langage ad hoc, mais c'est beaucoup de travail — même si je me contente de faire un interpréteur et de le baser sur un langage déjà de haut niveau comme Java).

Toujours est-il que, pour expliquer ce que je veux dire, vous pouvez voir cette démonstration de micro jeu d'aventure (il n'y a évidemment rien d'intéressant à y faire pour l'instant, je me contente d'illustrer le genre de choses que je cherche). Vous êtes bien sûr encouragés à regarder le code source de la page (qui, par ailleurs, ne marchera presque certainement pas sous Internet Explorer vue la quantité notoire de bugs de celui-ci ; en revanche, je l'ai testée avec succès sous Firefox et Konqueror), et à créer des petits mondes d'aventure dans ce style. Le gros défaut de JavaScript, c'est que je ne vois pas comment on pourrait arriver à un système de sauvegarde. Passons.

Le projet célèbre dans ce genre, c'est Inform. Mais je n'aime pas la direction dans laquelle il est parti.

(lundi)

Le taquin de Mathieu : le retour du fils de la vengeance

Bon, le taquin proposé dans l'entrée précédente était assez infaisable. Celui qui suit a le même groupe (toujours le groupe M24 de Mathieu) mais il est sans doute beaucoup plus faisable (et en tout cas plus amusant à essayer) :

Je ne propose pas une configuration précise à atteindre : je propose plutôt de mélanger le taquin (ce qui se fait en choisissant le lien « point d'interrogation à l'envers ») et de chercher ensuite à le remettre en ordre. Cette fois-ci le taquin a la forme de 7+1 colonnes sur 3 lignes : on peut cycler les lignes avec les flèches vers le haut et le bas, cycler les 7 colonnes principales (celle qui est séparée des autres reste alors fixe) avec les flèches vers la gauche et la droite, ou enfin appliquer un flip de Mathieu qui échange huit paires de cases coloriées de la même façon (cinq de ces huit paires sont contiguës : 02–03, 08–09, 11–14, 12–15 et 13–16 ; et les trois cases 22, 23, 24 de la colonne spéciale sont échangées avec 07, 21 et 20 respectivement). Cette présentation n'est peut-être pas encore totalement satisfaisante, mais elle n'a pas l'air complètement folle et on peut vaguement la retenir et même développer quelques techniques de jeu comme l'utilisation judicieuse de la colonne séparée et des deux cases échangeant en diagonale. Avant de jouer avec le taquin tout entier, on peut se familiariser avec le sous-groupe d'ordre 21 engendré par les flèches (ça c'est vraiment très facile), avec le sous-groupe d'ordre 54 engendré par les flèches verticales et le flip (c'est encore plutôt facile), et enfin avec le sous-groupe d'ordre 21504 engendré par les flèches horizontales et le flip (il permet par exemple d'échanger exactement les deux lignes d'en bas sans toucher à celle d'en haut, ce qui n'était pas évident a priori : voyez-vous comment ?). Quant aux 244823040 états du puzzle complet, j'arrive pour ma part à placer en gros deux cases où je veux, parfois trois, mais pas plus (le groupe M24 de Mathieu, je l'ai déjà expliqué, permet de placer cinq cases où on veut).

J'ai aussi essayé de rajouter la possibilité de jouer au clavier (avec les flèches et la touche insertion pour appliquer le flip), mais c'était probablement une mauvaise idée vu que la possibilité de capturer les touches en JavaScript est complètement bizarre et dépend horriblement du navigateur et marche mal même sur un navigateur bien connu comme Firefox (il y a plein de problèmes de focus).

(samedi)

Le taquin de Mathieu

À force de méditer sur les groupes simples finis, j'ai imaginé le puzzle suivant, que j'appelle le Taquin de Mathieu :

Votre but est d'inverser complètement les nombres, c'est-à-dire de mettre le 24 là où est le 01 initialement et vice versa, le 23 à la place du 02, le 22 à la place du 03, etc. Pour ça, on dispose d'essentiellement deux opérations : l'une consiste à décaler cycliquement les douze colonnes du puzzle (vers la droite ou la gauche), l'autre — que j'appellerai le flip de Mathieu — réalise simultanément huit échanges entre deux cases (chaque paire étant coloriée d'une même couleur pour qu'on les voie facilement), les huit autres cases (marquées en gris) restant fixes. Les trois symboles immédiatement en-dessous du tableau sont cliquables, et réalisent ces opérations (et celui encore en-dessous remet le puzzle à son état de départ). Arriver à la situation inverse demandée est faisable — mais ce n'est pas très facile.

Le puzzle a 244823040 états possibles — c'est considérablement moins qu'un Rubik's cube, pourtant il me semble possible qu'il soit, d'une certaine manière, plus difficile à résoudre : en effet, pour résoudre le Rubik's cube on va chercher à trouver certaines combinaisons qui font des opérations faciles à comprendre, alors que dans le groupe de Mathieu, en un certain sens, ces opérations n'existent pas (aucune opération ne peut laisser plus de huit points fixes, par exemple). Peut-être que je me trompe. Si vous y arrivez sans l'aide d'un ordinateur, dites-le-moi !

En tout cas, il s'agit d'une illustration d'une des choses que j'affirmais dans ma précédente entrée : si on cherche des puzzles de ce genre qui ne permettent pas de réaliser toutes les permutations possibles des pièces, ou au moins toutes les permutations paires, alors il n'y a en gros que celui-ci et un analogue sur douze pièces qui offrent une certaine liberté dans le mouvement des pièces (vous pouvez placer cinq pièces quelconques aux endroits que vous voulez, et c'est le maximum).

Continue to older entries. / Continuer à lire les entrées plus anciennes.


Entries by month / Entrées par mois:

2017 Jan 2017 Feb 2017 Mar 2017 Apr 2017 May 2017 Jun 2017 Jul 2017
2016 Jan 2016 Feb 2016 Mar 2016 Apr 2016 May 2016 Jun 2016 Jul 2016 Aug 2016 Sep 2016 Oct 2016 Nov 2016 Dec 2016
2015 Jan 2015 Feb 2015 Mar 2015 Apr 2015 May 2015 Jun 2015 Jul 2015 Aug 2015 Sep 2015 Oct 2015 Nov 2015 Dec 2015
2014 Jan 2014 Feb 2014 Mar 2014 Apr 2014 May 2014 Jun 2014 Jul 2014 Aug 2014 Sep 2014 Oct 2014 Nov 2014 Dec 2014
2013 Jan 2013 Feb 2013 Mar 2013 Apr 2013 May 2013 Jun 2013 Jul 2013 Aug 2013 Sep 2013 Oct 2013 Nov 2013 Dec 2013
2012 Jan 2012 Feb 2012 Mar 2012 Apr 2012 May 2012 Jun 2012 Jul 2012 Aug 2012 Sep 2012 Oct 2012 Nov 2012 Dec 2012
2011 Jan 2011 Feb 2011 Mar 2011 Apr 2011 May 2011 Jun 2011 Jul 2011 Aug 2011 Sep 2011 Oct 2011 Nov 2011 Dec 2011
2010 Jan 2010 Feb 2010 Mar 2010 Apr 2010 May 2010 Jun 2010 Jul 2010 Aug 2010 Sep 2010 Oct 2010 Nov 2010 Dec 2010
2009 Jan 2009 Feb 2009 Mar 2009 Apr 2009 May 2009 Jun 2009 Jul 2009 Aug 2009 Sep 2009 Oct 2009 Nov 2009 Dec 2009
2008 Jan 2008 Feb 2008 Mar 2008 Apr 2008 May 2008 Jun 2008 Jul 2008 Aug 2008 Sep 2008 Oct 2008 Nov 2008 Dec 2008
2007 Jan 2007 Feb 2007 Mar 2007 Apr 2007 May 2007 Jun 2007 Jul 2007 Aug 2007 Sep 2007 Oct 2007 Nov 2007 Dec 2007
2006 Jan 2006 Feb 2006 Mar 2006 Apr 2006 May 2006 Jun 2006 Jul 2006 Aug 2006 Sep 2006 Oct 2006 Nov 2006 Dec 2006
2005 Jan 2005 Feb 2005 Mar 2005 Apr 2005 May 2005 Jun 2005 Jul 2005 Aug 2005 Sep 2005 Oct 2005 Nov 2005 Dec 2005
2004 Jan 2004 Feb 2004 Mar 2004 Apr 2004 May 2004 Jun 2004 Jul 2004 Aug 2004 Sep 2004 Oct 2004 Nov 2004 Dec 2004
2003 May 2003 Jun 2003 Jul 2003 Aug 2003 Sep 2003 Oct 2003 Nov 2003 Dec 2003