Determination of fractal dimensions from equivalent L systems

This paper revises a few existing methods for computing fractal dimensions, underlines their dependency on the graphical properties of the curves, and proposes and discusses a new method, based on the representation of fractals by means of Lindenmayer systems, that makes use of the structure of L systems to compute the fractal dimension. The method is implemented in Prolog, and its limitations and usefulness are discussed.

The scale reduction at every derivation is such that, starting with an axiom equal to the left side of the only rule, the distance between the origin and the end of the graphical representation of the strings is always the same. The example given below illustrates the use of the algorithm.

The PD0L scheme

F : : = F + F – – F + F + : : = + – : : = –

(9)

with axiom F – – F – – F and a turtle graphic interpretation, where {F} is a draw symbol and the step angle is 60°, represents the fractal whose fifth derivation appears in Figure 1 (Von Koch snowflake curve).

Figure 1

The only string to be considered is

F + F – – F + F.

(10)

This string describes the fractal generator. The number of steps along the walk (N) is the number of draw symbols in the string, 4 in this case. The distance d between the extreme points of the generator, computable from the string by applying to it the turtle interpretation, is 3. Therefore, the dimension is

D =  log(4)  = 1.2618595071429 . . . , log(3)

(11)

in accord with the results obtained by other methods, specified by Mandelbrot in Reference [1], p. 42.

Problems in the previous definition

•	The distance d in the denominator may be zero. Computed by our formula, D becomes zero. An example is the PD0L scheme
	F : : = F + F + F + F + + : : = + – : : = – (12)
	with a step angle of 90°. We exclude these cases because they do not usually give rise to fractal curves, but to the same figure indefinitely repeated (in the example, a square).
•	The distance d in the denominator may be 1. Computed by our formula, D becomes infinite. An example is the PD0L scheme
	F : : = F + F + + F + + F + + : : = + – : : = – (13)
	with a step angle of 60°. We also exclude these cases because in every step of derivation the curve expands and is not limited to a finite space; therefore, it is not a fractal in the strict sense.
•	The length N of the visible walk may not be equal to the number of draw symbols in the generator string. This may happen in two ways: °   The turtle graphic associated with the string passes more than once along a set of points with a nonzero measure, as in the PD0L scheme F : : = F + FF + + + F + + F – FF + + + F + + F – – F + : : = + – : : = – (14) with a step angle of 45° and axiom F+ +F+ +F+ +F. Figure 2 represents the generator of the corresponding fractal curve and its third derivation. Our algorithm has been refined to take this case into account in such a way that the appropriate value of N is computed, where such sets of points are counted only once. This means that the value of N may be noninteger, as in this case, where its value is not 10 (the number of F in the string), but 9.4142 … (8 plus the square root of 2). °   The turtle graphic associated with a derivation of the string passes more than once along a set of points with a nonzero measure, as in the PD0L scheme F: : = F + FF – F – FF + F + ::= + – : : = – (15) with a step angle of 90° and axiom F+F+F+F. Figure 3 represents the generator of the corresponding fractal curve and its fourth derivation. In this case, we replace the definition of fractal dimension we are using with D = lim  log(N)  , log(d) (16) where the limit is taken on the string of derivations from axiom F. Our algorithm computes this case by taking a certain number of derivations until the quotient converges. The resulting dimension is approximately equal to 1.6, rather than 1.77, as computed from the string.

Figure 2 Figure 3

Fractal curves represented by several equivalent symbols
Our algorithm is also immediately applicable to those L systems with more than one rule, where all of the right parts of the rules give rise to identical fractal dimensions. Let us examine a couple of examples:

•	The PD0L scheme F : : = – G + F + G – G : : = + F – G – F + + : : = + – : : = – (17) with axiom F and a turtle graphic interpretation, where {F, G} are draw symbols and the step angle is 60°, represents the fractal whose first five derivations appear in Figure 4. In this example, there are two strings to be considered: – G + F + G – + F – G – F +. (18) Applying our algorithm to each of them, we obtain the same estimation of the fractal dimension, 1.58496 … . Therefore, the fractal dimension of the corresponding curve must be the same, in accord with Mandelbrot's results [1].
•	The PD0L scheme F : : = + A – – A + A : : = – F + + F – + : : = + – : : = – (19) with axiom A – – A – – A – – A – – A – – A and a turtle graphic interpretation, where A is a nongraphic symbol, F is a draw symbol, and the step angle is 30°, provides another way to represent the Von Koch snowflake curve in Figure 1, where only one of every two derivations generates a visible curve. In this example, there are two strings to be considered: + A – – A + – F + + F – . (20) Applying our algorithm to each of them, we obtain the same estimation of the fractal dimension, 1.261859 … . Therefore, the fractal dimension of the corresponding curve is again the same. Alternatively, taking advantage of the fact that one of every two steps is invisible, we could consider the result of the following two-step derivation: F + A – – A + + – F + + F – – – – F + + F – +. (21) The string + – F + + F – – – – F + + F – + can also be considered a description of the fractal generator. Applying our algorithm to it, we again obtain a result of 1.261859 … .
•	The PD0L scheme P : : = PFU – F + Q + F – PF Q : : = Q + F – PFR + + F – – Q + F – R : : = R + + F – – Q + F – S + + + F – – – R + + F – – S : : = S + + + F – – – R + + F – – T – – F + + S + + + F – – – T : : = T – – F + + S + + + F – – – U – F + T – – F + + U : : = U – F + T – – F + + PFU – F + F : : = + : : = + – : : = – (22) with axiom P+ +P+ +P and a turtle graphic interpretation, where F is a graphic symbol, {P, Q, R, S, T, U} are nongraphic symbols, is the empty string, and the step angle is 60°, provides another way to represent the Von Koch snowflake curve in Figure 1. In this example, the dimension estimated by our algorithm gives the correct dimension for every symbol after the first iteration: 1.261859 … . In this example there are several apparently different rules. In fact, the rules are very dissimilar. After carefully studying them one could state the following: °   The number of symbols on the right side is always equal to 8. °   Four of the eight symbols are graphics. Therefore, the rules are structurally similar.

Figure 4

The algorithm
The crucial part of the algorithm is the computation of N, the length of the visible walk followed by the fractal generator or the sequence of derived strings, where repeated walks are eliminated. To do this, we need to derive an exact unambiguous representation of all of the points in the walk, together with information about the visibility of each step. A typical Cartesian x – y representation is not appropriate, for we are dealing with irrational numbers for most turtle angle steps, and the precision of real numbers in a computer is finite, which means that only a subset of rational numbers can be represented. Our representation takes into account the fact that the turtle approach ensures that any point of interest in the plane can be reached by a finite sequence of unitary vectors taken from a set of n, where = (2k/n) is the turtle angle step. Thus, taking into account that vector addition is commutative, we can represent each point by a set of n integer numbers stating how many vectors of each kind are needed to reach that point from the origin by following the turtle movements, without specifying the order of the vectors.

To make the representation unique for every point, we must make sure that the walk from the origin to the point is minimal. We do this by performing the following additional computations on the set of integers that represent a point:

• For every n, we eliminate all n-sided regular polygons, represented by sequences of all ones.
• For odd n, we eliminate all smaller regular polygons with a number of sides that is a prime submultiple of n. They are easily recognized as sequences of ones and zeros.
• For even n (where, for every vector in the set, its opposite vector is in the set), we have to be subtler: A part of any regular polygon with a number of sides an odd prime submultiple of n, longer than half the polygon, can be replaced by a smaller set of vectors going around the remainder of the polygon in the opposite direction. This can also be done easily by looking at the sequences of ones and zeros in the point representation.

For example, let be 60°, which means that n = 6. The turtle walk defined by

F + + F – – F + + F + + F + + F

