2

I'm trying to join the nearest points within a group to create a line layer. I have the points, unique ids per point, and the grouping ids.

This question seems very easy or at least should have been answered before now but I just can't find a solution to it. This question was asked in 2015 but no answer has been provided - How to order points along a line?

I have tried to implement the solutions from here and tried to use Points to path but my points are not ordered so it doesn't work. When using Points to Path and using the group id as the Path group expression I get the attached screenshot where some lines are good, they just connect to the nearest points but then other lines are created that do not join the nearest points to one another.enter image description here I have double checked the points to make sure they are under the same group id and they are.

I have also tried to implement the solution from here, which uses geometry by expression using a Distance matrix but it doesn't join the correct points. I used the code

make_line (geometry ( get_feature_by_id( 'Centroids_aa787be7_c4bb_4ff5_96a9_d0075ff72b9a', "InputID")), geometry (get_feature_by_id('Centroids_aa787be7_c4bb_4ff5_96a9_d0075ff72b9a', "TargetID"))) which results in this:

enter image description here

Ideally I would like to be able to just order my points within each grouping and use Points to Path all in QGIS but I can't figure out a way to do so. Does anyone have a solution to either order (not just number) points within a group or an alternative solution that allows me to join nearest points within a group? Currently running QGIS version 3.32.3

Walshe_d
  • 729
  • 5
  • 19
  • Would manually drawing a line nearby the points be an option so that points can be ordered according to their position on that line? Can you share sample data? – Babel Oct 25 '23 at 06:46
  • Manually drawing the lines is not an option as this is just a subset of the data, I have millions of points. Here is a link to the data - https://drive.google.com/drive/folders/1MrKK2qTdChj5wLkuFFXw80QmF2UlfsrF?usp=sharing . You should be able to download the shapefiles, if not please let me know. – Walshe_d Oct 25 '23 at 15:22

1 Answers1

2

Your problem is pretty much equivalent to creating the shortest line between all the points in each group.

This in turn is a variation on the Travelling Salesman Problem, which is well-known in mathematical (and geographical) circles!

Unfortunately it's a computationally expensive problem. How expensive will depend on the maximum number of points there are in your groups.

I selected the points in one (larger) group from your sample data - ~170 points - and ran the TravellingSalesmanProblem tool from WhiteboxTools (separate plugin install) and got the following output. You could develop PyQGIS code that could automate this for all the groups if desired.

enter image description here

There's obviously a final step to remove the longest link between any two points, but in the whole scheme of things that's fairly trivial.

Tom Brennan
  • 4,787
  • 6
  • 26