Converting Isochrone Node Sets to Polygons

A bounded single-source Dijkstra returns a set of reachable nodes with their arrival costs. That is the correct answer to “what can this vehicle reach in thirty minutes”, and it is not something a map can draw. Turning it into a boundary is a separate step with its own choices, and the choice matters more than it looks: a convex hull over a river valley claims the far bank is reachable when the nearest bridge is twenty kilometres away, and the map is confidently, legibly wrong. This page covers the three constructions worth knowing, what each one claims, and how to pick without pretending the difference is cosmetic.

Prerequisites & Versions

The node set comes from the isochrone query; the geometry is client-side.

Requirement Minimum version Install
Python 3.11 —
neo4j (async driver) 5.20 pip install "neo4j>=5.20"
Neo4j Server 5.15 native point
shapely 2.0 pip install "shapely>=2.0"

Implementation

import math
from dataclasses import dataclass

from shapely.geometry import MultiPoint, box
from shapely.ops import unary_union

EARTH_R = 6_371_008.8


@dataclass(frozen=True)
class Reached:
    lat: float
    lon: float
    cost_s: float


def convex_hull(nodes: list[Reached]):
    """Smallest convex shape containing every reached node.

    Fast, always valid, and claims reachability for every point inside it —
    including water, private land and anything on the far side of a barrier.
    Honest only where the reachable region genuinely is convex, which a road
    network almost never is.
    """
    return MultiPoint([(n.lon, n.lat) for n in nodes]).convex_hull


def concave_hull(nodes: list[Reached], ratio: float = 0.25):
    """A boundary allowed to follow indentations in the reached set.

    `ratio` trades tightness against stability: near 0 the boundary hugs the
    points and becomes sensitive to a single outlier, near 1 it degenerates
    toward the convex hull. 0.2-0.3 is a usable range for road networks.
    """
    return MultiPoint([(n.lon, n.lat) for n in nodes]).concave_hull(ratio=ratio)


def cell_union(nodes: list[Reached], cell_m: float = 250.0):
    """Union of a small cell around each reached node.

    Makes no claim about the space BETWEEN nodes beyond one cell's width, which
    is the most defensible of the three: a hole in the middle stays a hole, and
    a peninsula stays a peninsula. Produces a blockier boundary, and a multi-
    polygon where the reachable set is genuinely disconnected — which is
    information, not a defect.
    """
    seen: set[tuple[int, int]] = set()
    cells = []
    d_lat = math.degrees(cell_m / EARTH_R)
    for n in nodes:
        d_lon = d_lat / max(math.cos(math.radians(n.lat)), 1e-6)
        # Snap to the grid and deduplicate: coincident cells union to themselves,
        # so unioning them repeatedly is work with no effect on the output.
        key = (math.floor(n.lon / d_lon), math.floor(n.lat / d_lat))
        if key in seen:
            continue
        seen.add(key)
        cells.append(box(key[0] * d_lon, key[1] * d_lat,
                         (key[0] + 1) * d_lon, (key[1] + 1) * d_lat))
    return unary_union(cells)


def band_polygons(nodes: list[Reached], bands_s: list[float], **kwargs):
    """One polygon per band, built from the CUMULATIVE set below each ceiling.

    Building each band from only the nodes between two ceilings produces rings
    with holes where the previous band sat, which then render as gaps rather
    than as nesting. Cumulative sets nest correctly by construction.
    """
    out = []
    for ceiling in sorted(bands_s):
        within = [n for n in nodes if n.cost_s <= ceiling]
        if within:
            out.append((ceiling, cell_union(within, **kwargs)))
    return out

How It Works

Each construction makes a different claim, and the claim is what should drive the choice.

A convex hull claims that everything inside is reachable. That is true only when the reachable region has no indentations — no estuary, no mountain, no restricted zone. On real geography it over-claims constantly, and the over-claim is the confident kind: a smooth boundary drawn across open water reads as authoritative. It is the right tool when the audience needs a rough catchment and understands it as one.

A concave hull lets the boundary follow indentations, at the cost of a tuning parameter. The ratio has no physically meaningful value — it trades tightness against stability, and the same setting produces different-looking boundaries on dense urban and sparse rural sets. That makes it hard to defend a specific number and easy to produce a boundary that looks precise and is not.

A cell union claims only what was measured. Each reached node contributes a small area around itself, and nothing is asserted about the gaps. Where the road network genuinely does not reach — the far bank, the middle of a park — there is a hole, and the hole is correct. It is blockier, it produces multi-polygons where the reachable set is disconnected, and both of those are the shape telling the truth about the data rather than smoothing it away.

