Meander Space Colonization – Algorithm 13.1

I just published a few days back an introduction to a series of ‘space colonization’ algorithms. The term sounds a bit sexier than it is, evoking images of bases on Mars and interstellar travel, but actually it just means connecting a cloud of random points into a network using one or a combination of specific strategies. As mentioned in the previous post, Peter Stevens proposed in 1974 that there are essentially only four possible strategies for connecting a population of points in 2D space with a non-redundant network, i.e. a network where only one path is possible between any two given points in the network.

The goal of the current algorithm is to connect the points with a meander network, i.e. a network where a single line connects all points without crossing over itself, and with frequent and unpredictable shifts in direction, unlike the spiral which similarly connects all points with one line, but using a consistent rotational direction.

The algorithm proposed here is *not* perfect but the results are generally good and if perfection is called for, may need some manually tweaking in the end. I have some ideas for fixes, but these might come in a future post.

Step One – Populate an Area, Calculate Cloud Density, and determine a Search Radius

In this first step, we will draw a closed curve. The algorithm works well with rectangles and circles, and even some irregular shapes like trapezoids, but won’t give good results with shapes that are too irregular. We then turn this curve into a surface with the Boundary Surface component and populate it with a cloud of points using the PopGeo component. Next we want to find out the density of the point cloud by finding the average distance between any two random points. I do this by using the Closest Points component searching for four points, using Cull Index on item 0 since this is always a point’s self (the closest person to you is yourself, technically, but usually you don’t want to know this). I then used the Average component twice to find first the average distance for a single point to its three closest neighbors and then to get the average distance to the closest points for all points in the set. I will then multiply this ‘cloud density’ factor by a parameter to determine the meander’s search radius, which will affect the meander algorithm’s behavior in the next steps. Depending on cloud density, numbers between around 1.3 and 2.5 seem to give the best results

Step Two – Set up the Loop

For this algorithm we will be using the Anemone plugin. See Algorithm 8.1 for basics on Loop setup if your not familiar with these. For this algorithm, we will be using three Data Ports in the loop: D0, D1, and D2. We input the initial point cloud into D0 and will iteratively remove one point from this cloud at every step of the algorithm. D1 will track the current ‘active’ point, which is initially a user input point from Rhino, but which will be the last point removed from the point cloud in D0 at each further step. Finally, D2 will be a collection of our Meander line segments. Initially there is no data in the D2 stream, but by the end there will be a list of segments equal to the initial population of points input into D0.

Step Three – Find the Next Point for the Growing Meander

The loop performs three operations in each round. First it finds the next point in the meander, secondly it draws a line between the last segment and the identified point, thirdly it removes the identified point from the point cloud set of unused points and makes this the new ‘active point.’

In each round, to determine which point the meander will grow to next, the algorithm searches all potential points in the point cloud within a given search radius from the end of the current meander set of lines. It does this by drawing a Circle with a Radius equal to the Point Cloud Density * Search Radius Factor determined in the previous step. Next using the Point in Curve component together with an Equality test, potential candidate points are determined–in this case all points in or on the curve are candidates, so if their R value is either 2 or 1, they can be selected, hence the use of the R not equal to 0 output. Candidate points are then put in a set with the Dispatch component, after which using Deconstruct Point, the Y value for each point is obtained. Since in this case we want a meander moving from the bottom of our point population to the top, the Point with the Lowest Y Value is identified as the next point in the Meander. Note that for this to work, the meander start point needs to be at the bottom of the point set. You can start to the left or right of the set as well, but then you need to reconfigure the script slightly in each case. A meander moving from left to right will use the point with the lowest X value, a meander moving from right to left will use the point with the highest X value, while a meander moving from top to down will use the point with the highest Y value.

There are cases, however, when no potential points are identified within the search radius. What then? To avoid the script from getting stuck, my provisional solution is to simply move to the Closest Point in the overall set. This can create some funny behaviors and is not an ideal solution, but for now is an acceptable short-term hack to keep things moving along. Future iterations of the script will hopefully have an improved ‘escape’ case.

To choose which of the behaviors is activated, the algorithm uses a simple if then expression. The expression is <<if (x = 0, y, z)>>. In this case x is a determined through a Mass Addition of the relation output of the Point in Curve component. If no points are in or on the curve, the result should be 0. If x = 0, the point input into y is chosen (the output of the second behavior), else the standard behavior with a point input into z is chosen.

Step Four –  Draw Meander Geometry, Replace Active Point, Remove Identified Point from the Unused Point Set

The final part of the loop does a few simple things. First a Line is drawn from the active point from the beginning of the round (the end of the growing meander) and the identified next point, this line is then added to a set of lines being fed through the D2 port of the Anemone loop. The identified point is then fed into the D1 input on the loop, effectively replacing the active point for the next round. Finally, the identified point needs to be removed from the set of unused points. This is done by using the Closest Point component to obtain the index for the point’s self, and then using Cull Index to remove this from the set.

Variations

Once everything is up and running, its time to try to see what the effect of changing various parameters. The results of changing the cloud density are shown at the top row, the results of changing the search radius factor in the second row, while changing the random seed produces results in the third row. The most important of these to note is changing the search radius. Where this value is low, the meander is well, a bit more meandering. making this high tends to create a much more striated series of meanders. If it is TOO low, however, the results will be unacceptable as the escape condition gets invoked too many times and the meander will jump a lot more.

If this all makes sense, an added challenge might be to adapt the script to work through a cloud of varying densities. Here the point cloud density needs to be recalculated with every round of the loop, where the search radius adapts to the local density near the current active point. I was quite happy with the results however, with the line in the image below used to generate the rendering at the top of this post.