can be defined by the set of integers: (3, 0, 2, 0, 1, 0), which means that we must make three steps with angle 0°, two with angle 120°, and one with angle 240°. This can be obtained immediately from the string by counting walks according to directions. Since n is even, we have to reduce polygons. The sequence (1, 0, 1, 0, 1, 0), which is included in (3, 0, 2, 0, 1, 0), represents a triangle (a polygon of three sides, where 3 is an odd prime submultiple of n). The sequence can be replaced by (0, 0, 0, 0, 0, 0), the remainder polygon in the opposite direction. The point representation thus becomes (2, 0, 1, 0, 0, 0). Next, we observe that the sequence (1, 0, 1, 0, 0, 0), contained in the latter, represents two sides of a triangle, which can be replaced by the vector corresponding to the third side in the opposite direction, (0, 1, 0, 0, 0, 0). Thus, the point reached by the above turtle string can be reduced to (1, 1, 0, 0, 0, 0). Figure 5 shows the original string walk, plus those corresponding to the three subsequent representations of the endpoint. The last one is the minimum, which we take as the canonical representation of the endpoint.

Figure 5

It can easily be proved that this algorithm correctly computes the canonical integer representation of the endpoint of any turtle string. Thus, we can unambiguously locate and eliminate repeated walks (even parts of turtle movements, as in the example in Figure 3), simply by comparing any visible turtle step with all of the previous ones and replacing canonical representations of endpoints. A simple algorithm can do this with a complexity of O(N²).

Prolog implementation of the algorithm
The Prolog predicate in the listing below computes the fractal dimension of the fractal curve defined by an L system. The predicate receives the following arguments:

• Left: the left symbol of a rule in the L system.
• Draw: the set of draw symbols.
• Move: the set of move symbols.
• Nograph: the set of nongraphic symbols.
• Angle: the angle step of the turtle.
• InitialPoint: the coordinates of the initial point of the curve, usually (0, 0).
• N: the number of derivations.

The predicate returns the result of the computation in variable FractalDimension.

A set of facts describing the rules of the PD0L scheme must be stated before invoking the predicate fractal_dimension. These facts can be read from a file:

fractal_dimension(Left, Draw, Move,
                  Nograph, Angle, 
                  InitialPoint, N, 
                  FractalDimension) :–

% FIRST THE NTH DERIVATION IS OBTAINED 
% FROM AXIOM ACCORDING TO THE PRODUCTION 
% RULES. 
  get_nth_derivation_from_axiom(Left, N, String), 

% THEN, THE GRAPHIC INTERPRETATION OF THE 
% RESULTING STRING IS CALCULATED IN ORDER 
% TO GET THE POINT REACHED. 
  string_to_end_point(String, Draw, Move,
                      Nograph, Angle, 
                      InitialPoint, 
                      LastPoint), 

% THE EUCLIDEAN DISTANCE BETWEEN THE TWO
% POINTS IS CALCULATED. 
  distance(InitialPoint, LastPoint, Distance), 

% THE EFFECTIVE LENGTH (WITHOUT 
% OVERLAPPING SEGMENTS) DEPICTED BY THE 
% CURVE IS CALCULATED. 
  string_to_effective_length(String, Draw, Move, 
                             Nograph, Angle, 
                             EffectiveLength), 

% AND FINALLY THE FRACTAL DIMENSION IS 
% ESTIMATED. 
  FractalDimension is 
  log(EffectiveLength)/log(Distance). 

Conclusions

The L system that represents a fractal curve with a turtle graphics interpretation has proved to contain enough information for the computation of the fractal dimension of the curve, for an interesting family of systems. In some cases, the computation may have to be applied to a sequence of derivations, and thus will be exponentially slow, but this is a consequence of the inherent exponential growth of fractal curves. However, in many other cases it is not necessary to compute this limit, and the appropriate dimension can be obtained in one or two steps.

Fractals represented by L systems associated with a vector graphics interpretation are automatically covered by our algorithm, if they have previously been converted to equivalent L systems with a turtle graphics interpretation, using the algorithm described in Reference [10].

In the future, we will try to extend the method to more complicated turtle graphics interpretations and to different types of L systems, such as those which have rules whose left symbols do not lead to the same results. The primary handicap with these systems is that they have not been well documented. Most of the fractals in the literature belong to the same class as the examples in this paper.

Acknowledgment

This paper has been sponsored by the Spanish Interdepartmental Commission of Science and Technology (CICYT), Project No. TEL1999-0181.

References

Received January 21, 2001; accepted for publication August 16, 2001