The same reached node set, drawn three ways across a river A thirty-minute reachable set for an origin on one bank of a river, with the nearest bridge well outside the frame. The convex hull spans both banks and the water between them, claiming a large area that cannot be reached at all. The concave hull follows the indentation but its shape depends on a tuning ratio with no physical meaning, and it still bridges the narrowest part of the channel. The cell union covers only a small area around each node actually reached, so the river appears as a gap — which is what the search found. 30-minute reachable set, origin on the south bank convex hull claims the far bank and the water concave hull follows the bank, tuned by an arbitrary ratio cell union claims only what the search reached All three are built from the identical node set. The differences are entirely in what each shape asserts about the space between the nodes — which is the space nobody measured.

Common Failure Patterns

1. Building bands from disjoint cost slices. Constructing the 20-minute band from nodes costing between 10 and 20 minutes gives an annulus with a hole where the 10-minute band sits. Rendered with any opacity the bands then fail to nest and the map shows rings rather than a gradient. Build each band from the cumulative set below its ceiling and let the renderer stack them.

2. Smoothing until the shape is pretty. Every simplification step moves the boundary, and the direction is not controlled — a simplified isochrone claims reachability in places the search never visited. Where a smoother outline is genuinely wanted, simplify inward with a negative buffer so the error is conservative, and say that the shape under-claims.

3. Forgetting that the node set is the road network, not the ground. An isochrone drawn from junction positions has holes wherever a large block has no road inside it — a park, an airfield, an industrial site. Those are real holes in the reachable-by-road set and spurious ones in the “area a person can get to” set. Which is wanted depends on the question, and the difference should be a deliberate buffer rather than an accident of construction.

# Conservative smoothing: shrink then grow, so the result never claims more
# than the raw union did.
smoothed = cell_union(nodes).buffer(-0.0004).buffer(0.0003)

Performance Notes

Construction cost differs sharply between the three, and it matters because an isochrone endpoint is usually interactive:

$$C_{\text{convex}} = O(n \log n), \qquad C_{\text{concave}} = O(n \log n) \text{ with a large constant}, \qquad C_{\text{union}} = O(k \log k) \text{ over } k \text{ distinct cells}$$

On a thirty-minute urban band of a few thousand nodes all three are milliseconds. On a two-hour band of a hundred thousand nodes the union would become the expensive one if it operated per node — which is why the implementation above snaps to the grid and deduplicates first. Coincident cells union to themselves, so the reduction changes nothing about the output while collapsing the input by an order of magnitude.

The other lever is where the polygon is built at all. A band requested repeatedly with the same origin and ceiling — a depot’s standard service area — should be built once and stored, exactly as the tile pyramid is. Pinning band ceilings to a fixed tier set makes that cacheable and, as a bonus, keeps the underlying isochrone query’s plan stable.

One property of the cell union is worth exploiting rather than working around: because the cells are on a fixed grid shared by every band and every origin, two service areas can be compared, intersected or subtracted as sets of integer cell keys without any geometry at all. “Which customers are covered by depot A but not depot B” becomes a set difference over keys, which is orders of magnitude cheaper than a polygon intersection and is exact rather than subject to floating-point boundary behaviour.

Deduplicating onto the grid before the union, with an identical result A two-hour band containing 96,000 reached nodes. Unioning a cell per node means 96,000 polygons entering the geometry engine. Because the cells sit on a fixed grid, coincident cells are identical and union to themselves, so deduplicating first reduces the input to 7,400 distinct cells. The output polygon is identical and the construction is roughly thirteen times faster — the reduction costs one pass over the node list. Two-hour band · 96,000 reached nodes one cell per node most of them coincident, and all of them entering the union 96,000 construction: 4.1 s deduplicated onto the grid first coincident cells are identical and union to themselves 7,400 construction: 0.31 s output polygon: identical in both cases the reduction costs one pass over the node list

A closing point about how the polygon is presented. Whichever construction is used, the shape is a summary of a node set and the node set is a summary of a road network, so the boundary carries two layers of approximation before anyone looks at it. Rendering it with a hard, high-contrast outline invites the reader to treat the edge as exact — and the edge is the least reliable part of it, since a node just inside the ceiling and one just outside differ by seconds. Drawing the boundary with a soft edge, or rendering the bands as a graded fill without a stroke, communicates the uncertainty that is genuinely there. It is a presentation choice rather than a technical one, and it is the difference between a map that informs a depot-siting decision and one that gets quoted back as a commitment.

This guide is part of Isochrone and Service-Area Analysis, within Cypher Spatial Queries & Pathfinding Patterns.

Siblings