Connect points to create paths

Maybe path is already a bad word. A path usually has no branches where multiple lines meet. But the image shows many such branches.
So i guess you want a graph, where most vertices are connected to two neighbors, but some can have more?

What more can you say?
Is your input axis aligned?
Are the expected lines at quantized to steps of 45 degrees?
Is it ok to have some disconnected vertices? (e.g. the two isolated dots on the very left?)

Actually, assuming all answers are a yes, what i have in mind would be something like this:

For each point, search for all nearby points within a given max radius.
Make an angular histogram from these, using bins of 45 degrees.
Use the histogram counts to decide in which directions we want to make a connection.
Find the closest points along those directions. If they are not very close, make no connection.

Agreed with the above.

I'd start with evaluating proximity to adjacent points. Assuming you're turning them into lines for ‘paths’, begin merging them based on proximity to established lines, growing and connecting the line as you go. You would need to play with tolerance a bit for what is considered close enough.

The next phase would be to look for disconnected segments. There are sparse segments along many of the lines. Depending on the rules (e.g. they look like they should be axis aligned) for each disconnected segment you could do line/ray intersection tests extending rays off each line segment and look for the shortest match, extending and merging them. If they're still outside your distance tolerance, turn them into ray/ray looking for the nearest intersection, extending and merging if you find one inside your tolerance.

But that's a lot of assumptions about the data and the rules behind your paths.

push all those points positions in a A* algorithm and then you can find path between any two locations, put multiple source and target for each branch separately …

@JoeJ Agree - it's a graph. I used the word path because these points refer to the path on ground where they were recorded.

The points are not axis aligned, and they could be going at any angle. There could be some disconnected points - but ideally there should always another point nearby to connect to. For the sake of simplicity we can assume that there are no such “loose” “hanging” points.

Thanks for your suggestion which I am going to try.

@frob Yes, the points are to be connected based upon the proximity. A nearest point is likely to be the point that connects to the point being processed. If there is more than one point within a threshold, then it implies branching. I will look into your suggestions further.

@Enzio599 Perhaps A* algorithm assumes that the connectivity exists and is already established to discover the path from A to B?

kaarigar said:
The points are not axis aligned, and they could be going at any angle. There could be some disconnected points - but ideally there should always another point nearby to connect to. For the sake of simplicity we can assume that there are no such “loose” “hanging” points. Thanks for your suggestion which I am going to try.

If the points are not axis aligned my proposal isn't that good, because we have no way to orient the histogram.
We could compute a global direction field to get such alignment. This is often used for geometry processing, looking like this:

This is a smooth crossfield, and it tries to align to primary curvature directions of the mesh. This would also work well for your example image, which has mostly 90 degrees angles. Even if we would rotate it by 30 degrees, and do some fisheye distortion, the field would still provide good local orientations so we know in which directions line segments probably go, to orient the histogram.

Beside crosses, this also works for lines (two vectors 180 degrees apart), and various stars (6 or 8 vectors, 60 or 45 degrees), or any other division of 360 degrees by a whole number.

However, if your input has high frequency curves and no global angular pattern, all this makes little sense.

Frobs proposal sounds like a solution which does not require to learn about such fields or other fancy stuff. I'd try such thing first, and only if result is too erroneous / low quality, try something else.

I like Enzios idea, which i think could be really nice eventually, if you already have graph algorithms like Dijkstra and spanning tree ready.
A similar application of this is to divide a high genus mesh into a set of patches which can be parametrized, e.g. to make automatic UV maps: https://www.cs.cmu.edu/~kmcrane/Projects/LoopsOnSurfaces/

The resulting paths look ugly and not nice, but this can be improved.
So at first you make a mesh containing all edges shorter than a given max value.
Though, this gives us the first problem of many crossing edges. Some graph algorithm should exist to remove them, so the remainder is a triangle mesh (with huge holes but that's fine). Maybe this step is optional and handled well enough by the next:
The second problem is to get rid of more edges so we have nice lines and no triangles.
One idea would be to find a low number of special points using some heuristic, which in your case would be the points where more than two lines meet (my histogram idea might work well enough to find them, even without alignment). Special points should not have other special points nearby.
If we have good special points, every other point could find the shortest path to the closest special point using Dijkstra. The resulting paths then might look pretty good. Finally you might want to connect disjoint graphs to close holes where one edge is missing.

kaarigar said:
@Enzio599 Perhaps A* algorithm assumes that the connectivity exists and is already established to discover the path from A to B?

Indeed. A* works by extending to neighbours in all directions repeatedly and smart selection of the next point to expand. Here the problem is to decide “what points are a neighbour”.

Wait, wouldn't a simple spanning tree already give the desired result, without any further work?
I think it would, turning all other proposals into over-complicated mess.

So you would just generate a initial graph by adding edges shorter than a given threshold, then compute the spanning tree and done.

Depending on what is being optimized, particularly total length of the graph edges vs. length of paths between the points, a minimum spanning tree might be improved by

• upgrading it to a Steiner tree (not likely to improve the example much, but there can be substantial difference with large gaps between clusters)
• adding extra edges as "shortcuts" to improve the ratio between the distance and path length between any two points (the smaller the ratio, the more convoluted the path)

Connect main dots(common lines). As in your picture looks like lines together but fragmented.