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.

Answer 2

def merge_seg(s):
   index_i = 0
   while index_i+1<len(s):
      index_j=index_i+1
      while index_j<len(s):
         if c[index_i][-1] == c[index_j][0]:
            c[index_i].extend(c[index_j][1:])
            del c[index_j]
         elif c[index_i][-1] == c[index_j][-1]:
            c[index_i].extend(c[index_j].reverse()[1:])
            del c[index_j]
         else:
            index_j+=1
      index_i+=1
   result = []
   s.reverse()
   for seg_index in range(len(s)-1):
      result+=s[seg_index][:-1]#use [:-1] to delete the duplicate items
   result+=s[-1]
   return result

In inner while loop,every successive segment of s[index_i] is appended to s[index_i] then index_i++ until every segments is processed. therefore it is easy to proof that after these while loops, s[0][0] == s[1][-1], s[1][0] == s[2][-1], etc. so just reverse the list and put them together finally you will get your result.

Note: It is the most simple and straightford way, but not most time efficient.

for more algo see:http://en.wikipedia.org/wiki/Sorting_algorithm

Answer 3

You say that you can assume that all segments are in the right order, which means that independently of the coordinates order, your problem is basically to merge sorted arrays.

You would have to flip a segment if it's not defined in the right order, but this doesn't have a single impact on the main algorithm.

simply defind this reordering function:

def reorder(seg):
    s1 = min(seg)
    e1 = max(seg)
    return (s1, e1)

and this comparison funciton

def cmp(seg1, seg2):
    return cmp(reorder(seg1), reorder(seg2))

and you are all set, just run a typical merge algorithm:

http://en.wikipedia.org/wiki/Merge_algorithm

And in case, I didn't really understand your problem statement, here's another idea:

Use a segment tree which is a structure that is made exactly to store segments :)