How to Clean a Line Network: Dangles, Overshoots and Disconnects

Problem statement

The road network looks perfect on screen. The routing fails.

import networkx as nx
G = build_graph(roads)
nx.number_connected_components(G)      # 412 — should be 1

Four hundred and twelve disconnected islands in a network that a map shows as continuous. Zoom to 1:200 and the cause appears: two roads that meet at a junction stop 4 cm apart, so nothing connects. Another pair crosses without a node, so a vehicle cannot turn. A third has a 30 cm stub hanging off the end of a cul-de-sac that came from a digitising slip.

Polygon layers have coverage errors. Line layers have their own family, and none of them make a geometry invalid — every one of these lines passes is_valid.

Quick answer

Four defects, four checks, and they must be fixed in order:

Defect	What it is	Detect with	Fix
Dangle	an endpoint that touches nothing	endpoint appears once in the layer	snap if near a line, delete if a stub
Undershoot	a line stops short of the one it should meet	dangle within tolerance of another line	extend or snap
Overshoot	a line crosses past a junction	short segment beyond the last node	trim
Missing node	two lines cross with no shared vertex	`crosses` is True	node the network

import geopandas as gpd
from shapely.ops import unary_union, linemerge
from collections import Counter

TOL = 0.5      # metres — the largest gap that counts as "should have connected"

def endpoints(gdf):
    pts = []
    for geom in gdf.geometry:
        for line in getattr(geom, "geoms", [geom]):
            pts.append(line.coords[0])
            pts.append(line.coords[-1])
    return pts

def network_report(gdf, tol=TOL):
    counts = Counter(endpoints(gdf))
    dangles = [p for p, n in counts.items() if n == 1]
    crossing = gpd.sjoin(gdf, gdf, predicate="crosses")
    crossing = crossing[crossing.index != crossing.index_right]
    return {
        "features": len(gdf),
        "endpoints": len(counts),
        "dangles": len(dangles),
        "crossings_without_node": len(crossing) // 2,
        "total_length_m": round(gdf.geometry.length.sum(), 1),
    }

print(network_report(roads))
# {'features': 18402, 'endpoints': 21188, 'dangles': 1204,
#  'crossings_without_node': 87, 'total_length_m': 2841192.4}

Not all 1,204 dangles are errors — every cul-de-sac and every edge of the study area legitimately ends in one. The ones that matter are dangles near another line, which is what separates a real junction from a genuine dead end.

The four defects

Grid of four line-network defects with what each breaks. — All four pass `is_valid`. Only routing and length totals notice.

Step-by-step solution

Vertical steps from noding through snapping, trimming overshoots, removing stubs and verifying connectivity. — Node first. Snapping before noding moves endpoints onto lines that still have no vertex there.

1. Node the network — split every line at every crossing

Two roads that cross with no shared vertex are, topologically, not connected at all. unary_union on a set of lines nodes them: every intersection becomes a vertex, and the lines are split there.

from shapely.ops import unary_union

noded = unary_union(roads.geometry)        # a MultiLineString, split at every crossing
segments = list(getattr(noded, "geoms", [noded]))
print(f"{len(roads)} lines → {len(segments)} noded segments")
# 18402 lines → 19871 noded segments

This must come first. Snapping endpoints to a network that has not been noded moves them onto a line that has no vertex at that position, so they still do not connect.

The cost is attributes: unary_union returns bare geometry. Re-attach by matching each segment back to the line it came from:

def reattach(segments, source, crs):
    seg = gpd.GeoDataFrame(geometry=segments, crs=crs)
    probes = seg.copy()
    probes["geometry"] = seg.geometry.interpolate(0.5, normalized=True)
    joined = gpd.sjoin_nearest(probes, source, max_distance=0.01, how="left")
    return seg.join(joined.drop(columns=["geometry", "index_right"]))

A midpoint probe is more reliable than a centroid here: a curved line's centroid can fall off the line entirely.

2. Find the dangles that should not be dangles

from shapely.geometry import Point

