Segments
Longueur
Dimension fractale
Position

Plus d'informations sur les courbes remplissantes

Explorateur de courbes remplissantes

Une ligne a une longueur mais pas d'aire, et un carré a une aire. Pourtant, une ligne peut être pliée de façon à passer par chaque partie d'un carré. Partez de quelques cases traversées par une seule ligne coudée ; découpez chaque case en cases plus petites et repliez la ligne pour qu'elle passe par toutes ; recommencez. Regardez un crayon tracer la courbe de Hilbert, la courbe de Peano et leurs cousines niveau par niveau, puis placez le crayon n'importe où sur la courbe pour voir quel point de la ligne tombe dans quelle case du carré. Une courbe remplissante est une seule ligne qui visite toutes les cases d'une grille ; chaque niveau découpe chaque case en cases plus petites et replie la ligne pour la faire passer par toutes. Appuyez sur Lancer pour voir le crayon tracer chaque niveau du début à la fin, ou sur Pas à pas pour tracer le niveau suivant. Choisissez la courbe de Hilbert, de Moore ou de Peano, l'ordre Z, le flowsnake de Gosper ou la pointe de flèche de Sierpiński. Cliquez ou faites glisser sur l'image, sur la ligne colorée située en dessous ou sur le curseur Crayon pour déplacer le crayon le long de la courbe : la tuile Position indique le numéro du pas et la case où il se trouve. Les couleurs se suivent le long de la ligne, si bien que des cases de couleurs proches correspondent à des pas proches.

Comment ça marche

  1. Appuyez sur Lancer pour voir le crayon tracer chaque niveau du début à la fin, ou sur Pas à pas pour tracer le niveau suivant ; faites glisser Niveau pour passer directement à n'importe quel niveau.
  2. Choisissez la courbe de Hilbert, de Moore ou de Peano, l'ordre Z, la courbe de Gosper ou la pointe de flèche de Sierpiński.
  3. Cliquez ou faites glisser sur l'image, sur la ligne colorée située en dessous ou sur le curseur Crayon pour déplacer le crayon le long de la courbe.
  4. Lisez dans les tuiles le nombre de segments, la longueur, la dimension fractale et la position du crayon.

Une ligne qui visite chaque case

La courbe de Hilbert de niveau n parcourt une grille de 2ⁿ sur 2ⁿ cases, en visitant chaque case une seule fois et en passant toujours à une case voisine. Le niveau 1 est un seul coude à travers 4 cases. Chaque niveau suivant remplace chaque case par 4 cases plus petites et chaque pas par une petite copie du coude, tournée de façon que les extrémités se raccordent. La ligne qui traverse 4ⁿ cases compte 4ⁿ − 1 pas et sa longueur vaut 2ⁿ − 2⁻ⁿ fois le côté du carré : elle double, à peu de chose près, à chaque niveau, alors que l'image garde la même taille. La courbe de Peano fait de même avec 9 cases par case, en décrivant des lacets en S, et la courbe de Moore réunit quatre courbes de Hilbert en une boucle fermée.

D'une droite numérique à un carré

La ligne colorée sous l'image est la droite numérique de 0 à 1, et la courbe est cette droite repliée dans le carré. Déplacez le crayon et la tuile Position vous indique sur quel pas il se trouve et de quelle case il s'agit. Sur la courbe de Hilbert, les pas de numéros proches sont toujours dans des cases proches, ce que montrent les couleurs : chaque couleur reste groupée en une seule tache. C'est pourquoi la courbe de Hilbert sert à ranger des cartes, des images et d'autres données à deux dimensions dans une mémoire à une dimension. L'ordre Z est plus facile à calculer, car les coordonnées de la case sont simplement les bits du numéro du pas distribués à tour de rôle, mais il fait des sauts : près de la moitié de ses pas ne mènent pas à une case voisine.

Des courbes qui remplissent d'autres formes

La courbe de Gosper, le flowsnake, remplace chaque segment par sept sur une grille de triangles et remplit une forme au littoral fractal, l'île de Gosper. Sa dimension est 2, comme celle des courbes qui remplissent un carré : log 7 / log √7. La courbe en pointe de flèche de Sierpiński remplace chaque segment par trois, chacun deux fois plus court. Elle ne remplit jamais une aire : elle tend vers le triangle de Sierpiński, et sa dimension est log 3 / log 2 ≈ 1,585, entre celle d'une ligne et celle d'une surface.

Questions fréquemment posées

Comment une ligne peut-elle remplir un carré ?

Aucun niveau n'y parvient à lui seul : chaque niveau est une ligne ordinaire, avec une longueur et sans aire. Mais les niveaux se stabilisent. Le point situé à une fraction donnée du parcours de la ligne bouge de moins en moins d'un niveau à l'autre, et la limite de tous les niveaux est une courbe continue qui passe par tous les points du carré. Giuseppe Peano a démontré en 1890 qu'une telle courbe existe, à la surprise des mathématiciens de son temps.

La courbe passe-t-elle par chaque point exactement une fois ?

Chaque niveau visite chaque case de sa grille exactement une fois. La courbe limite, en revanche, doit passer par certains points du carré plus d'une fois : en 1879, Eugen Netto a démontré qu'on ne peut pas appliquer une ligne sur un carré de façon à la fois continue et injective. La courbe de Hilbert passe par certains points deux, trois ou quatre fois.

Quelle est la différence entre la courbe de Hilbert et l'ordre Z ?

Tous deux rangent les cases d'une grille en une seule longue file. La courbe de Hilbert passe toujours à une case voisine, si bien que des cases proches dans la file sont proches dans la grille. L'ordre Z se calcule plus vite, en entrelaçant les bits des deux coordonnées, mais près de la moitié de ses pas sont des sauts, dont certains traversent tout le carré. La tuile Longueur compte les sauts.

À quoi servent les courbes remplissantes ?

À ranger des données à deux dimensions dans un ordre à une dimension qui garde les voisins ensemble. Les bases de données et les services de cartographie indexent les lieux le long d'une courbe de Hilbert ou selon l'ordre Z, les logiciels d'image parcourent les pixels le long d'une courbe de Hilbert pour répartir les erreurs d'arrondi, et les cartes de l'espace d'adressage d'Internet l'utilisent pour garder côte à côte les adresses apparentées.

Pourquoi la pointe de flèche de Sierpiński ne remplit-elle pas le carré ?

Parce qu'elle ne découpe chaque segment qu'en trois morceaux deux fois plus courts ; pour remplir une aire, il lui en faudrait quatre. La courbe tend vers le triangle de Sierpiński, une forme sans aire et de dimension log 3 / log 2 ≈ 1,585.

Prêt à l'essayer ?

Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.

Aller à l'éditeur