I am struggling with this problem. I have a polyline made up of several segments. Each segment is made up of points, each point identified in 3D space by coordinates and elevation. Together, if plotted, the segments make up a more or less continuous line (there could be breaks between segments), but the segments themselves are not consecutive, nor do the points of all segments follow the same direction of travel.
The question is: how can I create, using Python preferably, a single line from these non-consecutive segments so that I can measure the distance between points and the total length of the line.
I don't even know which of the segments is the first one or the last one in the line, but somehow I have to put them in the right sequence and make sure they all point in the same direction so I can measure them.
thank you for any assistance. I'll be happy to supply additional info, data, etc..
I stress I am not asking for the actual python code (not that I would refuse it…), just the strategy.
Bob
[GIS] Joining lines when direction is not known
polyline-creationpython
Best Answer
The segments can be used to form an abstract graph G in which they play the role of nodes. Consider a node that is the segment (arc) from point P to point Q, PQ. Let R be the closest endpoint among all the other segment endpoints to P and let S be the other endpoint of R's segment. G then contains an edge from node PQ to node RS and we will label this edge with the points P and R.
If we are to be successful, then G is either a linear graph or a single cycle. You can detect which is which by storing the degrees of the nodes as you create the edges. (The degree of a node counts the edges emanating from that node.) All nodes, except possibly two of them, must have degree 2. The other two must both have degree 2 (for a cycle) or degree 1: this marks them as the ends of the polyline. In the first case pick any node to start constructing the polyline; in the second case, pick one of those of degree 1. Any other combination of degrees is an error.
The polyline is initialized to the starting node (an arc). Look at one of the edges e incident on this node: its other node tells you which arc to process next and its label tells you which vertices of those arcs to join. (Join the vertices with a new line segment if they do not have identical coordinates.) Update the growing polyline in this fashion and, at the same time, remove edge e from the graph G. Continue until either an error occurs (and report that the edges do not form a non-branching connected polyline) or all edges are removed. If no error is raised, output the polyline you created.
Example
In the figure the arcs are AB, CD, EF, and FG. The nodes of the graph are therefore {AB, CD, EF, FG}. The edges are AB--CD (labeled with B and C), CD-EF (labeled with E and F), and EF--FG (labeled with F and F). The degrees of AB and FG are 1 whereas the degrees of CD and EF are 2. Here is a schematic of the abstract graph and its edge labels:
Let us arbitrarily start with FG, one of the degree-one nodes. Because it has degree 1, there is a unique edge EF--FG connected to it, labeled with F. Initialize the polyline with arc G-->F. Because the label designates a common endpoint of GF and EF, we don't have to make a new connection. Remove edge EF--FG from the graph and extend the polyline with EF via G-->F-->E.
This edge removal reduces the degree of EF from 2 to 1, leaving it with a single edge to arc CD labeled with E and D. This tells you to extend the polyline from E to D (with a new line segment there) and thence along arc CD: G-->F-->E-->D-->C. In the same manner, after removing edge ED--CD, you will extend the polyline further to its final form G-->F-->E-->D-->C-->B-->A. You stop because all edges have been removed from the graph: this indicates the procedure was successful.