Representation of Fractal Curves by Means of L Systems

by Manuel Alfonseca (Manuel.Alfonseca@ii.uam.es) and Alfonso Ortega

Abstract

Fractals can be represented by means of L-systems (Development Grammars), together with a graphic interpretation. Two families of graphic interpretations have been used: turtle graphics and vector graphics. This paper describes an APL2/PC system able to draw fractals represented by L-systems, with both graphic interpretations. A theorem has been proved on the equivalence conditions for both interpretations. Another point shown is the fact that supposed deficiencies in L-systems that have prompted proposals of extensions are really deficiencies in the graphic translation scheme.

Fractals

In 1890, the italian mathematician Giuseppe Peano described a certain curve, now known by his name, which displayed several monstruous properties, suchs as filling a surface (in the sense of passing through every point in it), and having a tangent at no point. Another monstruous line (the snowflake curve) was described in 1904 by Helge von Koch.

In 1919, H. Hausdorff introduced a new concept of dimension, different from the ordinary geometric dimension. According to his definition, later refined by Besicovitch, ordinary lines have a dimension of 1 and ordinary surfaces a dimension of 2, but the monstruous curves have a fractional dimension greater than 1. In fact, the Peano curve has a Hausdorff-Besicovich dimension of 2, while its value for the Koch snowflake is 1,2618595071429...

In 1975, Benoit B. Mandelbrot [Man 82] defined a fractal as an “object whose Hausdorff-Besicovitch dimension is greater than its geometric dimension”. Fractals have special properties, such as self-similarity (containing copies of themselves) and underivability at every point. They are appropriate for the description of natural shapes.

There are three main kinds of fractals:

L systems

In 1968, Aristid Lindenmayer [Lin 68] defined a new type of grammar (the parallel derivation grammar), which differs from the normal Chomsky grammars (sequential derivation grammars) because the grammar rules are applied simultaneously, rather than one at a time.

Parallel derivation grammars, also called L systems, can be classified in different ways:

These types may be combined: A D0L system is a deterministic context free system; a PD0L system is propagative, deterministic and context free; an EIL system is context sensitive with extensions; and so forth. A D0L system, for instance, is the three-fold (S, P, w), where S is an alphabet (a finite non-empty set of symbols); P is a set of production rules of the form A::=x, where AÎS is a symbol in the alphabet and x is a (possibly empty) word or string of symbols in the alphabet; and wÎS* is the starting word or axiom. Every symbol appears exactly once at the left of a production rule (this makes the system deterministic).

A D0L scheme is the two-fold (S, P), of an alphabet and a set of production rules, and represents the family of all the D0L systems sharing those two components and differing in the axiom.

An example of a D0L system is: 

( {F,+,-}, P, F++F++F )

where P is the following set of production rules: 

F ::= F-F++F-
+ ::= +
- ::= -

A derivation of a word in a D0L system is the new word obtained when each symbol in the first word is replaced by the right part of the production rule whose left part is that symbol. In the previous example, we can get the following derivation from the axiom: 

F++F++F • F-F++F-++F-F++F-++F-F++F-

The word obtained becomes the starting point of a new derivation, and so on.

L systems have been successfully applied in the simulation of biologic processes, such as plant growth, leave development, pigmentation of snail shells, etc. They are also very appropriate to represent fractal objects obtained by means of recursive transformations [Dem 85, Pru 86, Gie 91, Cul 91a, Cul 91b]. The initiator maps to the axiom of the L system, the generator to the production rules, and the recursive applications of the generator to the initiator correspond to the successive derivations of the axiom.

Something else is needed, however: a graphic interpretation that makes it possible to convert each word generated by the L system into a visible curve. The fractal object is the limit of the sequence of curves generated by the L system with the appropriate graphic interpretation.

It is very important to separate the L system from the graphic interpretation. Otherwise, a deficiency in the latter may be mistaken for one in the former. In the past, different extensions have been proposed for L systems, supposedly incapable of generating certain fractal objects, which a different graphic interpretation would make it possible to obtain.

Two different families of graphic interpretations of L systems have been used:

Turtle graphics

Created by Seymour Papert in 1980, the graphic is the spoor left by a moving invisible “turtle”, with a state defined by its position and the direction it is looking at. The state of the turtle may change as it moves a step forward, or as it rotates a given angle in the same position.

In the simplest turtle graphics interpretation, the alphabet of a D0L system consists of three symbols: 

S = {F, +, -}

The graphics interpretation of a word is as follows:

F
The turtle moves one step forward, in the direction it is looking at, leaving a visible trail. We will call F a drawing symbol.
+
The turtle rotates a positive angle a.
-
The turtle rotates a negative angle a.

Additional rules complicate the turtle graphics and make it possible to generate more complicated fractals. Between those rules, we will mention the following:

A given fractal may be represented by means of three components: an L system, a turtle graphic interpretation (made up of a combination of the preceding rules), and an angle step.

Vector graphics

In this family of interpretations, every symbol in the alphabet of the L system is associated to a vector in a rectangular cartesian system. A word (a string of symbols) is represented by the catenation of the vectors of the symbols that make the word.

In the simplest case, a fractal may be defined by two components: an L system, and a mathematical application V:SήR2 (the vector interpretation). We assume that all the vectors associated to the symbols in the alphabet generate visible movements. The graphic representation of each derivation of the L system is a set of straight connected segments.

This vector interpretation is capable of representing branching fractals, if for every symbol in the alphabet there is another associated to the opposite vector, which makes it possible to return to the start of the branch. However, a different vector interpretation is needed to build unconnected fractals. These can be covered by means of the following mathematical application: 

	V':SÏ•{0,1}×R2

