(Adapted from an article published in the IBM Technical Disclosure Bulletin, Vol. 34 No. 7B (December, 1991), pages 24-25.)
Method for finding geometrically similar fractal confined to fixed region
Timothy D. Greer
Disclosed is a method for determining the parameters of an iterated function system which generates a scaled fractal geometrically similar to the fractal generated by an original iterated function system. The terminology used is for fractals imbedded in two dimensions, but the extension to higher dimensions is straightforward. Likewise, stretching or compressing, to correct for aspect ratios for example, is easy to incorporate into the procedure.
An Iterated Function System definition of a fractal may consist of a set of affine contraction mappings [1]. Affine mappings are vector functions of the form f(x)=Ax+b, where x, f(x), and b are n-dimensional vectors and A is an n by n matrix. The fixed point of each mapping is the vector y such that y=Ay+b. So the fixed point is
-1
y = (I-A) b
where I is the n by n identity matrix
and the -1 denotes inverse.
The "image of a circle" under this mapping f means the points that
are obtained when every point on the circle is subjected to the
mapping f. Mathematically, this is the range of
f when the domain
of f is restricted to the circle.
The following procedure produces the mappings which define a new fractal, geometrically similar to the original, which lies within a pre-defined circle, say C(s,S). In the following C(c,R) denotes a circle centered at c, with radius R.
- Calculate the fixed points of the mappings making up the IFS, and then determine their average (the centroid, giving each point equal weight). Call the average c. It will be the center of a circle which will be guaranteed to contain the fractal.
- Find the most distant fixed point from c and choose an initial radius R of the containing circle to be the distance between c and this most distant fixed point.
- For each mapping in turn, increase R if necessary so that the image of C(c,R) just lies within C(c,R). This can always be done because the mappings are contraction mappings. An iterative method to bracket the necessary R is to successively double the step size by which R increases, until R is big enough. Once the necessary R is bracketed, successively halve the bracketing interval until R is as near as desired to exactly the distance of the most distant point from c on the image of C(c,R). R is never decreased from mapping to mapping, so the image of the circle under all the previous mappings will also lie within the circle.
- Now the circle C(c,R) encloses its image under all
the mappings defining the original fractal, so C(c,R) must
contain the entire fractal. Also, since in the previous step R was
always made only just big enough,
C(c,R) is the smallest circle centered at c which encloses its image
under each of the mappings.
(To find the smallest circle which encloses the fractal would require
adjustment of the center as well as the radius.)
Find the linear transformation
u=Mx+m
which transforms the circle C(c,R) to the desired circle C(s,S).
For each original mapping f(x)=Ax+b, the
corresponding new mapping is g(x)=Gx+h, where
-1 -1 G = MAM and h = -MAM m + Mb + m
Since these formulas are not obvious, here is the derivation for the matrix G and the vector h. The derivation uses the notation x'=Ax+b for the original mapping and u'=Gu+h for the new mapping. The new fractal will be geometrically similar to the original, with the similarity transformation u=Mx+m, if for each point x on the old fractal there exists a point u=Mx+m on the new fractal, and u'=Mx'+m. So
Gu + h = u' = Mx' + m = M[Ax+b] + m
-1 -1
= M[A(M u - M m) + b] + m
-1 -1
= MAM u - MAM m + Mb + m
Reference
1. Barnsley, M. F. Fractals Everywhere. Academic Press, Boston, 1988, page 82.Related Articles
The information provided, and views expressed on this site are my own and do not represent the IBM Corporation.