Skip to main content
 首页 » 编程设计

python之查找坐标列表是否形成循环

2024年11月24日12TianFang

所以我有一个点列表,这些点通常形成一种圆形形状,除了通常很少有来自圆的分支,这些分支基本上只是从圆的边界向某个方向延伸的线。我想创建一个函数,当给定这个坐标/点列表时,它会发现在这组点中是否存在完整路径。

我想过创建一个起点并找出是否存在不重复点的路径(即 (1,1) -> (2, 1) -> (1,1) 不允许)并且可以回到起点;但是,如果起点位于圆的分支中,则此方法无效。

例如,坐标列表

[[0, 0], [0, 1], [1, 2], [2, 3], [3, 3], [3, 4], [4, 4], [3, 2], [3, 1], [3, 0], [2, -1], [1, -1], [0, -1]]  

会形成一个完整的路径,而如果我去掉 [1, -1] 它就不会形成一个完整的路径。

请您参考如下方法:

您正在寻找的是 simple cycle .图论包 networkx 提供了一种在 simple_cycles 中查找那些的方法.我们需要做的只是一点点腿部工作来设置图表:

import networkx as nx 
 
def has_simple_cycle(l, start): 
    G = nx.DiGraph() 
    G.add_edges_from((v1, v2) for v1 in l for v2 in l if v1 != v2 and max(abs(v1[0] - v2[0]), abs(v1[1] - v2[1])) <= 1) 
    return any(start in c and len(c) > 2 for c in nx.simple_cycles(G)) 

在你给出的例子中:

In [26]: has_simple_cycle(l=[(0, 0), (0, 1), (1, 2), (2, 3), (3, 3), (3, 4), (4, 4), (3, 2), (3, 1), (3, 0), (2, -1), (1, -1), (0, -1)], start=(0, 0)) 
Out[26]: True 
 
In [27]: has_simple_cycle(l=[(0, 0), (0, 1), (1, 2), (2, 3), (3, 3), (3, 4), (4, 4), (3, 2), (3, 1), (3, 0), (2, -1), (0, -1)], start=(0, 0)) 
Out[27]: False