Page de maths de Thierry Monteil

contact :: thèmes de recherche :: papiers :: admin :: archive :: liens :: english


Blog -- Les mots du cercle

On peut approcher une courbe dessinée sur un quadrillage par les cases qu'elle rencontre (c'est par exemple le cas lorsqu'on veut tracer une courbe sur un écran d'ordinateur). La précision augmente lorsque le maillage du quadrillage diminue.

On peut coder cette représentation comme suit : lorsque la courbe croise le quadrillage selon une verticale, on écrit un "0", lorsqu'elle le croise selon une horizontale, on écrit un "1" (on néglige les cas ou la courbe rencontre un coin). On obtient ainsi un mot binaire, qui permet de dessiner la trace de la courbe sur le quadrillage de proche en proche.

Le cas des segments est particulièrement bien connu et on sait caractériser combinatoirement les mots binaires obtenus : ce sont exactement les mots dits équilibrés, c'est-à-dire les mots w tels que si u et v sont deux sous-mots de w de même longueur, alors le nombre de "1" apparaissant dans u et le nombre de "1" apparaissant dans v diffère d'au plus 1. On peut comprendre la notion d'équilibre comme la constance de la pente de la courbe (la pente correspond au rapport entre le nombre de "1" et le nombre de "0" apparaissant dans le mot considéré).

Par exemple le segment

SegmentGrille.png

est codé par le mot "001000100100", et sa pente vaut à peu près 1/3.

On se demande s'il est possible de caractériser les mots associés aux cercles. Par symétrie on se restreint au quart de cercle qui part du bas et monte vers la droite (si on voulait coder n'importe quelle courbe, il faudrait 4 lettres selon que l'on croise le quadrillage par la droite, la gauche, le haut ou le bas) : le mot associé commencera par plusieurs "0" et finira par plusieurs "1".

Déjà, un cercle est une courbe $C^1$ : elle se laisse approcher localement par des segments. On peut localiser la notion d'équilibre en disant qu'un mot est $l$-équilibré si tous ses facteurs de longueur inférieure à $l$ sont équilibrés. On peut dire qu'une courbe discrète est $C^1$ si pour toute longueur $l$, il existe $\varepsilon>0$ tel que le mot obtenu avec un quadrillage dont la maille est inférieure à $\varepsilon$ soit $l$-équilibré.

Pour un quadrillage donné, supposons que l'on fixe la longueur d'équilibre $l$. Cela impose une certaine rigidité à la courbe, et plus $l$ est grand, moins la courbe peut se plier (il faut y faire rentrer des segments de longueur $l$). Les arcs de cercles ont une propriété d'extrémalité : ce sont les courbes dont la courbure est constante. Si on impose une borne supérieure à la courbure, la courbe qui sera la plus courbée sera un arc de cercle. Un mot du quart de cercle associe à une rigidité maximale $l$ est un mot qui commence par $l$ "0" consécutifs (tangente horizontale) et va le plus vite possible vers $l$ "1" consécutifs (tangente verticale) tout en restant $l$-équilibré : dès qu'on peut mettre un "1" on le met.

Les mots du cercle seraient donc les mots obtenus par l'algorithme glouton suivant :

 w <- 00...0 (l fois)
 Tant que w ne finit pas par 11...1 (l fois):
 	si w.1 est l-équilibré
 		alors w <- w.1
 	sinon w <- w.0
 retourner w

Seulement il y'a un problème : le quadrillage est carré et un segment codé par un mot de longueur $l$ a une longueur comprise entre $l$ (lorsqu'on a $l$ "0" par exemple) et une longueur $\sqrt{\frac{l}{2}^2+\frac{l}{2}^2}$ (lorsqu'il y a $\frac{l}{2}$ "0" et $\frac{l}{2}$ "1"), de sorte que la rigidité imposée par la condition de $l$-équilibre est plus importante pour les tangentes proches de l'horizontale et de la verticale que pour des tangentes de pente 1 : notre arc de cercle sera légèrement bombé par rapport au cercle idéal.

Ainsi pour retrouver notre cercle euclidien, nous sommes devons normaliser la condition d'équilibre local :

Si on déroule l'algorithme précédent avec une rigiditée normalisée qui vaut 10, on obtient le mot "0000000000100001000100010010010010100101010010101010101011010101101011011011011101110111101111111111" ce qui donne (cliquer pour agrandir)

CercleDiscretCorrecMini.png

C'correc' (si on se limite à ce test).

N.B. ce qui a motivé initialement cette question n'est pas tant la construction de cercles discrets (thème classique de la géométrie discrète qui possède déjà de nombreux algorithmes), mais l'étude du codage d'un flot circulaire dans les surfaces de translation introduit par les physiciens Calogero, Grinevich et Santini, le cas étudié ici correspondant au cas du tore plat.


Page web propulsée par nilcms. Pour une validation stricte, débrouillez-vous.
[ Wiki :: WildSurfaces - BwataBaire - Substitutions - CellularAutomata - LMA - Ecool ]