Join segments / concatenate paths

hello all,
I am working on a project that is like a truchet tilling, I am using versions of a tile that are distributed in a grid and are rotates randomly to generate a certain drawing. once I have the random distribution, I would like to connect the segments and find the paths (like shown in the illustration)
I am asking if there is a known algorithm or paper to optimize this kind of task instead of just brut forcing it by comparing each point with all the others and finding the nearest one within a certain tolerance ?


1 Like

To generate the paths, wouldn’t you just walk through the grid and append each path segment based on the type and orientation as you go? I would store a bit field (i.e., an integer) for each tile that stores the type and orientation and has flags for which enter/exit points have been visited. Make a small lookup table that uses the enter direction and tile orientation to tell you which next tile to visit and your new walking orientation (i.e., 0-3 for left, up, right, down). If you store the nWide x nHigh tiles in a 1-D array, you can get the next tile by adding 1, nWide, -1, or -nWide to your current index for the 4 directions.

Run through the tiles in order looking for an unvisited path. Then walk the path adding on line segments, marking the edges that you visit. Each time a walk hits either the edge of the screen or a visited path (you’ve closed a loop), go back to the next tile in order and continue looking for the next unvisited path.

Don’t create the path segments first and try to join them. Instead, only add segments on to your paths as you create them by walking through the tiling.


Thanx , that’s a good start !