🎛️ Une seule ligne qui balaie tout le carré
Augmente l'ordre : la courbe se subdivise et se rapproche de chaque point du carré. La couleur va du début (bleu) à la fin (rouge) du parcours.
À l'ordre n, la grille fait 2n × 2n cases et la courbe possède 4n points.
Côté de grille
16 × 16
Cases visitées
256
Dim fractale
2 (limite)
Ordre 4 : 256 cases reliées en une seule ligne continue, sans jamais se croiser.
🧩 1890-1891 : peut-on remplir un carré avec une ligne ?
À la fin du XIXe siècle, une question hante les mathématiciens : une courbe (un objet de dimension 1, image continue du segment [0, 1]) peut-elle passer par tous les points d'un carré (un objet de dimension 2) ? L'intuition crie « impossible » : une ligne est « fine », un carré est « plein ».
Pourtant, en 1890, Giuseppe Peano construit la première courbe continue et surjective de [0, 1] vers [0, 1]², c'est-à-dire une courbe qui touche bel et bien chaque point du carré. Un an plus tard, en 1891, David Hilbert en donne une version géométrique d'une élégance saisissante — la plus célèbre des courbes de remplissage du plan. C'est celle que l'animation ci-dessus construit.
🪜 La construction : on subdivise, encore et encore
L'idée est récursive. On part du carré, qu'on découpe en 4 quadrants. On relie les centres de ces 4 quadrants par un motif en forme de U (∪). C'est la courbe d'ordre 1.
Pour l'ordre 2, on subdivise chaque quadrant en 4 et on y place une copie du U — mais tournée et/ou retournée de façon à ce que les quatre copies se raccordent bout à bout en une seule ligne continue. On obtient 16 cases visitées. On recommence : à chaque passage à l'ordre supérieur, chaque case se subdivise en 4, et le nombre de cases est multiplié par 4.
Le compte exact
À l'ordre n, la grille fait 2n × 2n cases.
- Nombre de cases visitées : 2n × 2n = 4n
- Ordre 1 → 4 cases · Ordre 4 → 256 · Ordre 7 → 16 384
- La courbe parcourt ces 4n cases une seule fois chacune, sans saut.
Quand n → ∞, la courbe limite passe « arbitrairement près » de chaque point du carré : elle le remplit.
🧲 La propriété reine : la localité
Ce qui rend la courbe de Hilbert si utile, ce n'est pas seulement qu'elle remplisse le carré — c'est sa localité. Énoncée simplement :
Deux points proches le long de la courbe restent proches dans le plan. Si deux positions sur la ligne sont séparées d'une distance t le long du parcours, leur distance dans le carré reste de l'ordre de √t — elle ne « saute » jamais d'un bout à l'autre.
Regarde le dégradé de couleur dans l'animation : des cases de teintes voisines (donc proches sur la ligne) sont aussi voisines à l'écran. C'est exactement ce que d'autres courbes de remplissage (comme la courbe en Z) ne garantissent pas : elles, elles font parfois de grands sauts. La courbe de Hilbert, elle, ne saute jamais — chaque pas se fait vers une case adjacente.
🔢 La conversion (x, y) ⟷ distance d
Concrètement, la courbe définit deux fonctions réciproques sur une grille 2n × 2n :
- xy2d : à une case (x, y) on associe sa position d ∈ [0, 4n − 1] le long de la courbe.
- d2xy : à une position d on associe la case (x, y) correspondante.
L'algorithme (popularisé par l'article « Hilbert curve » de Wikipédia) parcourt les bits de coordonnées par niveaux successifs, en appliquant à chaque niveau une rotation et une éventuelle symétrie du sous-carré — exactement le « tournage » des copies du U décrit plus haut. C'est l'animation que tu vois : chaque point est le résultat de d2xy appliqué à d = 0, 1, 2, …, 4n − 1.
🌍 Pourquoi c'est partout aujourd'hui
La localité transforme la courbe de Hilbert en outil d'ingénierie de premier plan :
- Indexation spatiale de bases de données : pour stocker des points GPS ou géographiques, on les range selon leur indice de Hilbert. Les objets géographiquement proches se retrouvent proches sur le disque → les requêtes « tout ce qui est près d'ici » deviennent ultra-rapides. C'est le cœur des Geohash, S2 de Google et de nombreux index R-tree.
- Parcours et compression d'images : balayer les pixels selon la courbe de Hilbert plutôt que ligne par ligne regroupe les pixels voisins → meilleure cohérence locale, meilleure compression, moins d'artefacts en tramage (dithering).
- Mémoire cache et localité : ranger des matrices ou des textures selon Hilbert améliore les défauts de cache, car accéder à des voisins 2D devient accéder à des adresses proches en mémoire 1D.
- Visualisation de données massives : on cartographie un espace d'adresses IPv4 entier (4 milliards d'adresses) sur une image 2D via Hilbert ; les blocs d'adresses voisins forment des régions compactes et lisibles (célèbres cartes XKCD de l'Internet).
- Art génératif & design : sa beauté auto-similaire en fait un motif prisé en art algorithmique, gravure laser et impression 3D.
📐 Une courbe de dimension fractale 2
Topologiquement, la courbe de Hilbert reste une courbe : sa dimension topologique vaut 1. Mais sa dimension fractale (dimension de Hausdorff) vaut 2 — elle est si repliée qu'elle « occupe » toute l'aire du carré.
On le voit par auto-similarité : passer d'un ordre au suivant multiplie le détail par un facteur d'échelle 2 (chaque côté se divise en 2) tout en multipliant le nombre de copies par 4. La dimension fractale vaut alors log(4) ⁄ log(2) = 2. C'est la signature d'une vraie courbe de remplissage du plan, comme celle de Peano.
Le lien avec ton programme
- Suites & récursivité : la courbe d'ordre n+1 se construit à partir de 4 copies de l'ordre n. Pur raisonnement par récurrence.
- Transformations du plan (1BAC) : rotations et symétries sont au cœur de l'assemblage des 4 quadrants.
- Puissances : la croissance en 4n et 2n illustre concrètement les suites géométriques.
- Limites : la « courbe de remplissage » est la limite d'une suite de courbes — un objet limite qui n'a aucune des propriétés naïves de ses approximations.