David Madore's WebLog

2007-08-28 (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:

(Transverse Mercator computations, spherical Earth:)

1. Start with latitude χ and longitude ϖ, and let ϖ₀ be the central meridian's longitude;
2. if we rotate the Earth to make the central meridian become the new (transverse) equator and the old equator become the new (transverse) reference meridian, then simple spheric trigonometry shows that the given point's transverse (i.e., new, i.e., rotated) longitude is ϖ^† = arctan[tan(χ)/cos(ϖ−ϖ₀)] and its transverse latitude is χ^† = arcsin[sin(ϖ−ϖ₀)·cos(χ)];
3. now if we apply the formula for Mercator projection to these transverse coordinates (namely: longitude in radians gives one coordinate and the other is given by log(tan(π/4+χ^†/2)) where χ^† is longitude), we get the transverse Mercator x = log(tan(π/4+χ^†/2)) = arctanh[sin(ϖ−ϖ₀)·cos(χ)] and y = ϖ^† = arctan[tan(χ)/cos(ϖ−ϖ₀)] (in radians).
4. It is then a simple matter of scaling (multiply x and y by the Earth's radius and by the 0.9996 scale factor) and translating (add 500000 meters to the easting coordinate and possibly 10000000 to the northing if in the southern hemisphere) to obtain UTM coordinates.

Here is a numerical example: consider the point with latitude χ=45° and longitude ϖ=0° and refer it to UTM zone 31's central meridian of ϖ₀=3°. We find x = −0.037024017523 and y = 0.786083865778. If we convert these in meters by taking the Earth's radius to be such that the meridian's length is the same as for the WGS84 model (10001965.7293m), and taking into accound the 0.9996 scale factor, then we get an easting coordinate of 264345.75067 and a northing of 5003346.90008. As we shall see below, these coordinates differ quite sensibly (by about 16km) from the correct values obtained for an ellipsoidal Earth.

For future reference, the complex number z = y − i·x will be called the complex latitude (this is my terminology: but it makes sense since when the point is on the central meridian ϖ=ϖ₀ then z is real and equals the latitude χ; so in the spherical Earth case, computing the transverse Mercator coordinates is basically just the same as computing this complex latitude).

Now in the case of a spheroidal Earth, things are much more complicated. For one thing, whereas longitude remains a simple concept (since we are assuming the ellipsoid in question has equal equatorial axes), the simple spherical latitude gives rise to half a dozen different concepts on a spheroid. The usual (geodetic) latitude, φ, is the angle which a line perpendicular to the ellipsoid at a given point forms with the equatorial plane. This is what the unqualified word latitude almost always means. But there are two other latitudes which are of importance:

• Conformal latitude χ is so defined that it is an increasing function of (geodetic) latitude which coincides with it at the equator (χ=φ=0°) and the poles (χ=φ=±90°), and such that mapping the ellipsoid to a sphere (of arbitrary radius) by taking a given point on the ellipsoid to the point on the sphere having the same longitude and latitude χ (the conformal latitude we are trying to define) gives a conformal map from the ellipsoid to the sphere.
  (To restate this in a less convoluted way: if you parametrize the spheroid by conformal latitude and longitude, you can pretend that it's a sphere when defining conformal projections.)
  A rather simple computation shows that χ is related to φ by dχ/cos(χ) = dφ/cos(φ) · (cos²(ε)/[cos²(φ) + cos²(ε)·sin²(φ)]) with ε the angular eccentricity (e=sin(ε)), and on integrating this gives the horrendous formula which is displayed in the Wikipedia article.
• Rectifying latitude μ is so defined that it is an increasing function of (geodetic) latitude which coincides with it at the equator (χ=φ=0°) and the poles (χ=φ=±90°) and which varies linearly with distance measured along the meridian. This is simple to define but it has no closed-form expression except involving incomplete elliptic integrals.

Obviously conformal latitude is of importance to us because we are trying to define a conformal map. If we simply apply the spherical-Earth formulæ with conformal latitude instead of (geodetic) latitude we get a conformal map but it is not the transverse Mercator we are looking for because coordinates along the central meridian will not be proportional to distance as they are supposed to be: for that, rectifying latitude needs to play a role. In fact, rectifying latitude is exactly what we need (up to proportionality and a trivial additive constant in the southern hemisphere) to get the vertical (northing) coordinate along the central meridian. So somehow we need to use both the conformal and the rectifying latitudes. How?

The trick is to consider the function M which takes a conformal latitude χ to the corresponding rectifying latitude μ=M(χ). That function is very difficult to write down explicitly, because it involves taking the reciprocal of a horrendous formula and then yet applying an (incomplete) elliptic integral. Nevertheless, it exists conceptually, and it is an analytic real function: so it has a locally unique holomorphic extension to a complex neighborhood of its real domain of definition; the reason we care is that holomorphic complex functions are conformal mappings. In practice, M can be approached by various power series techniques.

So the procedure to compute UTM coordinates on an elliptic Earth is this:

(Transverse Mercator computations, ellipsoidal Earth:)

1. Start with latitude φ and longitude ϖ: compute the conformal latitude χ corresponding to φ (there is a closed-form expression for this, so we are happy);
2. apply the spherical-Earth computations, using χ as latitude: let z = y − i·x be what we have previously called the complex latitude (here the complex conformal latitude, of course): at this point, we have defined a conformal map, but the central meridian is parametrized by conformal latitude, not rectifying latitude as we would like it to be;
3. compute z^♠ = M(z), where M is the (complex holomorphic extension of the) function taking a conformal latitude to the corresponding rectifying latitude: then z^♠ = y^♠ − i·x^♠ where x^♠ and y^♠ are the desired UTM coordinates
   {proof: since M is holomorphic, we have defined a conformal map, and since M takes a real conformal latitude to the corresponding rectifying latitude, it is what it should be on the real axis, but since real values suffice to identify an analytic function we are done}.

Here is a numerical example: consider the point with latitude φ=45° and longitude ϖ=0° and refer it to UTM zone 31's central meridian of ϖ₀=3°. We find a conformal latitude of χ=44°48′27.662601″. Now applying the spherical-Earth transverse Mercator formulæ, we find x = −0.037148195538 and y = 0.782727307059. Then M(y−i·x) = y^♠−i·x^♠ where x^♠ = −0.037148414843 and y^♠ = 0.783567347070. If we convert these in meters by taking into account the meridian's length for the WGS84 model (10001965.7293m), and taking into accound the 0.9996 scale factor, then we get an easting coordinate of 263553.97390 and a northing of 4987329.50469. This is the correct conversion: the point (45°N,0°) has UTM coordinates (263553.974,4987329.505) in zone 31 North.
Note that if we had naïvely applied the spherical-Earth transverse Mercator formulæ to the conformal latitude we would have found the incorrect value (263555.370,4981982.732), off by 5km; if we had applied the same formulæ to the rectifying latitude immediately, we would have found (263752.383,4987314.788), still off by 200m: so even for GPS-precision computations we can't simply forget about the complexity.

If we are aiming at a precision of slightly better than 1 metre, then the following numerical series expansions for M(z) (with the constants of WGS84) can be used: the first is around z=0 (to be used for latitudes less than 40°, say) and the second is around z=π/2 (to be used for latitudes above 40°):

• M(z) ≈ 1.00167851426z − 0.00112513485z³ + 0.00022996604z⁵ − 0.00002381665z⁷ + 1.76580·10⁻⁶z⁹ + O(z¹¹)
• M(z) ≈ π/2 + 0.99832757260(z-π/2) + 0.00110890291(z-π/2)³ − 0.00021697949(z-π/2)⁵ + 0.00001886787(z-π/2)⁷ − 6.6472·10⁻⁷(z-π/2)⁹ + O((z-π/2)¹¹)

I'm not sure how well these power series expansions compare with other classical approaches to computing UTM coordinates (e.g., pages 60–64 of this book).

Comments

2007-08-25 (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.

Commentaires

2007-08-23 (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.

Commentaires

2007-08-15 (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.)

Commentaires

2007-08-12 (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).

Commentaires

2007-08-10 (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.

Commentaires

2007-08-06 (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 M₂₄ 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 envendré 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 M₂₄ 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).

Commentaires

2007-08-04 (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).

Commentaires