Il devient de plus en plus difficile de choisir un carrelage original pour sa salle de bains.
Depuis le XVème siècle, 17 types de pavages réguliers différents sont utilisés dans les décorations de l'Alhambra. En 1891, le mathématicien russe Evgraf Fedorov démontre que le nombre de pavages réguliers distincts vaut … 17 [1]. Et ce n’est qu’entre 1968 et 1984 qu’on parvient à classifier toutes les formes de pavés possibles en 19 catégories [2]. Depuis, les carreleurs ne peuvent se distinguer que par des motifs et des couleurs, plus par la géométrie.
En 1974, le pavage de Penrose crée un choc : il est possible de recouvrir le plan avec des pavés de deux formes différentes arrangés selon des règles rigoureuses, mais ne générant pas de motif périodique. En 1994, Radin et Conway en proposent un autre, le « Pinwheel tiling ». Voilà pour le XXème siècle.
En 2011, c’est John Shier, un « artiste algorithmique » qui vient d’ouvrir tout grand la porte à une infinité de nouveaux pavages. Sa méthode permettent de couvrir le plan avec des pavés de presque n’importe quelles formes, mais de surface décroissantes [3,4]. Le principe semble tout simple : on place le plus grand pavé au hasard, puis le suivant en taille au hasard dans une surface libre et ainsi de suite.
Le problème est que si on réduit la taille des pavés trop vite on ne recouvre pas tout le plan, et si on réduit trop lentement, on risque d’être « coincé » à ne pas pouvoir placer un pavé. L’astuce consiste à attribuer au i-ème pavé une surface de A0/ic. Dans ce cas, la surface totale vaut :
$$A_{total}=A_{0}\sum_{i=0}^{\infty}i^{-c}$$
On reconnait en passant la fonction zêta de Riemann, qui converge pour c>1. Grâce à cette formule, une fois choisi un c, la formule permet de calculer la surface A0 qui garantit qu’il ne restera plus un seul espace libre après avoir placé une infinité de pavés. En pratique on obtient d’excellent remplissages avec quelques milliers de pavés, un peu de patience et un bon programme. Paul Bourke décrit tout ceci en détail sur une page [5] agrémentée de magnifiques exemples:
Il a même étendu la méthode à la 3D :
Pour ma part, j’ai réalisé la petite application ci-dessous en Processing (disponible aussi sur OpenProcessing avec son code source) pour expérimenter un peu cet algorithme que je trouve spectaculaire:
[processing sketch= »RandomTiling »]
En pressant sur les touches 0,1,3,4,5,6 vous pouvez changer la forme des pavés à la volée, et la touche espace relance un pavage. Contrairement à Shier et Bourke, je ne pave pas un tore mais un rectangle, en prenant garde à ce que les pavés ne soient pas « coupés » par les bords. En plus je me suis amusé à implémenter les pavés en forme d’étoiles, en prévision d’une carte de Noël. Mignon, n’est-ce pas ? Bon, il reste pas mal de noir car la détection d’intersection entre étoiles est très lente, il faudrait améliorer ça.
ajout du 8/10/11 : j’ai présenté hier un Tutoriel Processing décrivant la conception de ce programme.
edit du 20/9/13 : l’applet utilise maintenant Processing.js : drgoulu.com n’a plus besoin de Java !
Il y a encore (ou déjà…) 2 bugs connus, si ça vous dit de vous y mettre :
- le pavage bloque parfois, surtout avec les triangles ou étoiles, il faut que j’ajoute un moyen d’ajuster la constante c…
- des intersections entre cercles et polygones subsistent. Normal, j’ai eu la flemme d’implanter ça.
Une autre amélioration intéressante serait de remplir l’intérieur des pavés avec d’autres pavés…
Références:
- Thérèse Eveilleau « Les 17 types de pavage » avec animations flash
- Xavier Hubaut « Pavages du plan«
- John Shier « Filling Space with Random Fractal Non-Overlapping Simple Shapes« , Hyperseeing, summer 2011 issue, pp. 131-140, published by ISAMA (International Society of the Arts, Mathematics, and Architecture).
- John Shier « Statistical Geometry »
- Paul Bourke « Random space filling tiling of the plane« , July 2011
14 commentaires sur “Pavages aléatoires”
Une nouvelle construction avec des pavés pentagonaux : https://plus.maths.org/content/five-fits
John Shier m’a indiqué par e-mail cet article décrivant en détail l’algorithme : Shier, J., & Bourke, P. (2013). An Algorithm for Random Fractal Filling of Space. Computer Graphics Forum, 32(8), 89–97. doi:10.1111/cgf.12163
J’avais fait ce petit truc qui a des connexions avec ce qui précède 🙂 (Processing, Sketchup et Moi3D)
size(1024,512); // taille de votre image en pixel
PImage pilou = loadImage(« your image.png »); // n’importe quelle image PNG avec un fond transparent
int t = 8; // hauteur minimum en pixel
for (int k = 8; k < 513; k = k + t) { // incrément de la largeur et hauteur
for (int y = 0; y < 513; y = y + k) { // position x,y de chaque nouvelle image sur l'écran
for (int x = 0; x < 1023; x = x + k*2) // dessine une image réduite
{image(pilou,x,y,k*2,k) ; // à la position x,y sur l'écran
} // fin de boucle x
} // fin de boucle y
filter(INVERT); // Inverse les couleurs à chaque dessin d'écran: facultatif
t=t*2; // incrémente la hauteur de l'image,
} // peut être n'importe quoi: Da Silva t= t+8
image(pilou,0,0); // dessine l'image originale :
J’avais fait ce petit truc qui a des connexions avec ce qui précède 🙂 (Processing, Sketchup et Moi3D)
size(1024,512); // taille de votre image en pixel
PImage pilou = loadImage(« your image.png »); // n’importe quelle image PNG 1024*512 avec un fond transparent
int t = 8; // hauteur minimum en pixel
for (int k = 8; k < 513; k = k + t) { // incrément de la largeur et hauteur
for (int y = 0; y < 513; y = y + k) { // position x,y de chaque nouvelle image sur l'écran
for (int x = 0; x < 1023; x = x + k*2) // dessine une image réduite
{image(pilou,x,y,k*2,k) ; // à la position x,y sur l'écran
} // fin de boucle x
} // fin de boucle y
filter(INVERT); // Inverse les couleurs à chaque dessin d'écran: facultatif
t=t*2; // incrémente la hauteur de l'image,
} // peut être n'importe quoi: Da Silva t= t+8
image(pilou,0,0); // dessine l'image originale :
Nice article, sorry but while I can read French my written French is rubbish.
Un billet sur les pavages quelques jours avant le prix Nobel sur les quasi-cristaux, c’est fort !
argh je m’en voudrai longtemps de ne pas avoir fait le lien entre pavages et cristallo dans l’article. Trop paresseux…
L’article d’Enro sur ce sujet est très bien. Je ne savais pas qu’il y avait des pavages apériodiques à l’Alhambra (une raison de plus d’y aller).
Je pense qu’on peut s’attendre a de très belles visualisations de quasicristaux en 3D bientôt…
Si vous avez des soucis avec Processing, je vous conseille le forum Codelab: ils ont une section processing et pleins de spécialistes qui donnent de bons conseils !
Comment ça choisir A_0 ? Je ne comprends pas, pour c > 0 et tout A_0 > 0 le résultat est fini ?!
Je veux dire c > 1…
Ah j’ai compris, on ne recouvre pas le plan mais un pavé… Hum, c’est évident qu’il y a toujours de la place pour le i+1 ème motif ?
Après lecture des références, je constate que c’est une constatation empirique… hum… joli…
(j’ai groupé les 4 commentaires de H envoyés n quelques minutes en un seul…)
Oui, pour c>1 la somme est toujours finie, donc on peut déterminer le A_0 qui permet de remplir la surface A_total. Effectivement, on remplit une surface finie, et pas tout le plan.
La démonstration du fait qu’on trouve toujours de la place pour le i+1ème pavé doit être assez « sport » si elle existe…
Je viens d’ajouter une ligne de debug intéressante à mon code : le rapport entre la surface restante et la surface du pavé augmente très vite. Dans le cas « par défaut » de l’applet, le premier disque occupe 1/7ème de la surface, mais le 1000ème ne prend qu’environ 1/3000 ème de la surface restante. C’est probablement ce qui explique que l’heuristique marche : à l’échelle du pavé, la place disponible est très grande.
Merci d’avoir groupé… oui c’est sans doute assez difficile de caractériser les coupes (A_0,c) pour lesquels ça peut bloquer ou non, mais qui sait ? Peut-être un argument tout simple attend-il au tournant ?
Déjà est-ce qu’on peut montrer que si l’ensemble des tirages qui peuvent conduire à un blocage est non vide, alors il est de mesure > 0 ? Ça me semble assez intuitif, ça.
Merci pour ce billet.
Justement j’ai entendu, par hasard, parler de Processing la semaine dernière. Ton billet me donne un exemple de résultat.
Le code source est assez court, je tenterai d’y jeter un œil pour comprendre comment ça fonctionne.
PS : Les « pavages » en 3D sont très jolis.
Tiens! je me demande si les apprentis paveurs de la Ville apprennent ces utiles fonctions. A mon avis, je risque d’en prendre un sur la tête (de pavé, donc), mais je vais leur demander ;-).
Y a-t-il un interface entre Processing et Python?