5

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.

enter image description here

  • 2
    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... – Jendrusk Mar 2 '17 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. – michael Mar 2 '17 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... – Jendrusk Mar 2 '17 at 14:13
  • This is called minimum spanning tree. Easy thing if you can use Python networkX module – FelixIP Mar 2 '17 at 18:27
2

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. – michael Mar 2 '17 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. – Jendrusk Mar 2 '17 at 21:10
1

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? – michael Mar 2 '17 at 12:58
  • 1
    I have added a solution to the answer. – Dylan Hamilton Mar 2 '17 at 14:36
  • It's working but the result is still lines connected not the nearest points – michael Mar 2 '17 at 14:57
  • What does the result look like? – HeikkiVesanto Mar 2 '17 at 15:03
  • 1
    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. – Dylan Hamilton Mar 2 '17 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.