def real_dangles(gdf, tol=0.5):
    """Endpoints that appear once AND sit close to another line — i.e. failed junctions."""
    counts = Counter(endpoints(gdf))
    singles = [Point(p) for p, n in counts.items() if n == 1]

    lines = gdf.sindex
    suspects = []
    for pt in singles:
        near = list(lines.query(pt.buffer(tol), predicate="intersects"))
        # ignore the line this endpoint belongs to
        others = [i for i in near if gdf.geometry.iloc[i].distance(pt) > 1e-9]
        if others:
            suspects.append({"geometry": pt, "near_lines": len(others),
                             "gap_m": min(gdf.geometry.iloc[i].distance(pt) for i in others)})
    return gpd.GeoDataFrame(suspects, crs=gdf.crs)

suspects = real_dangles(roads)
print(f"{len(suspects)} of {network_report(roads)['dangles']} dangles are near another line")
# 289 of 1204 dangles are near another line

The other 915 are cul-de-sacs and study-area edges — correct dangles that must be left alone. Deleting all dangles is the classic over-clean that removes every dead-end street in the district.

3. Snap the undershoots

from shapely.ops import snap

def snap_undershoots(gdf, tol=0.5):
    target = unary_union(gdf.geometry)
    fixed, moved = [], 0
    for geom in gdf.geometry:
        snapped = snap(geom, target, tol)
        if not snapped.equals(geom):
            moved += 1
        fixed.append(snapped)
    return gdf.assign(geometry=fixed), moved

roads, moved = snap_undershoots(roads, tol=0.5)
print(f"{moved} lines snapped")

The tolerance is the whole decision, and it has a hard upper bound: it must be smaller than the shortest genuine gap in the network. A 5 m tolerance on an urban network will weld a service road to the dual carriageway it runs beside.

# sanity check: how much did snapping move things?
delta = (roads.geometry.length - original.geometry.length).abs()
print(f"largest length change: {delta.max():.3f} m")

4. Trim the overshoots

An overshoot is a short piece of line sticking past a junction — the digitiser carried on a few centimetres too far. After noding, it is a separate segment with a dangle at one end and a length below any plausible real road.

MIN_SEGMENT = 1.0     # m — nothing real is shorter

def trim_overshoots(gdf, min_length=MIN_SEGMENT):
    counts = Counter(endpoints(gdf))
    def is_stub(geom):
        if geom.length >= min_length:
            return False
        ends = [geom.coords[0], geom.coords[-1]]
        return any(counts[e] == 1 for e in ends)     # dangling at one end

    stubs = gdf.geometry.apply(is_stub)
    print(f"trimming {stubs.sum()} stubs shorter than {min_length} m")
    return gdf[~stubs]

Both conditions are needed. A short segment between two junctions is a real link — a kerb line, a slip road. A short segment dangling at one end is almost always an artefact.

5. Merge the pieces back where noding split them unnecessarily

Noding splits a road at every crossing, which is correct for routing and noisy for cartography. linemerge puts back the pieces that meet at a degree-2 node with the same attributes:

from shapely.ops import linemerge

def merge_by_attribute(gdf, by="road_name"):
    out = []
    for name, group in gdf.groupby(by, dropna=False):
        merged = linemerge(unary_union(group.geometry))
        for part in getattr(merged, "geoms", [merged]):
            out.append({by: name, "geometry": part})
    return gpd.GeoDataFrame(out, crs=gdf.crs)

Do this last, and only if the output is for display. A routing graph wants the noded version.

6. Verify with connectivity, not with a map

import networkx as nx

def connectivity(gdf):
    g = nx.Graph()
    for geom in gdf.geometry:
        for line in getattr(geom, "geoms", [geom]):
            g.add_edge(line.coords[0], line.coords[-1], length=line.length)
    comps = list(nx.connected_components(g))
    biggest = max(comps, key=len) if comps else set()
    return {
        "components": len(comps),
        "largest_component_nodes": len(biggest),
        "isolated_fraction": round(1 - len(biggest) / max(g.number_of_nodes(), 1), 4),
    }

print(connectivity(roads))
# before: {'components': 412, 'largest_component_nodes': 18220, 'isolated_fraction': 0.1103}
# after:  {'components': 6,   'largest_component_nodes': 20981, 'isolated_fraction': 0.0021}

The component count is the only honest measure. A map cannot show a 4 cm gap, and a length total does not change when a network falls into pieces.

Code examples

Example 1: the complete clean, with a report

import geopandas as gpd
import networkx as nx
from collections import Counter
from shapely.ops import unary_union, snap

