Ordering linestring direction algorithm

Question

I want to build an algorithm in python to flip linestrings (arrays of coordinates) in a linestring collection which represent segments along a road, so that I can merge all coordinates into a single array where the coordinates are rising monotonic.

So my Segmentcollection looks something like this:

segmentCollection = [['1,1', '1,3', '2,3'],
                     ['4,3', '2,3'],
                     ['4,3', '7,10', '5,5']]

EDIT: SO the structure is a list of lists of 2D cartesian coordinate tuples ('1,1' for example is a point at x=1 and y=1, '7,10' is a point at x=7 and y=10, and so on). The whole problem is to merge all these lists to one list of coordinate tuples which are ordered in the sense of following a road in one direction...in fact these are segments which I get from a road network routing service,but I only get segments,where each segment is directed the way it is digitized in the database,not into the direction you have to drive. I would like to get a single polyline for the navigation route out of it.

So: - I can assume, that all segments are in the right order - I cannot assume that the Coordinates of each segment are in the right order - Therefore I also cannot assume that the first coordinate of the first segment is the beginning - And I also cannot assume that the last coordinate of the last segment is the end - (EDIT) Even thought I Know,where the start and end point of my navigation request is located,these do not have to be identical with one of the coordinate tuples in these lists,because they only have to be somewhere near a routing graph element.

The algorithm should iterate through every segment, flip it if necessary, and append it then to the resulting array. For the first segment,the challenge is to find the starting point (the point which is NOT connected to the next segment). All other segments are then connected with one point to the last segment in the order (a directed graph).

I'd wonder if there isn't some kind of sorting data structure (sorting tree or anything) which does exactly that. Could you please give some ideas? After messing around a while with loops and array comparisons my brain is knocked out, and I just need a kick into the right direction in the true sense of the word.

Answer 1

If I understand correctly, you don't even need to sort things. I just translated your English text into Python:

def joinSegments( s ):
    if s[0][0] == s[1][0] or s[0][0] == s[1][-1]:
        s[0].reverse()
    c = s[0][:]
    for x in s[1:]:
        if x[-1] == c[-1]:
            x.reverse()
        c += x
    return c

It still contains duplicate points, but removing those should be straightforward.