(Adapted from an article published in the IBM Technical Disclosure Bulletin, Vol. 36 No. 6A (June, 1993), pages 489-491. See also Optimization on a Fractal Feasible Region for more of the mathematical underpinnings.)

Method for scaling fractal for display by finding upper bound on extent

Disclosed is a method to rescale a fractal for display. The method is to calculate a tight upper bound to the extent of the fractal, and then rescale so that the polygon comprising the tight upper bound just fits into the desired display window. While rescaling given a tight upper bound is an obvious approach, its application to this problem is novel because a tight upper bound was never available. Most of this disclosure will be a discussion of how to obtain such a tight upper bound. The method may usefully be applied to the following sorts of problems.

1. Finding the extent of a fractal in any given direction.
2. Finding a tight upper bound for the extent of a fractal in a given direction.
3. Finding the convex hull of a fractal.
4. Finding the boundary of the convex hull of a fractal.
5. Finding an approximation to the boundary of the convex hull of a fractal.
6. Finding a polygonal approximation to the boundary of the convex hull of a fractal.

An earlier disclosure [1] presented a method to obtain an upper bound to the extent of a fractal defined by an iterated function system made up of affine transformations. [1] also described how to alter the affine transformations to accomplish the rescaling required to fit its upper bound within the limits of the display window.

Using the techniques of [1], we can obtain a loose bound for the extent of the fractal. Specifically, we obtain a circle which encloses the fractal. ([1] also points out that the same algorithm applies to fractals imbedded in higher than two dimensions. A similar statement applies to this disclosure, although the computational complexity of the algorithms required might limit the usefulness of this disclosure in higher dimensions.) This circle is optimal in the sense that, based on the algorithm which generates it, no smaller circle with the same center exists which can be guaranteed to contain the fractal. So, this circle makes a nice starting point.

Given the circle obtained using the procedure in [1], increase its radius by a small amount, say 1%. The image of this larger circle under each mapping of the iterated function system will lie strictly inside the circle (i.e. no image will be tangent to or will extend beyond the circle). Now pick a direction. Each of the images of the circle has some point which is farthest in the picked direction; these points can be found using ordinary techniques of vector calculus. We thus find the point farthest in the picked direction which lies on an image of the circle under some mapping. (Ties may be broken arbitrarily.) Draw a secant to the circle through this point, perpendicular to the given direction. Since the images of a circle which encloses the fractal all lie to one side of the secant, the entire fractal must lie to that side also.

The secant intersects the enclosing circle in two points. Pick one of those points; the vector difference between this point and the center of the circle defines a new direction, from which a new secant is obtained using the above procedure. One of the points of intersection of the new secant with the circle is farther around the circle; use it to define yet another direction. By this method one proceeds all the way around the circle. The intersections of the secants define the vertices of a polygon which is entirely within the interior of the circle, and which contains the fractal.

After obtaining these points making up the vertices of an enclosing polygon, the polygon may be iteratively improved. Apply each mapping of the iterated function system to each point. From the new set of points, eliminate all those that may be written as convex combinations of the others. That is, eliminate all except the extreme points of the convex region generated by the points. The remaining points are the vertices of an improved polygon -- improved in the sense that it is contained within the previous polygon. The limit of this procedure is the boundary of the convex hull of the fractal, but a small number of iterations suffice to bound the fractal reasonably well.

"Hurricane" fractal shown with convex closure boundary

6-mapping IFS shown with convex closure boundary

The result of this procedure is a set of points, the vertices of a polygon. As an illustration, the figures show two fractals, each enclosed by its polygon resulting from the procedure. It is apparent that the boundary of the convex hull of the fractal is well approximated by the polygon. After determining the maximums and minimums of the points in each coordinate direction, the transformation which maps these maximums and minimums to the size of the display window can be used, as shown in [1], to rescale the fractal. Because the polygon encloses the fractal and approximates the boundary of its convex hull, the entire fractal will be displayed and will fill the display. Scaling the fractal has been reduced to a problem of scaling a polygon, so other aspects of the display window (if it is not rectangular, for example) can also be accommodated if necessary.

Reference

1. Greer, Timothy D. "Method for Finding Geometrically Similar Fractal Confined to Fixed Region", IBM Technical Disclosure Bulletin Volume 34, No. 7B (December 1991), pp. 24-25.
   
   

   The information provided, and views expressed on this site are my own and do not represent the IBM Corporation.

   
   
    
   

Return to the author's home page.