PostGIS or QGIS: Convert unsorted points to a single line by connecting each 2 closest points

Question

I have shapefile/PostGIS table of points.

I want to connect them to form a single line.

When trying with PostGIS:

Select ST_MakeLine(points_table.geom) FROM points_table;

The problem is that because the points are not ordered, the line is crossing itself.

When trying in QGIS Points2One plugin - same issue.

After looking at the data - It seems that if connect each 2 closest points - the desired line will created.

Answer 1

This problem is quite complex... or it's a compilation of several problems... I can see at least two

1. Which of points is first and which is last
2. What is correct order of points

As a resolution of first I think we have to find 2 nearest points for every point and then look for a point which in nearest points of nearest points doesn't have this point (I know it sounds complicated)

Second problem - when we'll find start we have to point after point search for nearest till we reach the end...

Of course since we have no order given every resolution will be only guessing and this will not work for every set of points but if we get from the first to the last point, and there will be no points not included in the line, we can assume that our solution is correct.

As other resolutions could be some brute-force method - join points in every order and return first non-self-intersected line including all points, or use some genetic algorithm...

I'll try to write some plpgsql function as a first resolution POC later.

Answer 2

You can use ST_ClosestPoint() to find the closest one to each point. If you use that in combination with make line you should be able to achieve what you need. Here is a link to the documentation for ST_ClosestPoint().

You could do it like this -

select st_asgeojson(st_makeline(g)) from 

    (select geometry as g from testing group by geometry order by st_closestpoint(geometry, geometry)) as f