0

我想在 python 中构建一个算法来翻转线串集合中的线串（坐标数组），这些线串表示沿道路的线段，以便我可以将所有坐标合并到一个坐标单调上升的数组中。

所以我的 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，以此类推）。整个问题是将所有这些列表合并到一个坐标元组列表中，这些坐标元组在沿着一个方向沿着道路的意义上是有序的……事实上，这些是我从道路网络路由服务中获得的段，但我只得到细分市场，每个细分市场都按照它在数据库中的数字化方式进行定向，而不是按照您必须驾驶的方向。我想从中获得一条用于导航路线的折线。

所以：-我可以假设所有段的顺序都正确-我不能假设每个段的坐标顺序正确-因此我也不能假设第一个段的第一个坐标是开始-我也不能假设最后一段的最后一个坐标是结束 - （编辑）即使我知道，我的导航请求的起点和终点位于哪里，这些不必与其中一个坐标元组相同这些列表，因为它们只需要在路由图元素附近的某个地方。

该算法应遍历每个段，如有必要，将其翻转，然后将其附加到结果数组中。对于第一段，挑战是找到起点（不连接到下一段的点）。然后，所有其他线段都通过一个点连接到顺序中的最后一个线段（有向图）。

我想知道是否没有某种排序数据结构（排序树或任何东西）可以做到这一点。你能给出一些想法吗？在用循环和数组比较搞砸了一段时间后，我的大脑被击倒了，我只需要真正意义上的朝着正确的方向前进。

4

3 回答 3

1

如果我理解正确，您甚至不需要对事物进行排序。我刚刚将您的英文文本翻译成 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

它仍然包含重复点，但删除这些点应该很简单。

于 2013-11-17T15:27:00.047 回答
1 
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] 然后 index_i++ 直到每个段都被处理。因此很容易证明在这些 while 循环之后，s[0][0] == s[1][-1]、s[1][0] == s[2][-1] 等。所以只需颠倒列表并将它们放在一起最后你就会得到你的结果。

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

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

于 2013-11-17T16:53:32.710 回答
0

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

如果没有以正确的顺序定义一个段，您将不得不翻转它，但这对主算法没有任何影响。

简单地定义这个重新排序函数：

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

这个比较函数

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

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

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

以防万一，我并没有真正理解您的问题陈述，这是另一个想法：

使用段树，它是一种完全用于存储段的结构:)

于 2013-11-11T17:35:06.570 回答