Find intersection of 2 layers containing multiple lines (in python)

Question

I have 2 layers with links and nodes: layer A (yellow) and layer B (blue).

I would like to get the places where the lines of layer A intersect with the lines of layer B (red nodes), directly in python.

I have the coordinates for all nodes in both layers (the nodes of layers A and B are hidden in the image below).

I saw this option to find line intersection in python, but since layer A has approx. 23,000 lines and layer B 50,000, it would be too computational intensive to use it:

from shapely.geometry import LineString

line1 = LineString([(x1,y1), (x2,y2), (x3,y3)])
line2 = LineString([(x4,y4), (x5,y5)])

output = line1.intersection(line2)

Does anyone know a better (faster) way to get these intersection nodes?

Thanks a lot!

Answer 1

Okay, I can see what do you mean. I will try to explain a method to do this. You can easily do this by using brute force. But it's time consuming as you mentioned. Specially when there are thousands of nodes and edges. I can suggest a less time consuming method.

Let there are N nodes in layer 1 and M nodes in layer 2. Then for your method the time complexity is O(N*M)

My method. A moderately complex method. I can't implement code here. I will describe steps at the best level I can. You have to figure out how to implement in code. The Cons: May miss intersections

We use Localization in the graph. Otherwise we select (relatively) small windows from layers and perform the same thing you have done. Using shapely.

Ok, First we have to determine the window size we going to use.

1. determine the size of the rectangle which contains the all nodes in both layers
2. Divide it into small squares of same size.( like a square grid)
3. Build zero matrix equivalent to squares.
4. get count of nodes in each square and assign it to the related element in matrix. Which will have time complexity of O(N+M)
5. Now you have the density of nodes.
6. If density of a tile is high, Window size is small. (3x3 would be enough). The selected tile is at the middle. Since nodes are closer less chance to miss intersections. So perform your method on nodes inside selected tiles. Will have time complexity of O(n*m) where n,m are nodes inside the selected window.
7. If density of a tile is low, Window size is large. (5x5,7x7,9x9.... you can determine). The selected tile is at the middle.Since nodes are far away less chance to miss intersections. So perform your method on nodes inside selected tiles. Will have time complexity of O(n*m) where n,m are nodes inside the selected window.

How does this reduce the time. It will be prevented from comparing the nodes far away from the selected lines. If you have learned about time complexity, This is very efficient than your previous brute force approach. This is a little bit less accurate than your previous approach But faster.

ATTENTION : This is my method for select less number of nodes for comparison. There may be methods much more faster and accurate than my solution. But most of them will be very complex. If you are worried about the accuracy use your method or look for much faster and accurate method. Else you can use mine.

IN ADDITION : You can determine window size using the line length instead of using node density. No need to draw a grid. Select large window around a line if the line is long. If short , Use small window. This is also faster. I think This will be much more accurate than my previous method.