4

I'm using ArcGIS Pro and would prefer solutions using ArcPy, ArcMap, or ArcGIS Pro, but an open source alternative may work too.

I'm trying to construct a line from a series of points using the Points to Line tool. This works well if the points are all in some sort of order as given by the attributes table or their ObjectID; but if points are added out of order, the line is then constructed out of order as well, as seen in the image below after using Points to Line. The intended image looks like a smooth 'S' curve. (This is a simple example based off of more complex multiple points/lines.)

Line Doubles Back at A Point Instead of Continuing Smoothly

Sorting by latitude or longitude doesn't always work either, since the line meanders back at times.

How do I construct a line from points based off of something like nearest point?

JMNC
  • 197
  • 1
  • 10
  • 3
    Is there an ascending field to put the points into order? The points to line tool https://resources.arcgis.com/en/help/main/10.2/index.html#/Points_To_Line/00170000003s000000/ can sort the points but there needs to be something to sort by. Otherwise you could give http://desktop.arcgis.com/en/arcmap/10.3/tools/data-management-toolbox/how-sort-works.htm a go and see if it helps, I haven't used this tool so cannot testify to its efficacy. – Michael Stimson Dec 03 '19 at 00:31
  • I'll take a look at Sort (management), thanks! – JMNC Dec 03 '19 at 00:40
  • Sort (management) didn't work in my case, but it gave interesting results--basically zigzagged the line as if I'd sorted strictly by longitude or latitude. I may end up having to sort by longitude or latitude and then manually correct at places where the line doubles back. – JMNC Dec 03 '19 at 00:57
  • You could try using the near tool to find which points are closest to each point. You can run the near analysis on a single feature class and it will calculate distances between features. http://desktop.arcgis.com/en/arcmap/10.3/tools/analysis-toolbox/near.htm – jbalk Dec 03 '19 at 01:03
  • The Near tool identifies points between different feature classes that are closest to each other and then does a table join by matching unique IDs; it doesn't help draw a spatial line between them. Since it doesn't work within a single layer, I also wouldn't want to make a dozen different feature classes/layers if I have a dozen points that make up a line (let alone hundreds). It does give me hope that ArcGIS has the functionality to do what I need, though. – JMNC Dec 03 '19 at 01:13
  • 2
    You have to define the order. ArcGIS can only guess the order OR use an order that you define. If there is not already an attribute that defines the order, then you'll need to create one, and populate it yourself, either manually, or based on some criteria that can be calculated. Eg, you could write a script that would calculate the next nearest point, however, in my experience, this is not always the next intended point; you also need to calculate which is the first point to start at, which is not something that can be reliably done automatically. Then use points-to-line tool. – Son of a Beach Dec 03 '19 at 02:32
  • There are many potential "correct" paths in an unordered set of points. You'd need additional knowledge and a willingness to "save" the state of associations, to test if the decisions work, or branch off in a different direction. This could quickly become an NP Hard problem. – Vince Dec 03 '19 at 03:10
  • Thanks for the replies so far. The solution I'm currently working on is to create a new field that copies the existing line order (that is, by ObjectID or FID), but numbering stops at the original final object ID. Any additional points inserted 'between' other points (as will be the case with my lines) will be assigned some decimal ID in the new field based on the nearest latitude or longitude neighbors, so I just need to figure out a cursor script to detect that, then I can Points to Line. This isn't flawless and doesn't work on totally jumbled points, but it works for my lines in most cases. – JMNC Dec 03 '19 at 03:40
  • This is classic example of minimum spanning tree. – FelixIP Dec 03 '19 at 04:24
  • 1
    Do you have other features that overlap or are nearby that have attributes that are in order? If so I would consider Spatial Join. – Jacob Helfman Dec 18 '19 at 04:30

1 Answers1

3

Minimum spanning tree handles this very well, unless there are sharp turns < 90 degrees:

enter image description here

Output:

enter image description here

So:

  • triangulate points
  • extract edges
  • build undirected graph
  • compute it's MST

Networkx module does it with ease.

See script here.

FelixIP
  • 22,922
  • 3
  • 29
  • 61