Найти, если список координат образуют цикл - PullRequest
Новая
       48

Найти, если список координат образуют цикл

2 голосов
/ 06 апреля 2019

Итак, у меня есть список точек, которые обычно образуют некую круглую форму, за исключением того, что часто есть небольшие ответвления от круга, которые по сути являются просто линиями, скажем, от границы круга, идущего в определенном направлении. Я хочу создать функцию, которая при задании этого списка координат / точек определяет, существует ли полный путь в этом наборе точек.

Я думал о создании начальной точки и поиске того, существует ли путь, который не повторяет точки (то есть (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], он не будет формировать полный путь.

1 Ответ

1 голос
/ 06 апреля 2019

То, что вы ищете, это простой цикл .Пакет теории графов 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
...