In this case, the vector equivalent to a symbol has three elements instead of two: a visibility coefficient (0 or 1) is added, indicating that the vector displacement should be visible (a 1) or invisible (a 0).

An APL2 implementation

A system has been implemented in APL2/PC to experiment with fractals using different graphic interpretations. A fractal scheme is represented by a 3-element vector (additional elements in vectors are considered to be comments):

  1. A [T][P][D]0L scheme.
  2. A graphic representation.
  3. Additional information, depending on the graphic representation.

The 0L scheme is represented by the set of production rules (a matrix of two columns), from which the alphabet may be deduced (it is the set of all the symbols appearing in the rules). The rules have the following structure:

At this time, the graphic representation may be one of the following:

The additional information is the following:

  • For vector and pixel graphics: a matrix containing the definition of the vectors for all the symbols at the left of the rules in the 0L scheme.
  • For turtle graphics: the angle step and the sets of drawing symbols and moving symbols (the set of non-graphic symbols may be deduced from those). If the sets are not given, they are assumed to be {F} and {f}, respectively.

    The system includes a set of functions performing the following actions:

    The fractal schemes created may be kept in a file of APL objects using the AP211 auxiliary processor. The steps to the fractal curve are drawn using the AP207 VGA graphics auxiliary processor.

    Examples

    The examples given below have been designed by different authors and are common in the literature.

    An equivalence theorem

    Since we have two different graphic interpretations for L systems (turtle graphics and vectors) the question of the possible equivalence of both interpretations jumps to the mind. In other words: given a fractal represented by an L system with turtle graphics, can we represent the same fractal by another (usually different) L system with vector graphics? In fact, in the preceding examples, we have shown that the same fractal may be obtained by means of totally different L systems, each of which uses a different graphic interpretation.

    We have proved a theorem that can be considered as a first approach to the demonstration of full equivalence, which states:

    1. For every fractal curve represented by a D0L system with a vector graphics interpretation, there is another D0L system with a turtle graphics interpretation that represents the same fractal curve.
    2. For every fractal curve represented by a D0L system with a turtle graphics interpretation, there is another D0L system with a vector graphics interpretation that represents the same fractal curve, if the first representation satisfies the following restrictions:
      • There are two integers, n and k, such that n.a = 2.k.p, where a is the turtle incremental angle.
      • For every rule in the L system, the number of + symbols minus the number of - symbols is a multiple of n, where n is the constant defined in the preceding condition.
      • The alphabet for the L system includes the + and - signs, together with three sets of letters, corresponding to draw, move, and non-graphic symbols.

    In a computer, the first condition is always in effect, since the turtle incremental angle is a rational number (one cannot store irrationals in a computer). Therefore, in practice, the only restrictions are the last two. The theorem, such as stated, seems to imply that turtle graphic interpretations are more powerful than vector graphics.

    Our proof of the theorem is a constructive algorithm that, starting from an L system of one kind, generates an equivalent system of the other kind. In fact, the vector graphics L-system that generates the Koch snowflake curve shown in the examples, was obtained from the equivalent turtle graphics L-system, using our algorithm.

    Conclusion

    We have seen that D0L systems, given an appropriate graphic interpretation, are quite powerful to represent large families of fractal curves, even some that previous authors had assumed required nonstandard extensions.

    It is thus important to isolate the D0L system from its graphic interpretation, which can be very different and belong either to the turtle or the vector family.

    We have also proved a fractal equivalence theorem between L systems associated with a subset of turtle graphics and those associated with vector graphics.

    References

    [Cul 91a]
    K. Culik II, S. Dube, “Balancing Order and Chaos in Image Generation”. Proc. 18th Int. Coll. on Automata, Languages and Programming, ed. J.L. Albert, B. Monien, M.R. Artalejo, Springer-Verlag, Berlin, 1991, pp. 600-614.
    [Cul 91b]
    K. Culik II, S. Dube, “New Methods for Image Generation and Compression”, Proc. Conf. on Facts and New Trends in Computer Science, ed. H. Maurer, Springer-Verlag, Berlin, 1991, pp. 69-90.
    [Dem 85]
    S. Demko, L. Hodges, B. Naylor, “Construction of Fractal Objects with Iterated Function Systems”. Computer Graphics, Vol. 19:3. pp. 271-278, 1985.
    [Gie 91]
    E.G. Giessmann, “Generation of fractal curves by generalizations of Lindenmayer’s L-systems”. Proc. 1st IFIP Conf. on Fractals in the Fundamental and Applied Sciences, ed. H.O. Peitgen, J.M. Henriques, L.F. Penedo, North Holland, Amsterdam, 1991, pp.147-157.
    [Lin 68]
    A. Lindenmayer, “Mathematical models for cellular interactions in development” (two parts). J. Theor. Biol. 18, pp. 280-315, 1968.
    [Man 82]
    B.B. Mandelbrot, The Fractal Geometry of Nature. W.H.Freeman, San Francisco, 1982.
    [Pru 86]
    P. Prusinkiewicz, “Graphical Applications of L-Systems”, Proc. Graphics Interface 86 and Vision Interface 86, ed: M. Wein, E.M. Kidd, Vancouver, Canada, 1986, pp. 247-253.

    Manuel Alfonseca
    Professor at the Universidad Autonoma of Madrid

    Escuela de Ingenieria Informatica
    Universidad Autonoma de Madrid
    Ciudad Universitaria de Cantoblanco
    28049 Madrid SPAIN

    Telephone: (34) 1 397 4467; Fax: (34) 1 397 5277 Email: Manuel.Alfonseca@ii.uam.es

    and Alfonso Ortega, Ph.D. student at the Universidad Autonoma of Madrid.