User:Devon McCormick/DLA00/BuildingACloseNeighborhood

Building a Close Neighborhood

A flaw in the existing DLA (diffusion-limited aggregation) code - in the original code as well as in a preliminary re-vamp of this code (also here) - results in etiolated structures, for the reason illustrated below. New points are "released" in the narrow band indicated by the area between the inner and outer circles here.

Since this code avoids the potentially infinite processing of a point that wanders away from the cluster by limiting the number of steps in the random walk, this means that points released too far from any point on the cluster will never get a chance to join it.

Centering the Cluster

An attempt to address this by adjusting the central point to be at the center of the point cluster, rather than at the center of the entire space, doesn’t avoid the problem of preferentially adding points to the extreme ends of the cluster as illustrated below. As above, the circular band represents the area in which new points are released.

Release from a Convex Hull

One proposed solution is to build a release neighborhood based on the convex hull. However, for certain shapes of clusters, this has essentially the same problem, as illustrated here.

Building a Neighborhood

So, the ideal release neighborhood would form some sort of loose outline around the cluster. How might we do this? What follows is one way that shows some promise (an alternate exposition of the following method, in the context of a slightly more advanced version of this DLA code, can be found here). We’ll work with the following problematic cluster.

This was actually generated from the original version of the DLA code but using the following variant of the random walk function:

walk2=: 3 : 'y + (? 1 +  # nbs) { nbs, csign center - y'
NB. Random walk biased toward center of lattice
csign=: (+.^:_1) @ ( * @ +.)
NB. Get the 'sign' of a complex number i.e. csign 0.25j_0.5 -> 1j_1

As the above diagram illustrates, this alternate method also exhibits the "etiolation problem" albeit in two dimensions.

We'll start by transforming the bit-map representation of the space into an explicit list of points:

   $PTS=: ($space)#:I.,space
12248 2
   3{.PTS     NB. What do some points look like?
222 521
223 522
224 523

(We're using the name space instead of its namespace-qualified version space_dla_ because we specified

   coinsert 'dla'

in our session.)

We use this form to help us by finding points with no neighbors:

   neigh2=: 13 : 'x-.~~.,/y+"1/+.nbs'   NB. Empty neighbors of these
   $NP=: PTS neigh2 PTS
31050 2
   viewmat 2 (<"1 NP)}space

This gives us something as shown here:

If you look closely, you'll see that the original, delicate structure looks a little fatter as we've chosen all the points next to each point in the original.

However, it’s easier to see the effect if we apply this repeatedly to its own result (timed here to show expensive this could be),

   6!:2 'NP=: PTS neigh2^:20]NP'
94.124175

giving this picture:

So, essentially we've chosen an envelope of points around the original set. Removing the points in the cluster gives us a release neighborhood that’s perhaps too close. However if we take only the points just outside this set,

   edges=. NP -.~ ,/NP+"1/+.nbs

Where nbs is a global, from the original implementation, that gives the offsets to generate the eight cells surrounding a given point in a two-dimensional, square lattice.

   |:+.nbs
1 1 0 _1 _1 _1  0  1
0 1 1  1  0 _1 _1 _1
   $edges
76076 2

This is a lot of points, but many of them are duplicated, as seen by looking at the "nub" of this set.

   $edges=. ~.edges
15159 2
   viewmat 2 (<"1 edges)}space

giving us this thin envelope:

We can then expand this into a release area, or set of "release candidates" RC, by finding the neighbors of the points in this envelope,

   $RC=: PTS neigh2^:4]edges-.PTS
25970 2
   viewmat 2 (<"1 RC)}space

we get something more interesting, as seen here:

These release candidates closely border the cluster. If we release a point in this neighborhood close to the cluster, our random walk will encounter it fairly quickly but we're not biased toward adding points to any particular part of the cluster.

There are potentially small islands of release areas within the cluster as seen in the small pink blob on the lower left quadrant here. These can be accentuated by choosing a narrower initial, enclosing envelope, e.g instead of "20" iterations in the above "expensive" expression

   NP=: PTS neigh2^:20]NP

we could choose a smaller number - like "15" - giving us a result more quickly. Alternately, these islands can be eliminated by fattening the original enclosure by choosing more iterations at that step. The arbitrariness of these adjustments reflects that this is essentially an aesthetic choice.

Arbitrary Seeds

We can apply this technique to any arbitrary set of points to seed the cluster.

Single Seed Structure

Let's say we start with our favorite letter and apply a few hundred random points. We might get something like this:

If we continue aggregating to this, we'll get something like this:

Eventually, the original structure gets buried in the ever-growing aggregation:

Multiple Seeds

Once we've gone this far, there's no reason we can't also apply this to multiple point sets:

And continue to aggregate this:

As long as we like: