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)      # should be 1

Built from Hereford's 3,220 OpenStreetMap road ways as mapped, a graph of line endpoints has 2,119 separate components in a network a map shows as continuous (Example 1). The causes are the ordinary ones: roads that meet at a vertex half-way along one of them rather than at an end, pairs that cross with no shared vertex, and endpoints that stop just short of the line they were meant to meet.

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:

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': 3220, 'endpoints': 5206, 'dangles': 4381, 'crossings_without_node': 47, 'total_length_m': np.float64(349480.8)}

On raw ways that count is nearly useless: 4,381 of Hereford's 5,206 distinct endpoints appear only once, because OpenStreetMap roads usually meet at a vertex in the middle of the other way, not at its end. Node the network first (step 1), and the count starts to mean something. Even then not every dangle is an error — 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

Node, find dangles, snap, trim, merge, verify

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")

3220 lines → 5980 noded segments

Before noding, look at what the crossings are. A crossing without a shared vertex is a missing junction only if the two roads are at the same level:

pairs = gpd.sjoin(roads, roads, predicate="crosses")
pairs = pairs[pairs.index < pairs["index_right"]]
graded = (pairs["bridge_left"].notna() | pairs["bridge_right"].notna()
          | pairs["tunnel_left"].notna() | pairs["tunnel_right"].notna())
print(f"{len(pairs)} crossings without a node; {graded.sum()} involve a bridge or tunnel")

47 crossings without a node; 3 involve a bridge or tunnel

unary_union nodes every one of them, bridges included, so a noded graph lets a route turn off a bridge onto the road beneath it. For routing, node only the crossings between roads on the same level, or drop the bridge and tunnel ways from the noding and add them back whole.

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"]))


pieces = reattach(segments, roads, roads.crs)
print(f"{pieces['osm_id'].notna().mean():.1%} of segments recovered their attributes; "
      f"{pieces.index.duplicated().sum()} matched two source lines")

100.0% of segments recovered their attributes; 0 matched two source lines

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)})
    # an empty list still needs its columns, or GeoDataFrame refuses the CRS
    return gpd.GeoDataFrame(suspects, columns=["geometry", "near_lines", "gap_m"],
                            geometry="geometry", crs=gdf.crs)

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

0 of 4381 dangles are near another line

On this network none were: no dangle came within 0.5 m of another line, because OpenStreetMap junctions share a node or they are not junctions. A digitised network from drawings or scans is where near-misses of a few centimetres pile up. Either way, 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")

6 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")

largest length change: 0.102 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]


trimmed = trim_overshoots(pieces)

trimming 0 stubs shorter than 1.0 m

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):
        union = unary_union(group.geometry)
        # linemerge refuses a single LineString, which a one-segment road name gives
        merged = linemerge(union) if union.geom_type == "MultiLineString" else union
        for part in getattr(merged, "geoms", [merged]):
            out.append({by: name, "geometry": part})
    return gpd.GeoDataFrame(out, crs=gdf.crs)


merged = merge_by_attribute(trimmed.assign(road_name=trimmed["name"].fillna("(unnamed)")))
print(f"{len(trimmed):,} noded segments → {len(merged):,} merged lines")

5,980 noded segments → 3,779 merged lines

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("raw ways:", connectivity(original))
print("noded:   ", connectivity(pieces))

raw ways: {'components': 2119, 'largest_component_nodes': 392, 'isolated_fraction': 0.9247}
noded:    {'components': 9, 'largest_component_nodes': 5215, 'isolated_fraction': 0.0069}

The component count is the only honest measure — here 2,119 components on the raw ways and 9 once noded. A map cannot show a 4 cm gap, and a length total does not change when a network falls into pieces.

Cleaning Hereford's roads with a connectivity test

The data used on this page

Every OpenStreetMap road in and around Hereford, fetched from Overpass as raw ways — one line per way, as mapped, with the bridge, tunnel and layer tags that say whether two crossing roads meet — and projected to the British National Grid.

import json
import os
from collections import Counter

import geopandas as gpd
import requests
from shapely.geometry import LineString

QUERY = """[out:json][timeout:120];
way["highway"~"^(motorway|trunk|primary|secondary|tertiary|unclassified|residential|service|living_street|motorway_link|trunk_link|primary_link|secondary_link|tertiary_link)$"](52.035,-2.76,52.075,-2.68);
out geom tags;"""
if not os.path.exists("hereford_roads.json"):
    for url in ("https://overpass-api.de/api/interpreter",
                "https://maps.mail.ru/osm/tools/overpass/api/interpreter"):
        try:
            reply = requests.post(url, data={"data": QUERY}, timeout=180,
                                  headers={"User-Agent": "spatialworkflow.io guide"})
            reply.raise_for_status()
            json.dump(reply.json(), open("hereford_roads.json", "w"))
            break
        except requests.RequestException:
            continue

ways = json.load(open("hereford_roads.json"))["elements"]
roads = gpd.GeoDataFrame(
    [{"osm_id": w["id"], "highway": w["tags"]["highway"], "name": w["tags"].get("name"),
      "bridge": w["tags"].get("bridge"), "tunnel": w["tags"].get("tunnel"),
      "geometry": LineString([(p["lon"], p["lat"]) for p in w["geometry"]])}
     for w in ways if len(w.get("geometry", [])) > 1], crs=4326).to_crs(27700)
original = roads.copy()
print(f"{len(roads):,} road ways, {roads.length.sum() / 1000:,.1f} km, "
      f"{roads['bridge'].notna().sum()} bridges, {roads['tunnel'].notna().sum()} tunnels")

3,220 road ways, 349.5 km, 25 bridges, 13 tunnels

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(original)
print(report)

{'features_in': 3220, 'length_in': np.float64(349480.8), 'components_in': 2119, 'segments_after_noding': 5980, 'stubs_trimmed': 0, 'features_out': 5981, 'length_out': np.float64(349479.7), 'length_change_m': np.float64(-1.1), 'components_out': 9}

length_change_m is the number to check. Here cleaning moved 6 lines, trimmed nothing and changed the total by 1.1 m in 349.5 km, which is what cleaning a well-maintained network should do. A change of kilometres would mean the tolerance welded roads 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

gaps = gap_distribution(original)

  50% of near-dangles are within 3.387 m
  75% of near-dangles are within 4.110 m
  90% of near-dangles are within 4.709 m
  95% of near-dangles are within 4.893 m
  99% of near-dangles are within 4.971 m
  max 4.983 m

Asked for gaps up to 5 m, this network's near-dangles spread evenly from a few metres to the 5 m cap — median 3.4 m — rather than clustering at centimetres: service roads and yards that stop a few metres short of another road on purpose. That is the signal to read: a cluster of centimetre gaps is digitising noise to snap; an even spread of metre-scale gaps is the real layout, and a tolerance reaching into it welds roads that should stay apart. On this network 0.5 m catches nothing and harms nothing.

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"
    )

for test, args in ((test_network_stays_connected, (clean,)),
                   (test_cleaning_did_not_shorten_the_network, (original, clean))):
    try:
        test(*args)
        print(f"{test.__name__}: passed")
    except AssertionError as failure:
        print(f"{test.__name__}: FAILED — {failure}")

test_network_stays_connected: passed
test_cleaning_did_not_shorten_the_network: passed

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

A network is a graph inferred from geometry

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.

Noding cost, lost attributes, Z values and bridges

• 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
• 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
• How to build measures onto a line that has none — what the cleaned network is needed for
• Blocks from streets look wrong — what dangles and dual carriageways do to blocks

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.