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

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.

• You don't have any metadata on which you can sort your data (maybe some timestamp or sth else)? It's quite simple to write some anonymous block which will sort your data, most difficult will be to find first point of your line... Commented Mar 2, 2017 at 13:32
• @Jendrusk No I don't have any metadata. Of course when one look at the data the order seems to be obvious. Commented Mar 2, 2017 at 13:51
• yes, but for this points... what if you'll get four points as four corners of square? all distances are equal... I'll think about it... Commented Mar 2, 2017 at 14:13
• This is called minimum spanning tree. Easy thing if you can use Python networkX module Commented Mar 2, 2017 at 18:27

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.

• Well I'm happy to hear it's quite complex problem cause I was little bit embarrassed trying for several hours to find kind of one liner ready method solution, and was surprised ain't one. Commented Mar 2, 2017 at 20:07
• At least I didn't know one (simple one-liner), but it doesn't mean there is no such. :) I'll write sth tomorrow. Commented Mar 2, 2017 at 21:10

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
``````
• But how can I write the query? ST_ClosestPoint(geometry g1, geometry g2), who is my g1 and g2? Commented Mar 2, 2017 at 12:58
• I have added a solution to the answer. Commented Mar 2, 2017 at 14:36
• It's working but the result is still lines connected not the nearest points Commented Mar 2, 2017 at 14:57
• What does the result look like? Commented Mar 2, 2017 at 15:03
• Looking things over, it looks like you're correct. It did happen to work for my test dataset, but thats why I'm hoping he gives us his data. I'm still working on finding something else that will work. Commented Mar 2, 2017 at 18:36