I’m developing a program to find the shortest path in an infrastructure network. I’m overlaying road and sewage grids (as lists of LineString objects, etc.), all in EPSG:2180 format. I then perform a “snap to grid” operation on these grids. The grids are passed to an algorithm that identifies intersection points of the LineStrings, and it returns a list of split LineStrings, which I then use to create a graph. The intersection points are added as nodes.

The problem is that, in many cases, the added node turns out to be an isolated node. I suspect this is due to precision issues in the calculations with one of the libraries. I’m using networkx and shapely. What can I do to ensure the nodes are placed exactly at the edge intersection points?

red dot – node which should be intersection
green and orange line – road and sewage grids

My code:

def find_intersection_points_on_list_of_linestrings(line_groups):
    # List for intersection points
    intersection_points = []

    # Combine all lines from the groups into a single list
    all_lines = []
    for group in line_groups:
        all_lines.extend(group)

    # Iterate through all combinations of LineString pairs
    for i, line1 in enumerate(all_lines):
        for j, line2 in enumerate(all_lines):
            # Ensure not to compare the same LineString
            if i < j:
                # Check for line intersection
                intersection = line1.intersection(line2)
                # If the intersection is a point, add it to the result list
                if isinstance(intersection, Point):
                    intersection_points.append(intersection)
                # If the intersection is a MultiPoint, add all points as well
                elif intersection.geom_type == 'MultiPoint':
                    intersection_points.extend(intersection.geoms)

    return intersection_points

def add_points_as_nodes(graph, points):
    """
    This function adds nodes to the graph based on a list of Shapely Point objects,
    converting them into tuples (x, y).
    
    :param graph: A graph object from networkx (e.g., nx.Graph())
    :param points: A list of Shapely Point objects
    """
    for index_, point in tqdm(enumerate(points), total=len(points), desc="Adding nodes"):
        # Check if the point has x and y attributes (if it's a Point object from Shapely)
        if hasattr(point, 'x') and hasattr(point, 'y'):
            # Add the tuple (x, y) as a node to the graph
            graph.add_node((point.x, point.y))
        else:
            raise ValueError(f"Unsupported point type: {point}")

I tried using shapely to find the intersection points of the LineStrings and then splitting the LineStrings at those points. I expected that after splitting the LineStrings and adding the intersection points as nodes to the graph, all nodes would be correctly connected. However, I’m noticing that some nodes are isolated, indicating they are not properly connected to the corresponding edges, likely due to precision issues during the intersection and splitting process.