Random grid edge traversal (?)

I’m trying to come up with a method for “outlining” or following the edges of a set of random square cells, so that the edges connect and can pass through diagonal areas. See the images:

ConnectedGridsmall

The curve is colored with a gradient to help show how it follows along edges but passes through intersections where squares touch diagonally. You can see in the first image that segments should not have extra vertices if it just continues straight. And in the second image there are actually 2 curves (the long purple vertical line in the middle helps to show that). I did those by hand so there could be mistakes.

Any ideas for going from the left side of the images (either as curves or surfaces) to the right side? I’d be happy with just an explanation of how you might go about it. or c# or gh!

Is there a proper name for this? I just don’t know what to google. The closest looking thing I could find are Knot Grid Diagrams which are only visually similar.

In Grasshopper you can get sort of close if you join boundary surfaces made from the squares and then take their naked edges and join those, but it does not cross over diagonals:

gridJoin.gh (8.7 KB)

An Eulerian path uses every edge of a graph exactly once.

Such a path only exists if all the vertices are connected to an even number of edges, but it looks like this is true here.

1 Like

I could be wrong but it seems that what I did do the job


Or quite

1 Like

Daniel and Laurent, your comments were helpful in sending me down the right route to figuring this out. I looked into Eulerian paths and realized it would be good to represent this as a graph, so I did so using adjacency lists for every node. Since every node is either valence 2 or valence 4, it was pretty easy to see that it always goes straight through valence 4 nodes and just follows edges otherwise.

So I wrote some code to do that and it was working, although a little slow. I realized I was creating a ton of boundary surfaces at one step where I could create meshes instead, and save a little time. Well, when testing meshes vs breps I found, to my surprise, that just joining meshes and getting their naked edges results in exactly the same thing but 4 times as fast.

Just this code:

Mesh joinedMesh = new Mesh();
for(int i = 0; i < grid.Count; i++)
{
  joinedMesh.Append(Mesh.CreateFromClosedPolyline(grid[i].ToPolyline()));
}

Polyline[] edges = joinedMesh.GetNakedEdges();

A = edges;

For anyone to play with:
gridJoin_RE.gh (44.4 KB)

4 Likes

That is a neat solution!

1 Like