CODEWITHSUNDEEP
pythonlist
DodoDude700
DodoDude700

Reputation: 165

Group elements based on condition in Python

I have a list of line segments, each with x and y coordinates of their "from" and "to" points, as seen below (example below is truncated, it's quite long).

[
{'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}},
...
]

I also have a function, lines_connected, which takes two of these list items (lines) as its a and b parameters, and returns True if the end of either line is on some part of the other (but False if they just intersect without one ending at the other, or if they don't "touch" at all). Using this, I need to find all groups (presumably as lists within a list) of lines which "connect" as described above. Not every line within a group is necessarily connected directly to every other line, but they are connected via other lines in the group.

What is the best way to group these lines into these "connected groups"?

Upvotes: 2

Views: 702

Answers (2)

Mad Physicist
Mad Physicist

Reputation: 114578

This is a graph problem. You can convert your list into a networkx graph pretty easily, with your endpoints being the nodes and segments being edges:

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)

For reference, I've added an obj attribute to each edge, which points to the original dict used to construct it.

Now to get the groups, all you have to do is get the connected components of the graph: The edges within each component will be interconnected segments. These can be obtained according to the description of the deprecated connected_component_subgraphs method:

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

To check if any two points are connected somehow, just check if there's a path from the starting point of one to the other, as here:

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

It does not matter if you use f or t for the endpoints.

Upvotes: 1

HakunaMaData
HakunaMaData

Reputation: 1321

One way of doing this would be to use a network based approach. You could use networkx for this.

In this setup each line segment would be a node and the output of lines_connected will determine whether there is an edge between them or not. So, if lines_connected spits out True for any two segments a and b then you can create an edge between two nodes. Else you don't.

Finally you get the "connected groups" by using connected subcomponent graphs as in

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)

Upvotes: 2

Related Questions