创建线连接公共点

Question

我有一个坐标列表，我想从这些点创建一个链（线），例如 输入

[
  [
    ((1, 1), (2, 3)), ((1, 1), (3, 4))
  ],
  [
    ((2, 3), (6, 6)), ((3, 4), (7, 8))
  ],
  [
    ((7, 8), (9, 9)), ((6, 6), (9, 10)), ((6, 6), (7, 9))
  ],
  [
    ((11, 11), (12, 13))
  ]
]

我想创建一个链，在这里我们有共同点，例如在上面的输入中，我们有共同点。你知道吗

输出：我想收集所有这样的公共坐标点，并从中取出一个积来创建多条候选线，例如

# expected outputs from above input
out1 = [((1, 1), (2, 3))] X [((2, 3), (6, 6))] X [((6, 6), (9, 10)), ((6, 6), (7, 9))]
out2 = [((1, 1), (3, 4))] X [((3, 4), (7, 8))] X [((7, 8), (9, 9))]

# will take product for combinations, which results in-
# for out1
= [((1, 1), (2, 3)), ((2, 3), (6, 6)), ((6, 6), (9, 10))]
= [((1, 1), (2, 3)), ((2, 3), (6, 6)), ((6, 6), (7, 9))]

任何指针，伪代码！你知道吗

---

我的尝试#1 适用于前2个列表项：（不确定如何在完整列表中扩展它

def pairs(ps):
    for i in range(1, len(ps)):
        yield (ps[i - 1], ps[i])

ls = [
    [((1, 1), (2, 3)), ((1, 1), (3, 4))],
    [((2, 3), (6, 6)), ((3, 4), (7, 8))],
    [((7, 8), (9, 9)), ((6, 6), (9, 10)), ((6, 6), (7, 9))],
    [((11, 11), (12, 13))],
]

master_list = []
for l in pairs(ls[:2]): # take fist 2 sub-list
    for k, v in groupby(sorted(l[0], key=lambda t: t[1]), key=lambda t: t[1]):
        new_ls = []
        t = [p for p in l[1] if p[0] == k]
        if t:
            new_ls.append(list(v))
            new_ls.append(t)
        master_list.append(new_ls)

gls = []
for m in master_list:
    for l in list(product(*m)):
        gl = nx.Graph() 
        print("Candidate Line: ", l)
        gl.add_edges_from(l)
        gls.append(gl)

nx.draw_networkx(gls[0])

输出

Candidate Line:  (((1, 1), (2, 3)), ((2, 3), (6, 6)))
Candidate Line:  (((1, 1), (3, 4)), ((3, 4), (7, 8)))

Answer 1

[E_0, ... E_n]的每个元素都是边的列表。如果可能的话，您希望将列表E_k中的边u, v连接到下一列表E_{k+1}中的边v, w。对于每个列表E_k，可以存储列表F_k中的自顶点和列表T_k中的至顶点。如果vertice在T_k和F_{k+1}中，则是您定义的公共点：

Es = [
    [((1, 1), (2, 3)), ((1, 1), (3, 4))],
    [((2, 3), (6, 6)), ((3, 4), (7, 8))],
    [((7, 8), (9, 9)), ((6, 6), (9, 10)), ((6, 6), (7, 9))],
    [((11, 11), (12, 13))],
]

Fs = [set(e[0] for e in E) for E in Es]
Ts = [set(e[1] for e in E) for E in Es]

commons = set(t for v, u in zip(Ts, Fs[1:]) for t in v & u)
# set([(3, 4), (2, 3), (7, 8), (6, 6)])