CODEWITHSUNDEEP
pythongraphnetworkx
Dean Taler
Dean Taler

Reputation: 773

How check if there is intersection of any two edges given the fixed nodes positions, assuming the edges are drawn as straight lines with networkx?

What I want?

I want to check if there is any interscions beteewn edges in my graph. I have a graph with a lot of vertices and edges.

Here is a simple graph for example:

    G = nx.Graph().to_undirected()
    G.add_nodes_from(pos)
    G.add_edge(1, 3, weight=1)
    G.add_edge(2, 4, weight=1)
    G.add_edge(2, 3, weight=1)
    nx.draw_networkx(G, with_labels=True, pos=pos)
    plt.show()

Graph

What I have tried?

I already tried to use

    print(nx.check_planarity(G, False))

but because there is an option to draw this graph as a planar graph, the return value is True

How can I check if there are edge interscions in my graph? assuming the position is fixed and the edges are drawn as straight lines

Upvotes: 0

Views: 1364

Answers (2)

Bera
Bera

Reputation: 1949

You can use Shapely:

Create linestrings using the coordinates and save as edge attributes, then iterate over each pairwise combination of edges and check if they cross, if they do calculate their intersection point.

import networkx as nx
from shapely import LineString
from shapely.plotting import plot_points
from itertools import combinations
import matplotlib.pyplot as plt


#Create a graph and create a line using the node coordinates and store as the geometry attribute
G = nx.Graph()
positions = {1:(0,0),
             2:(0,5),
             3:(5,5),
             4:(5,0)}
G.add_edge(1, 3, weight=1, geometry=LineString([positions[1], positions[3]]))
G.add_edge(2, 4, weight=1, geometry=LineString([positions[2], positions[4]]))
G.add_edge(2, 3, weight=1, geometry=LineString([positions[2], positions[3]]))


fig, ax = plt.subplots(nrows=1, ncols=1, figsize=(8,8))
nx.draw(G, pos=positions, with_labels=True, ax=ax, font_color="whitesmoke")


#For each pair of nodes, check if they cross and if they do calculate their intersection point
intersections = []
for e1, e2 in combinations(G.edges(data=True), 2):
    line1 = e1[-1]["geometry"]
    line2 = e2[-1]["geometry"]
    if line1.crosses(line2):
        intersections.append(line1.intersection(line2))
        #If you only want to check if any line intersects any other 
        #  your can add a break here.

for point in intersections:
    plot_points(geom=point, ax=ax, color="red", markersize=10, marker="P")

enter image description here

Upvotes: 0

kirogasa
kirogasa

Reputation: 949

NetworkX does not have this function, you need to implement it yourself (How can I check if two segments intersect?) or take it from another library (for example from Shapely).

Upvotes: 0

Related Questions