对线阵列进行排序，以使顶点中的点相连

Question

我有一系列的线。每条线与另一条线正好相连，这意味着它们共享顶点中的同一点。阵列示例：

((31,10),(48,50))
((20,33),(10,20))
((48,50),(60,81))
((10,20),(31,10))

这里的问题是数组被洗牌了。我想对它进行排序，使第1行的第2点与第2行的第1点相同。排序后的数组应如下所示：

((20,33),(10,20))
((10,20),(31,10))
((31,10),(48,50))
((48,50),(60,81))

我的想法是这样的——用每一行检查每一行。找到与另一条线共享同一点的线时，请将其放置在第一条线之前或之后的新阵列中，具体取决于它们在起点还是终点共享一点

def sortLines():
    sortedLines = []
    for line1 in lines:
        if line1 not in sortedLines:
            sortedLines.append(line1)
        for line2 in lines:
            if line2 not in sortedLines:
                if line1.p1.equals(line2.p2): #If the beginning of line1 is connected to the end of line2
                    sortedLines.insert(sortedLines.index(line1), line2)
                if line1.p2.equals(line2.p1): #If the end of line1 is connected to the beginning of line2
                    sortedLines.insert(sortedLines.index(line1)+1, line2)
    return sortedLines

但是，这只起到部分作用-端点已连接，但线仍然没有按应有的顺序排序

((10,20),(31,10))
((31,10),(48,50))
((48,50),(60,81))
((20,33),(10,20))

有人知道我可能做错了什么吗

Answer 1

可以使用字典映射直线的起点和终点坐标。起始点是键，而不是字典中的值

lines = [((31,10),(48,50)),
         ((20,33),(10,20)),
         ((48,50),(60,81)),
         ((10,20),(31,10))]

d = dict(lines)

sorted_lines = []
start = next(iter(d.keys() - d.values()))
while start in d:
    end = d[start]
    sorted_lines.append((start, end))
    start = end

print(sorted_lines)

给出（为可读性插入一些换行符后）：

[((20, 33), (10, 20)),
 ((10, 20), (31, 10)),
 ((31, 10), (48, 50)),
 ((48, 50), (60, 81))]

行中：

start = next(iter(d.keys() - d.values()))

键和值的行为类似于集合，因此差分用于提取应该是1元素集的内容，该元素集包含不也是值的键。next(iter(...))用于从集合中提取单个成员

---

如果要支持直线可能形成多边形的可能性，请替换：

start = next(iter(d.keys() - d.values()))

与：

try:
    start = next(iter(d.keys() - d.values()))
except StopIteration:
    sorted_lines.append(lines[0])
    del d[lines[0][0]]    
    start = lines[0][1]

在这种情况下，它将手动将第一行添加到输出中，并将其从字典中删除，然后从下一行开始执行其余的算法。输入的示例：

lines = [((31,10),(48,50)),
         ((20,33),(10,20)),
         ((60,81),(20,33)),
         ((48,50),(60,81)),
         ((10,20),(31,10))]

给出：

[((31, 10), (48, 50)),
 ((48, 50), (60, 81)),
 ((60, 81), (20, 33)),
 ((20, 33), (10, 20)),
 ((10, 20), (31, 10))]

Answer 2

您可以将lines列表显示为图形。每个点是一个顶点，每个线段（两个点）是一条边。您知道图形是连接的（线段是连接的）@阿莱维的想法是：

1. 要将图形表示为adjacency list，并且每个顶点最多有一个neightbor，则
2. 首先搜索不是相邻顶点的顶点，并跟随邻接列表直到其结束

这里还有另一个想法：图形非常具体，因为几乎每个顶点都有一个左邻居和一个右邻居。只有最左侧的顶点没有左邻居，而最右侧的顶点没有右邻居。要获得有序的线段，只需从任何顶点开始，然后将左顶点添加到左顶点，将右顶点添加到右顶点。（这类似于二叉树的顺序遍历。）

有一个可选的检查：如果我们在顶点上循环，那么我们有一个多边形

def order_segments(lines):
    def in_order(start):
        L = [start]
        e = left.get(start) # None if there is no left vertex
        while e != None:
            L.insert(0, e)
            e = left.get(e)

            if e == start: # optional: check for a polygon
                L.insert(0, e) # complete the polygon
                return L
                
        e = right.get(start) # None if there is no right vertex
        while e != None:
            L.append(e)
            e = right.get(e) # None if there is no right vertex

        return L

    # build the tree
    left = {}
    right = {}
    for e1, e2 in lines:
        right[e1] = e2
        left[e2] = e1

    start = lines[-1][0] # any vertex would be ok
    L = in_order(start) # the ordered vertices
    return list(zip(L, L[1:])) # build the segments

lines = [((31,10),(48,50)),
         ((20,33),(10,20)),
         ((48,50),(60,81)),
         ((10,20),(31,10))]

print(order_segments(lines))
# [((20, 33), (10, 20)), ((10, 20), (31, 10)), ((31, 10), (48, 50)), ((48, 50), (60, 81))]

print(order_segments([((60, 81), (20, 33))] + lines)) # a polygon
# [((10, 20), (31, 10)), ((31, 10), (48, 50)), ((48, 50), (60, 81)), ((60, 81), (20, 33)), ((20, 33), (10, 20))]