"Merging" 2 layers of LineString with splits at intersections

Question

I would like to "merge" 2 networks of lines and these lines need to be split when they intersect. With pictures it should be clearer :

What to do:

• if a black line intersects a red line, they should be split
• a line can be split in more than 2 parts
• I would like to keep line IDs (for example, a red_line_001 can be split into red_line_001_01 + red_line_001_02 + red_line_001_03)

Restrictions:

• each network may have more than 100000 lines
• the algorithm should be efficient
• I need to do it in Python
• If possible, I would like to use Shapely, OGR-GDAL and/or Fiona
• If possible, it should work with more than 2 networks

I already did this work with PostGIS and it was quite efficient (but not generic and worked only for 2 networks). I do not want you to solve this problem for me, I just need some hints and advice about what is the best solution to my problem.

Answer 1

I somehow have to deal with a similar issue in hydrology. Below is what I did to resolve it:

1. Obtain all the start and end vertices of each line, and save the vertices in table A
2. Intersect all the lines with each other to get all the intersection vertices, and save them in table B
3. Combine A and B to get the larger table C which has all the vertices
4. Split all the lines using table C. There are different ways to do so. For example, in a 2D case, if a point is exactly on a line, this line can be split into two parts. You can keep the line ID in this step.
5. You can classify vertices using how many split lines they are connected to.