(Adapted from an article published in the IBM Technical Disclosure Bulletin, Vol. 34 No. 8 (January, 1992), pages 275-277, and Vol. 34 No. 12 (May, 1992) pages 476-477.)
Senile Depth First Search applied to Iterated Function Systems
Timothy D. Greer
Disclosed is a deterministic, terminating method to mark the points in a quantized space, such as an array of pixels, according to whether or not a given iterated function system "hits" each quantized region. The method is based on depth first search, but avoids unproductive exploring of many branches by acting senile -- the algorithm forgets upper portions of the search tree. One use is to speed up the display of images of fractals, and to eliminate the need for stochastic algorithms.
This description refers to (X,Y) coordinates as if the iterated function system is a subset of the 2-dimensional plane. This is for convenience and clarity only. The system can be a subset of higher dimensions as well, or one dimensional too. Likewise, "plotting" a point here may be taken to mean marking the memory location (X,Y,Z,...). Marking a two-dimensional memory location is equivalent to lighting a pixel on a digital display.
In the accompanying flowchart, the current and previous values of the coordinates for plotting are kept in the arrays X(*) and Y(*). The function used to get from one (X,Y) pair to the next is identified by the array MAP(*). The function "Plot (X,Y)" marks a pixel. X and Y are floating point numbers, whereas the Plot function can plot only integer values, so the values of X and Y are rounded to the nearest integer within the plotting routine. Likewise rounding occurs when checking to see if a point has already been plotted.
The flowchart acts as an ordinary depth first search, except that after the depth of MAX+1 is reached, the oldest points begin to be written over. The amount of overwriting is unlimited. Since each of the iterating functions can be invoked to get to the next point, the depth first search will have at each node as many branches as there are functions. Encountering a pixel that is already plotted is the signal to the depth first search to begin backing up. If all branches have been covered from the node backed up to, the depth first search algorithm backs up again, and so on until it is back to the beginning. Since in the following algorithm the beginning is expected to be written over, the variable BOT is introduced as a variable bottom of the tree. When the depth first search backs up so that TOP=BOT, the search has backed up either as deep as it went or from a depth of MAX+1, which is as far as it could remember, so the algorithm then halts.
If the iterated function system is bounded in extent, the algorithm must eventually terminate because there are at most a finite number of pixels to plot. Since each point is obtained from previous points by using the iterating functions, only points lying on the iterated function system will be plotted. (Rounding occurs at plotting, but the floating point values are to be used in calculating the next point.) If the iterated function system is composed entirely of contraction mappings, it is a fractal and is guaranteed to be bounded in extent. [1] If non-contraction mappings are involved, but points are plotted modulo some number, as they would be with finite computer memory, the system is still effectively bounded, so again the algorithm will terminate.
Reference
1. Barnsley, M. F. Fractals Everywhere. Academic Press, Boston, 1988, pages 80-82.
Flowchart
Dimension X(MAX+1), Y(MAX+1), MAP(MAX+1)
Function Definitions Increment(n) = 0 if n=MAX Decrement(n) = MAX if n=0
= n+1 otherwise = n-1 otherwise
-----------------------
| TOP=BOT=0 |
| X(0)=InitialX | Notes: The mappings are numbered 0 to NMAPS-1.
| Y(0)=InitialY | The point (Fx(A,B,I),Fy(A,B,I)) is the
| MAP(0)=0 | image of the point (A,B) under the
----------------------- Ith mapping.
|
|
V
O<-------------------------------------
| |
| |
V |
O<-------------------------------- |
| | |
| | |
V | |
----------------------- | |
| I=Increment(TOP) | | |
----------------------- | |
| | |
| | |
V | |
------------------------------------ | |
| X(I)=Fx(X(TOP),Y(TOP),MAP(TOP)) | | |
| Y(I)=Fy(X(TOP),Y(TOP),MAP(TOP)) | | |
------------------------------------ | |
| | |
| | |
V | |
----------------------- | |
| TOP=I | | |
----------------------- | |
| | |
| | |
V | |
/ \ | |
/Is \ | |
/ \ Yes | |
/TOP=BOT\___________ | |
\ / | | |
\ ? / V | |
\ / ---------------------- | |
\ / | BOT=Increment(BOT) | | |
| ---------------------- | |
No | | | |
V | | |
O<-------------- | |
| | |
| | |
V | |
--------------------------- | |
| MAP(TOP)=0 | | |
--------------------------- | |
| | |
| | |
V | |
/ \ | |
/ \ | |
/ \ | |
/ \ | |
/ Is \ _________________ | |
/ \ | | | |
/(X(TOP),Y(TOP))\___\| Plot |_| |
\ / /| (X(TOP),Y(TOP)) | |
\ already / No |_________________| |
\ plotted / |
\ ? / |
\ / |
\ / |
\ / |
\ / |
| |
Yes | |
| |
V |
O<------------------------------- |
| | |
| | |
V | |
----------------------- | |
| TOP=Decrement(TOP) | | |
----------------------- | |
| | |
| | |
V | |
/ \ | |
/Is \ | |
/ \ | |
/TOP=BOT\ | |
/ and \ Yes | |
/ MAP(TOP) \_________ | |
\ =NMAPS-1 / | | |
\ / | | |
\ ? / | | |
\ / _V__ | |
\ / / \ | |
\ / / \ | |
| | STOP | | |
No | | | | |
V \ / | |
/ \ \____/ | |
/ \ | |
/ \ | |
/ Is \ | |
/ \ Yes | |
/ MAP(TOP) \_________________________| |
\ =NMAPS-1 / |
\ / |
\ ? / |
\ / |
\ / |
\ / |
\ / |
| |
No | |
| |
V |
------------------------- |
| MAP(TOP)=MAP(TOP)+1 |-----------------------
-------------------------
Related Articles
- Method for finding geometrically similar fractal confined to fixed region
- Method for scaling fractal for display by finding upper bound on extent
- Pseudocode (actually C code lifted right out of one of my programs, written for DOS and the IBM/C2 compiler) is available in Chapter 8 of Fractal Horizons: The Future Use of Fractals
The information provided, and views expressed on this site are my own and do not represent the IBM Corporation.