def clean_network(gdf, *, snap_tol=0.5, min_stub=1.0):
    report = {"features_in": len(gdf), "length_in": round(gdf.geometry.length.sum(), 1)}
    report["components_in"] = connectivity(gdf)["components"]

    # 1. node
    noded = unary_union(gdf.geometry)
    segs = gpd.GeoDataFrame(
        geometry=list(getattr(noded, "geoms", [noded])), crs=gdf.crs
    )
    report["segments_after_noding"] = len(segs)

    # 2. snap undershoots
    target = unary_union(segs.geometry)
    segs["geometry"] = [snap(g, target, snap_tol) for g in segs.geometry]

    # 3. re-node (snapping can create new crossings)
    noded = unary_union(segs.geometry)
    segs = gpd.GeoDataFrame(
        geometry=list(getattr(noded, "geoms", [noded])), crs=gdf.crs
    )

    # 4. trim stubs
    counts = Counter(endpoints(segs))
    stub = segs.geometry.apply(
        lambda g: g.length < min_stub
        and any(counts[e] == 1 for e in (g.coords[0], g.coords[-1]))
    )
    report["stubs_trimmed"] = int(stub.sum())
    segs = segs[~stub].reset_index(drop=True)

    report["features_out"] = len(segs)
    report["length_out"] = round(segs.geometry.length.sum(), 1)
    report["length_change_m"] = round(report["length_out"] - report["length_in"], 1)
    report["components_out"] = connectivity(segs)["components"]
    return segs, report

clean, report = clean_network(roads)
print(report)
# {'features_in': 18402, 'length_in': 2841192.4, 'components_in': 412,
#  'segments_after_noding': 19871, 'stubs_trimmed': 143,
#  'features_out': 19728, 'length_out': 2841098.2, 'length_change_m': -94.2,
#  'components_out': 6}

length_change_m is the number to check. Ninety-four metres removed from 2,841 km is stub trimming working correctly. Ninety-four kilometres would mean the tolerance welded half the network together.

Example 2: choosing the snap tolerance from the data

import numpy as np

def gap_distribution(gdf, max_gap=5.0):
    """How far apart are the dangling endpoints and their nearest line?"""
    suspects = real_dangles(gdf, tol=max_gap)
    if suspects.empty:
        return None
    gaps = suspects["gap_m"]
    for q in (0.5, 0.75, 0.9, 0.95, 0.99):
        print(f"  {q:.0%} of near-dangles are within {gaps.quantile(q):.3f} m")
    print(f"  max {gaps.max():.3f} m")
    return gaps

gap_distribution(roads)
#   50% of near-dangles are within 0.021 m
#   75% of near-dangles are within 0.084 m
#   90% of near-dangles are within 0.310 m
#   95% of near-dangles are within 2.870 m      ← the distribution breaks here
#   99% of near-dangles are within 41.200 m
#   max 288.400 m

The jump between the 90th and 95th percentile is the signal. Below 0.31 m the gaps are digitising noise; above ~3 m they are genuine separations that happen to be near each other. Setting the tolerance at 0.5 m catches the noise and nothing else.

Example 3: a regression test for connectivity

def test_network_stays_connected(cleaned_roads):
    stats = connectivity(cleaned_roads)
    assert stats["isolated_fraction"] < 0.01, (
        f"{stats['isolated_fraction']:.1%} of nodes are cut off in "
        f"{stats['components']} components"
    )

def test_cleaning_did_not_shorten_the_network(original, cleaned):
    change = abs(cleaned.geometry.length.sum() - original.geometry.length.sum())
    assert change / original.geometry.length.sum() < 0.001, (
        f"cleaning changed total length by {change:,.0f} m"
    )

Connectivity regressions are silent — a later simplify or reprojection can disconnect a network without changing anything visible.

Explanation

Two panels showing why snapping before noding fails and noding first succeeds. — Snapping an endpoint onto a line does not connect it unless that line has a vertex there.

A line layer stores geometry; a network is a graph, and the graph is inferred from the geometry by treating shared coordinates as shared nodes. That inference is exact: two lines are connected if and only if they have a coordinate in common, to the last bit of the double.

Everything on this page follows from that. Two roads that visually meet but differ by 4 cm share no coordinate, so the graph has two nodes where a person sees one, and no edge between them. The map is unaffected — 4 cm is invisible at any sensible scale — while the routing engine correctly reports that you cannot get from one street to the other.

