有序线串方向算法

Question

我想在python中构建一个算法来翻转linestring集合中的linestring（坐标数组），它代表一条道路上的线段，这样我就可以将所有坐标合并到一个坐标单调上升的数组中。在

所以我的Segmentcollection看起来像这样：

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

编辑：所以这个结构是二维笛卡尔坐标元组的列表（“1,1”例如x=1和y=1的点，“7,10”是x=7和y=10的点，依此类推）。整个问题是将所有这些列表合并到一个坐标元组的列表中，这些元组按照沿着一条道路的方向排列……事实上，这些是我从道路网络路由服务中获得的段，但我只得到段，其中每个段都是按数据库中数字化的方式定向的，不要往你必须开的方向开。我想得到一个单一的多段线的导航路线从它。在

所以： -我可以假设，所有的片段都是按正确的顺序排列的 -I不能假设每个线段的坐标顺序正确 -因此，我也不能假设第一段的第一个坐标是起点 -我也不能假设最后一段的最后一个坐标是终点 -我认为这些元组在我的导航元素的某个地方是相同的，因为它们在某个地方是相同的。在

该算法应该迭代每个段，如果需要，将其翻转，然后将其附加到结果数组中。对于第一段，挑战是找到起点（与下一段没有连接的点）。然后，所有其他的线段用一个点按顺序连接到最后一个线段（有向图）。在

我想知道是否有某种排序数据结构（排序树或任何东西）能做到这一点。你能给我一些建议吗？在把循环和数组比较搞得一团糟之后，我的大脑被打昏了，我只需要一个真正意义上的正确方向。在

Answer 1

你说你可以假设所有的段都是正确的顺序，这意味着独立于坐标顺序，你的问题基本上是合并排序的数组。在

如果没有按正确的顺序定义一个段，就必须翻转它，但这对主算法没有任何影响。在

只需定义此重新排序函数：

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

这个比较函数呢

^{pr2}$

一切就绪，只需运行一个典型的合并算法：

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

我真的不明白你说的另一个问题：

使用一个segment tree，这是一个专门用来存储段的结构：）

Answer 2

如果我理解正确的话，你甚至不需要分类。我刚把你的英文文本翻译成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

它仍然包含重复的点，但是删除那些应该很简单。在

Answer 3

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

在内部while循环中，s[index_i]的每个连续段都附加到s[index_i] 然后索引_i++直到每个段都被处理。 因此很容易证明，在这些while循环之后，s[0][0]==s[1][1]，s[1][0]==s[2][1]，等等。所以只要把列表倒过来，把它们放在一起，你就会得到结果。在

注意：这是最简单、最直接的方法，但不是最省时的。在

有关更多算法，请参见：http://en.wikipedia.org/wiki/Sorting_algorithm