Create nodes at edge intersections

[tomalrussell]

No description provided.

[tomalrussell]

Notes towards this:

    intersection_node_geoms = []
    for edge in edges.itertuples(index=False):
        geom = edge.geometry
        candidate_idxs = list(edges.sindex.intersection(geom.bounds))
        candidates = n.edges.iloc[candidate_idxs]
        intersections = candidates.intersection(geom)
        for intersection in intersections:
            geom_type = intersection.geom_type
            if intersection.is_empty:
                continue
            elif: geom_type == 'Point':
                intersection_node_geoms.append(intersection)
            elif geom_type == 'MultiPoint':
                for point in intersection.geoms:
                    intersection_node_geoms.append(point)
            elif: geom_type == 'MultiLineString':
                for line in intersection.geoms:
                    start = Point(line.coords[0])
                    end = Point(line.coords[-1])
                    intersection_node_geoms.append(start)
                    intersection_node_geoms.append(end)
            else:
                print(intersection.geom_type)

    nodes = geopandas.GeoDataFrame(intersection_node_geoms, columns=['geometry'])

MultiLineString intersections happen when lines run almost-overlapping for a stretch.

[tomalrussell]

see argentina-transport preprocessing/network_road_topology

[jmon12]

Hi Tom,

New in the field of spatial networks, I've been searching into the related python ecosystem for network-oriented packages, and snkit is the only one partially implementing geometrical intersection based nodes creation.
It would be my pleasure to contribute by proposing an implementation of nodes creation from edges intersections.

After reading the code, I think the following would make sense. You already did most of the work with your notes above.

• A split_edges_at_intersections function on the model of split_edges_at_nodes function and your notes.
• A edges_intersecting function analog to nodes_intersecting
• Probably a corresponding test

I'll be implementing it and will make a PR if that makes sense to you. Any recommendation and advise is welcome. What do you think?

[tomalrussell]

Hi @jmon12 thanks for the message 🙂

Yes, a PR for this would be welcome.

Here's a bit more quick thinking about implementation details of split_edges_at_intersections:

1. Find edge-edge intersection points, based on my notes above (maybe check if the use of sindex needs updating to work with pygeos.STRTree)
2. Append those points as nodes to create a network_with_crossings (dropping/skipping duplicates if any were already in the nodes)
3. Split the edges (happy for you to think this through - it might be clearer once coding)
   • maybe reuse split_edges_at_nodes directly, calling it with that network_with_crossings, and we're done?
   • or would it be simpler and more efficient to do the edge-splitting in the for edge in edges.itertuples loop just after we've identified the edge's intersections?

Yes, a few tests would be welcome - try and exercise a couple of simple cases and any corner cases you can come up with:

• network with just two edges crossing like + .. output would have one node in the middle and four edges after splitting
• network already split neatly - no change
• network with lines exactly overlapping for a section, something like the below, where a-c is one straight LineString and b-d is a second LineString that overlaps exactly for the x-c portion. Should create nodes at x and c, and end up with edges a-x b-x x-c (twice) and c-d

    a
    |
b---x
    ||
    c----d

[jmon12]

Thank you for your advises!

I was actually trying to find a way to reuse split_edges_at_nodes, and your approach might do the job. The danger here would be that we snap non-intersection nodes to edges as well, which might not be desired. I think the effects of every function should be strictly bounded, even though such a side effect would be generally appreciated.

For the 2nd approach, since every iteration identifies all the intersections of a given edge, this should also give the correct topology.

For the corner cases, I think that the case of an edge crossing an end-point should be considered: should it be recognized as an intersection or not? This would make split_nodes_at_intersections enter the 'realm' of split_edges_at_nodes. And what about the buffering (tolerance) in that case...?

Anyway, further points and questions will come while coding, I'll keep you updated. As soon as I have something mature-enough, I'll open a PR for you to review. Have a nice evening!

[jmon12]

Hi @tomalrussell,

I just commited the first working version with a basic test. I will open a PR so you can have a first look and comment directly there, if that's alright with you. Every feedback is welcome since I'm not familiar with the tools at play.

I will do and implement the following tests:

• Check the output with a small dataset I'm familiar with
• Implement the other tests you suggested
• Implement a test for multiple intersections of the same line
• Implement a test for end-point crossing (which shouldn't lead to a split, if you agree with that.)

The main design question I think is the following. Since I'm creating new points at intersections, the internal _intersects_* returning indices of elements already inside the sindex cannot give me the actual intersection points. To overcome that, I see two possibilities:

1. Implement a parallel set of internal functions which would use shapely.object.intersection instead of geopandas.sindex.intersection.
2. Extract the actual intersection point from the received index of the sindex using shapely.object.intersection. This is done from the highest level function split_edges_at_intersections.

I chose the 2. option because it's less disruptive for the structure of your code. I might miss something here.

Potential issues:

• End-points crossing
• Self-crossing (not overlap): it actually make sense to split them in a topological sense, but would:
  • generate a self-loop edge: is it a problem for snkit?
  • need to refine the extraction of the intersection point

Concerning linting and coding style, I tried as much as possible to respect your style, but still:

• Let me know of any small details I should adapt: spacing, commenting style, ...
• Should I run some linting tool? Which one do you use?
• What about the documentation?

[tomalrussell]

Thanks for the draft PR, looks like a great start

I chose the 2. option

This makes sense to me - I generally use the sindex to quickly look up candidates then check whether they actually intersect

end points

See my comment on #51 - I wonder if end points should also cause edges to be split

self-crossing

A self-loop edge should be no problem for snkit, I agree it makes sense to split on self-crossing points

small details

All look good. The comments in line with the code are helpful notes on implementation detail 👍🏻

linting

I like black, though I wouldn't block on linting issues.

documentation

The docs are fairly lightweight - it would be cool to add an example to the demo notebook - and documentation comments will get picked up in the API reference

[czor847]

Just skimming through the above, if it's not already included, being able to restrict the node creation/line splitting to just those intersections of lines which share common attributes (along the same lines as by=[] in merge_edges) would be handy too.

i.e. for a road network, you wouldn't want nodes created where a tunnel happens to pass under local (ground level) roads. Likely the same for any other hierarchal network which could be at different 'levels' and/or elevations above/below ground?

[tomalrussell]

Hey @czor847 - yes, that would be useful related functionality, I'd say nice-to-have for this issue rather than essential. What do you reckon, @jmon12 ?

One approach would be to pass in a condition callable (lambda or function) that would get called for each pair of candidate edges, and return True/False, then the caller can apply whatever check they like. We do something similar in link_nodes_to_nearest_edge (network.py#L339-L340).

[jmon12]

@czor847 Yes that's definitely a nice feature, thank you for pointing it out. As you mentioned and for multilayer networks in general, it could do the job.
I will finish the basic implementation, hopefully robust enough and then look into it. Since I will be working with mutli-layer networks, it should be sooner than later.
@tomalrussell As always, thank you for your hint! Btw, I had more troubles than expected with self-crossings. I will update you on that tomorrow.