The ordering constraint has the same root. snap() moves an endpoint onto the geometry of a nearby line, which puts it somewhere along a segment between two of that line's vertices. Geometrically it is now on the line; graph-wise it is still not a node, because the line's coordinate list does not contain that position. Noding — splitting every line at every intersection — is what turns a geometric touch into a shared coordinate. Hence: node, snap, node again, because snapping can create new crossings.

The judgement call is the tolerance, and it is bounded on both sides. It must be larger than the digitising noise (or undershoots survive) and smaller than the shortest real gap (or distinct roads weld together). Example 2 is the honest way to find that window: the noise and the real gaps occupy different parts of the distribution, and the break between them is visible.

The last thing worth internalising is that dangles are not errors by default. Every cul-de-sac ends in one. Every road clipped at the study-area edge ends in one. A cleaning script that deletes dangles indiscriminately produces a network that routes beautifully and is missing every dead end — which is exactly the kind of damage that survives review, because the result looks tidier than what it replaced.

Edge cases or notes

unary_union on a large line layer is expensive — minutes for hundreds of thousands of segments. Node by tile if it will not finish.
Noding discards attributes. Re-attach by midpoint probe, not centroid: a curved line's centroid can fall off the line.
snap() moves vertices, not just endpoints, if they fall within tolerance. Check the total length change.
Z coordinates break endpoint matching — (x, y, z) tuples differ even when (x, y) matches. force_2d first unless the Z is meaningful.
Bridges and tunnels legitimately cross without a node. Noding a network that has them creates junctions where none exist; exclude by attribute first.
linemerge only joins at degree-2 nodes, so it will not merge across a junction — which is correct.
Digitised direction matters for one-way networks but not for connectivity; do not reverse lines while cleaning.
Duplicate collinear segments survive noding as two identical pieces. Deduplicate on WKB after noding.

Internal links

Topological coverage: what "clean" means for adjacent polygons — the polygon equivalent of this page
How to find and fix gaps and overlaps in a polygon coverage — snapping and precision, applied to areas
How to snap and align geometries to fix slivers and gaps — the snapping mechanics
Topology in GIS explained: slivers, gaps and shared boundaries — the underlying ideas
Coordinate precision and floating point in GIS explained — why 4 cm and 4 nm are the same problem
Repair, reject or flag? Choosing what cleaning should do — why dangles get flagged, not deleted
The Python GIS data cleaning checklist — where network cleaning fits
What makes a geometry valid? The OGC rules explained — and why none of these defects break it

FAQ

Why does my routing fail when the map looks continuous?

Two lines that meet visually are only connected if they share an exact coordinate. A 4 cm gap is invisible on any map and fatal to a graph.

Should I snap before or after noding?

After. Snapping puts an endpoint onto a line's geometry, but the line has no vertex there until it is noded — so the graph is still disconnected. Node, snap, node again.

How do I pick the snap tolerance?

Plot the distribution of gaps between dangling endpoints and their nearest line. Digitising noise and real separations occupy different ranges, and the break between them is the tolerance.

Are all dangles errors?

No. Cul-de-sacs and lines clipped at the study-area edge end in legitimate dangles. Only dangles close to another line are failed junctions.

What is an overshoot, exactly?

A short piece of line continuing past a junction, left by a digitiser. After noding it is a separate segment, shorter than any real link, dangling at one end.

Will cleaning change my total length?

Slightly — stub trimming removes a little, snapping adjusts a little. Assert the change is a small fraction of the total; a large change means the tolerance is too big.

How do I know the clean worked?

Count connected components before and after. A map cannot show a centimetre gap; the component count can.

How to Clean a Line Network: Dangles, Overshoots and Disconnects #

Problem statement #

Quick answer #

The four defects #

Step-by-step solution #

1. Node the network — split every line at every crossing #

2. Find the dangles that should not be dangles #

3. Snap the undershoots #

4. Trim the overshoots #

5. Merge the pieces back where noding split them unnecessarily #

6. Verify with connectivity, not with a map #

Code examples #

Example 1: the complete clean, with a report #

Example 2: choosing the snap tolerance from the data #

Example 3: a regression test for connectivity #

Explanation #

Edge cases or notes #

Internal links #

FAQ #

Why does my routing fail when the map looks continuous? #

Should I snap before or after noding? #

How do I pick the snap tolerance? #

Are all dangles errors? #

What is an overshoot, exactly? #

Will cleaning change my total length? #

How do I know the clean worked? #