Browse Prior Art Database

Method for Scaling Fractal for Display by Finding Upper Bound on Extent

IP.com Disclosure Number: IPCOM000104953D
Original Publication Date: 1993-Jun-01
Included in the Prior Art Database: 2005-Mar-19
Document File: 4 page(s) / 123K

Publishing Venue

IBM

Related People

Greer, TD: AUTHOR

Abstract

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:

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

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 [*]  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.  It 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 [*], we can obtain a loose bound for
the extent of the fractal.  Specifically, we obtain a circle which
encloses the fractal.  It also points out that the same algorithm
applies to fractals imbedded in higher than two dimen- sions.  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 [*], 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...