Checking if an edge in a graph intersects other edges

I have a 2D undirected network created using graph function in matlab (using the coordinates of the nodes). I want to add some edges to the network and check if these intersects other edges of the network. One way to do this is using the coordinates of the nodes forming the edges, checking for a point of intersection with each edge. But I think this would be compuatationally intensive for large networks. Is there a simpler way?

Answer 1

[Sameer]

Hi @Hari

Checking for edge intersections in a large 2D undirected network can indeed be computationally intensive, especially if you do it naively by comparing each new edge against all existing edges

Use spatial data structures like a "quadtree" or "R-tree" to divide the space into hierarchical sections. This allows you to quickly eliminate large sections of the network that cannot possibly contain intersecting edges.