10182

# Dynamic Step Distance Transforms

This Demonstration explores various ways of measuring the distance of a cell from a set of initial cells. Each cell stores a distance and a color (black or white), and these values propagate out from the initial set. The color of each cell is updated based on the colors of the neighboring cells at smaller distances. For example, the color might be set to white if the number of white, smaller neighbors is 0 or 2; this is totalistic color rule 1010000002=320. Distances between cells are measured by a variation of the taxicab metric: as the sum of distance steps along a connected path, with the individual steps chosen by taking the corresponding horizontal, vertical, or diagonal entry from one of the two sets of 3x3 values shown. The color of the cell is used to choose one of the two sets. Toggle the distance steps, then use the slider to change their values.

### DETAILS

Several of the snapshots and bookmarks show approximately circular patterns. Other snapshots show snowflake-like shapes, rectangular or hexagonal, and patterns that operate on two scales, such as the "bow tie" example.
The statistics displayed under the images include two ways of measuring the circularity: the percentage variation in the radius and the number of sides of the polygon with the same radial variation.
The "symmetric" checkbox (checked) means that the initial cells are set to 1 (white) and surrounded by zeros (black). When unchecked, the right and diagonal lower-left values are also set to 1. Try making the bow tie or "least circular" bookmarks symmetric.
Internally the color is saved as the least significant bit of the distance, which is why the distance steps are even numbers.
The smaller neighbor counts image has a value at each cell in the range 0-8, equal to the number of neighbors with smaller distances. Closely spaced parallel white lines radiating outwards in this image are caused by distance contours with a fine sawtooth pattern, and always seem to indicate circularity generation or smoothing.
For example, the approximately circular rule 416 (Snapshot 2) with size set to the maximum (wait a few seconds) shows this, as does Snapshot 1. The most circular-appearing rule (20-sided polygon bookmark) shows a more uniform pattern; at large scale it can be seen to be a polygon without much smoothing. At a size of approximately 1000, the slight instability on the diagonals blows up and the circle grows four ears.
The rotationally symmetric rules are set up by taking the pattern of smaller neighbors as digits, cyclically rotating to a minimum position, then applying a rule to the first three or four color bits, taken in clockwise order from that position.
The hexagonal rules (rule type 6) use the two least significant bits for the color (black/white) and to simulate the hexagonal neighborhood by switching the six neighbors on alternate rows. Rule type 9, where the rule counts smaller neighbors (instead of smaller white neighbors), can achieve a similar effect. For example, try rule 348 with white distance steps (clockwise from top left) = {2, 2, 2, 100, 2, 2, 2, 100} and black distance steps={0, 198, 0, 0, 0, 198, 0, 0}.
Other growth rules (A New Kind of Science, p. 928) can be simulated by setting the black steps to a large value (or to 0, meaning ignore this neighbor), so that growth occurs first for smaller (white) steps.
The worm rules (rule type 7) turn left or right at each step depending on the color, producing tightly twisting or spiralling patterns with long path lengths. The path length is the longest series of decreasing distances back to the start.
With random selection of the color (rule type 8) it is interesting to vary the proportion of white/black and to compare the result with patterns generated by a color rule with the same percentage of white cells.
These dynamic step distance transforms can be defined more generally as cellular automata on directed acyclic networks on a grid. As with other kinds of distance transforms (fixed step or Euclidean), cells can be updated in parallel or sequentially in any order, with the same end result, although by updating in order of increasing distance, each cell need only be updated once.
They can be useful for image analysis and for modeling patterns where growth occurs along a front that sweeps across an area, leaving a fixed pattern behind. Examples include the time evolution of 1D cellular automata, and more general cases where the network connections and shape of the front are generated dynamically.

### PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.