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

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

2 Answers 2

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.

2
  • 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
    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.
    – Jendrusk
    Commented Mar 2, 2017 at 21:10
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
7
  • But how can I write the query? ST_ClosestPoint(geometry g1, geometry g2), who is my g1 and g2?
    – michael
    Commented Mar 2, 2017 at 12:58
  • 1
    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
    – michael
    Commented Mar 2, 2017 at 14:57
  • What does the result look like? Commented Mar 2, 2017 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. Commented Mar 2, 2017 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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