Группировать элементы на основе условий в Python

Question

У меня есть список отрезков, каждый с координатами x и y их точек «от» и «до», как показано ниже (пример ниже урезан, он довольно длинный).

[
{'f': {'x': 15.0, 'y': -5.0}, 't': {'x': 16.0, 'y': -5.0}},
{'f': {'x': 3.0, 'y': -7.0}, 't': {'x': 5.0, 'y': -7.0}},
{'f': {'x': 9.0, 'y': -7.0}, 't': {'x': 10.0, 'y': -7.0}},
{'f': {'x': 10.0, 'y': -4.0}, 't': {'x': 10.0, 'y': -5.0}},
{'f': {'x': 9.0, 'y': -4.0}, 't': {'x': 10.0, 'y': -4.0}},
{'f': {'x': 4.0, 'y': -4.0}, 't': {'x': 5.0, 'y': -4.0}},
...
]

У меня также есть функция lines_connected, которая принимает два из этих элементов списка (строк) в качестве параметров a и b и возвращает True, если конец любой строки находится в некоторой части другой (но False, если они просто пересекаются без одного конца на другом, или если они вообще не "касаются"). Используя это, мне нужно найти все группы (предположительно в виде списков в списке) линий, которые «соединяются», как описано выше. Не каждая линия в группе обязательно связана напрямую с любой другой линией, но они связаны через другие линии в группе.

Как лучше всего сгруппировать эти строки в эти «связанные группы»?

Answer 1

Это проблема с графиком. Вы можете довольно легко преобразовать свой список в график networkx , а ваши конечные точки будут узлами, а сегменты - ребрами:

import networkx as nx

def to_xy(p, key='f'):
    d = p[key]
    return (d['x'], d['y'])

segments = [...]
g = nx.Graph()
for seg in segments:
    g.add_edge(to_xy(seg, 'f'), to_xy(seg, 't'), obj=seg)

Для справки, я добавил атрибут obj к каждому ребру, который указывает на исходный дикт, использованный для его построения.

Теперь, чтобы получить группы, все, что вам нужно сделать, это получить связанных компонентов графика: ребра внутри каждого компонента будут взаимосвязанными сегментами. Они могут быть получены в соответствии с описанием устаревшего connected_component_subgraphs метода:

components = map(g.subgraph, nx.connected_components(g))
edges = [list(nx.get_edge_attributes(sg, 'obj').values()) for sg in components]

Чтобы проверить, связаны ли какие-либо две точки каким-либо образом, просто проверьте, существует ли путь от начальной точки одной к другой, как здесь :

nx.has_path(g, to_xy(s1), to_xy(s2))

Не имеет значения, используете ли вы f или t для конечных точек.

Answer 2

Один из способов сделать это - использовать сетевой подход. Для этого вы можете использовать networkx .

В этой настройке каждый сегмент линии будет узлом, и вывод lines_connected будет определять, есть ли граница между ними или нет. Таким образом, если lines_connected выплевывает True для любых двух сегментов a и b, то вы можете создать ребро между двумя узлами. Иначе нет.

Наконец, вы получаете «связанные группы», используя связанные подкомпонентные графы, как в

import networkx as nx
#G would be your Node-Edge Graph created with line segments and the outuput of lines_connected 
sub_graphs = nx.connected_component_subgraphs(G)