domingo, 14 de diciembre de 2014

L-systems

Fractal plant for n = 6 (Wikipedia: ejemplo de sistema-L)


Los Sistemas-L o sistemas de Lindenmayer fueron originalmente desarrollados por el biólogo Aristid Lindenmayer en 1960 con la idea de describir las estructuras ramificadas de las plantas, células y otras formas de la naturaleza. Lindenmayer, en colaboración con Przemyslaw Prusinkiewicz1, consiguieron obtener un conjunto considerable de estructuras originales de vida artificial. A grandes rasgos, estos sistemas consisten en la generación repetida de una gramática semi-Thue basada en la jerarquía de Chomsky; aunque la gran diferencia con ésta última estriba en que todas las variables son reemplazadas en cada paso, no solo una. En este  sentido, una gramática L-system consiste en el reemplazamiento de reglas de producción sobre un conjunto de caracteres (alfabeto), comenzando por un símbolo inicial o axioma. Dichas reglas, aplicadas simultáneamente sobre un alfabeto, generan palabras complejas después de unas cuantas iteraciones. En épocas pasadas, estas frases complejas podían dibujarse en pantalla por medio del lenguaje LOGO, en el que una tortuga que obedecía a comandos gráficos trazaba líneas sobre un dispositivo de vídeo.

Formalmente una gramática de Lindenmayer se puede definir como:

  • Σ es un alfabeto finito
  • A ∈ Σ+ (axioma)
  • R = {(a, b, c) → d | a, c ∈ Σ*, b ∈ Σ, d ⊂ Σ*} 
  • Para cualquier (a, b, c) → d ∈ R, if |d| > 1 el sistema-L es estocastico, y si un a≠λ or c≠λ, el sistema-L es contextual
De aquí se deduce la tupla G = {Σ, A, R}, donde:
  • Σ es un alfabeto de caracteres finito
  • A es el axioma
  • R conjunto de reglas de producción
Un ejemplo de gramática L-system podría ser el del crecimiento de las algas:

Variables : A B
Constantes : ninguna
Axioma : A
Reglas : (A → AB), (B → A)
la cual produce las siguientes frases:
n=0 : A → AB
n=1 : AB → ABA
n=2 : ABA → ABAAB
n=3 : ABAAB → ABAABABA

Otra posibilidad es usar producciones estocásticas, donde la selección de una regla de producción dependiendo de ciertas probabilidades y variaciones estocásticas generan una gran irregularidad sobre la forma obtenida. Esta característica se puede conseguir gracias a las funciones random asociadas con números aleatorios y disponibles en muchas librerías matemáticas de programación.

Un ejemplo de esta gramática estocástica podría ser la siguiente:

\[ F =\begin{cases}
 \xrightarrow{0.95}  & F [+F] [<F] F [-F] F\\
\xrightarrow{0.05} &   \lambda
\end{cases} \]

donde se interpreta que:
  • F es dibujar hacia delante
  • f salto hacia delante sin dibujar
  • + giro a la izquierda de α°
  •  -  giro a la derecha en el mismo ángulo
  • < indica el giro de 30° exactos 
  • [ comienzo de ramificación
  • ] fin de ramificación
  • {0.95}  llamada de la regla el 95% de las veces
  • {0.05} llamada de la regla el 5% de las veces para podar (λ)
Una situación típica acaecida en la generación de sistemas-L surge cuando es necesario incluir información sensible al contexto para generar reglas de producción, debido principalmente a la detección de colisiones y compartición del espacio físico sobre el que dibujar. En concreto, para resolver estas situaciones se recurre a estructuras de datos que mantienen información relativa al control de producciones.

Un ejemplo clásico de sistema-L, muy acorde con esta época del año ;-), es el famoso copo de nieve de Koch:

Construcción del Copo de Koch
Copo de nieve de Koch (Wikipedia)



Que como sistema Lindenmayer tiene la siguiente estructura:

Alfabeto: F
Constantes: +, -
Axioma: F++F++F
Reglas de producción: F → F−F++F−F

Con el fin de ilustrar con más claridad las ideas aquí expuestas, proponemos la aplicación en línea http://www.kevs3d.co.uk/dev/lsystems/ para que usted mismo pueda ejercitarse en el diseño de estas bellas estructuras.


(1) P. Prusinkiewicz and A. Lindenmayer (1990) The Algorithmic Beauty of Plants, Springer-Verlag, New York.

Referencias:
  • http://www.jflap.org/tutorial/lsystem/index.html
  • http://en.wikipedia.org/wiki/L-system
  • Huw Jones (2001). Computer Graphics through key mathematics. Springer-Verlag.