L-System - Définition

Bibliographie

• « The Algorithmic beauty of plants » de Przemyslaw Prusinkiewicz et Aristid Lindenmayer, 1990
• « The book of L » de Przemyslaw Prusinkiewicz
• « Lindenmayer Systems, Fractals, and Plants » de Przemyslaw Prusinkiewicz et James Hanan, 1992

Context-Sensitive

Les deux systèmes précédents (des OL-Systems) ne peuvent pas simuler l'interaction de parties d'une plante car ils sont context-free, i.e. chaque partie se développe indépendamment des autres parties. Un L-System context-sensitive résout ce problème en prenant en compte ce qui précéde ou succède à une partie, c’est-à-dire un symbole. Un tel système est appelé IL-System ou encore (k, l)-System, le contexte de gauche est un "mot" de longueur k et celui de droite un "mot" de longueur l. Pour expliquer la manière dont se lisent les regles voici deux exemples :

Exemple 1 : signal acropète

Ce L-System simule la propagation d'un signal acropète dans une structure de branches qui ne se développe pas.

• Variable : V = {A, B}
• Constantes : S = {+, −, [, ], <}
• Axiome : w = B[+A]A[−A]A[+A]A
• Règles : (B < A → B)

A est une branche qui n'a pas encore reçu le signal, et B en est une qui l'a reçu. La règle se comprend ainsi : si un symbole A est précédé d'un symbole B, alors ce A devient un B à la génération suivante.

Voici la propagation du signal sur trois générations, sachant que les signes + et - seront ignorés dans la prise en compte des règles :

• n=0, B[+A]A[−A]A[+A]A
• n=1, B[+B]B[−A]A[+A]A
• n=2, B[+B]B[−B]B[+A]A
• n=3, B[+B]B[−B]B[+B]B

On constate que peu à peu, chaque branche est atteinte par le signal acropète qui permet aux fleurs les plus hautes de s'ouvrir. Remarquez bien qu'à chaque génération, deux nouvelles branches reçoivent le signal, en effet, puisque l'on sauvegarde la position, que l'on dessine A puis qu'on restitue la position et que l'on redessine un A, cela signifie que ces deux A ont la même base, donc la même branche précède les deux.

Exemple 2 : signal basipète

Ce L-System simule la propagation d'un signal basipète dans une structure de branches qui ne se développe pas.

• Variable : V = {A, B}
• Constantes : S = {+, −, [, ], <}
• Axiome : w = A[+A]A[−A]A[+A]B
• Règles : (A > B → B)

A est une branche qui n'a pas encore reçu le signal, et B en est une qui l'a reçu. La règle se comprend ainsi : si un symbole A est suivi d'un symbole B, alors ce A devient un B à la génération suivante.

Voici la propagation du signal sur trois générations, sachant que les signes + et - seront ignorés dans la prise en compte des règles :

• n=0, A[+A]A[−A]A[+A]B
• n=1, A[+A]A[−A]B[+B]B
• n=2, A[+A]B[−B]B[+B]B
• n=3, B[+B]B[−B]B[+B]B

On constate que peu à peu, chaque branche est atteinte par le signal basipète qui permet aux fleurs à l'inflorescence en ombrelle ou en capitule de fleurir de manière centrifuge.

Remarque : il est bien sûr possible d'écrire une règle dans le genre (B < A < B → B), ce qui signifie que si une branche A est entourée par des branches B alors elle deviendra une branche B à la prochaine génération. Il est aussi possible d'écrire plusieurs règles, pour plusieurs situations.