Preventing Trajectory Self-Intersection in Physics Paths

When a physics-based path generator produces a synthetic vehicle track that loops back and crosses its own line — a manoeuvre no real vehicle at that speed could make — the cause is a steering model that can change heading faster than the vehicle’s turn radius allows, and the fix is a curvature bound plus a geometry gate that rejects any path that is not simple.

Part of Physics-Based Path Generation: that workflow integrates a motion model to produce trajectories that obey acceleration and speed limits, and self-intersection is the geometric symptom that those limits are not yet constraining heading change. This page explains why unconstrained steering self-crosses, imposes a turn-radius bound derived from lateral acceleration, and gates the output with a Shapely is_simple check so a crossing path can never reach a consumer.

Root Cause: Unbounded Heading Rate Folds the Path

A physics path is generated by integrating a kinematic model — position advances along the current heading, heading changes according to a steering input. If the steering input is drawn from noise, sampled from a distribution, or optimized toward waypoints without a bound on how fast heading may change, the model can rotate the velocity vector almost instantaneously. When heading turns faster than forward motion carries the vehicle away from where it just was, the path curls back on itself and crosses its earlier trace.

The governing quantity is curvature κ\kappa, the rate of heading change per unit distance travelled. It is bounded by the vehicle’s dynamics: a vehicle moving at speed vv that can sustain lateral acceleration at most alata_{\text{lat}} has a minimum turning radius

Rmin⁡=v2alat,κmax⁡=1Rmin⁡=alatv2.R_{\min} = \frac{v^{2}}{a_{\text{lat}}}, \qquad \kappa_{\max} = \frac{1}{R_{\min}} = \frac{a_{\text{lat}}}{v^{2}}.

The crucial feature is the v2v^2: the faster the vehicle, the larger the minimum radius, so tight turns are only physical at low speed. An unconstrained generator ignores this and allows a small radius at any speed, which is exactly the regime where the path folds. A self-intersection is therefore not primarily a geometry bug — it is a dynamics violation that happens to show up as geometry. A path can also self-cross without any single step exceeding κmax⁡\kappa_{\max}, by accumulating heading change across many steps until it completes a loop; that global case is why a per-step curvature clamp needs a global geometry gate behind it.

Bounding curvature turns the free-heading integrator into a curvature-limited one: at each step the heading change is clipped to κmax⁡ Δs\kappa_{\max}\,\Delta s, where Δs\Delta s is the arc length of the step. This is the continuous analogue of a Dubins/Reeds-Shepp path, which is built entirely from straight segments and arcs of the minimum radius, and it is what keeps a synthetic vehicle track looking like something a real vehicle could drive.

Unconstrained self-intersecting path versus a curvature-bounded simple path Left panel: a trajectory drawn from unconstrained steering weaves upward and then curls sharply back, so an earlier segment and a later segment cross at a single point marked with an accent ring; the panel is labelled is_simple is False, self-intersection. Right panel: a trajectory over comparable waypoints produced by curvature-bounded steering follows a smooth S-shape that never crosses itself; a dashed circle of radius R-min is drawn tangent at the sharpest bend to show the minimum turn radius the heading change respects, and the panel is labelled is_simple is True. A caption ties the bound to R-min equals v squared over lateral acceleration. Unconstrained steering Curvature-bounded steering is_simple == False self-intersection R₋ₐ₋ is_simple == True Heading change per step clipped to κ₁₁ₓₓ · Δs, with R₋ₐ₋ = v² / aₓₐₜ
Same waypoints, two steering models: unconstrained heading rate folds the path into a self-crossing, while clipping each step's heading change to the minimum turn radius keeps the trajectory simple.

Minimal Reproducer: Free Heading Crosses Itself

Integrate a point mass whose heading is nudged by unbounded noise, then ask Shapely whether the resulting LineString is simple. With no curvature limit, the track loops and the check returns False.

python
# requirements.txt — pin majors; let patch releases float
numpy==1.26.*
shapely==2.*         # GEOS 3.11+; LineString.is_simple runs the self-intersection test

python
import numpy as np
from shapely.geometry import LineString

rng = np.random.default_rng(20260705)
n, ds = 60, 5.0                                  # 60 steps, 5 m arc length each
heading = 0.0
pos = np.array([0.0, 0.0])
pts = [pos.copy()]
for _ in range(n):
    heading += rng.normal(0.0, 1.2)              # UNBOUNDED heading change (radians)
    pos = pos + ds * np.array([np.cos(heading), np.sin(heading)])
    pts.append(pos.copy())

line = LineString(pts)
print(f"is_simple = {line.is_simple}")           # -> False: the path crosses itself

A per-step heading noise of over a radian at 5 m steps implies a turn radius of a few metres — physical only at walking pace, not for the vehicle this track is meant to represent. The geometry check confirms the dynamics violation.

Fix: Clip Curvature, Then Gate the Geometry

The fix has two layers. The per-step layer clips heading change to the physical maximum, which removes almost every self-crossing at the source. The whole-path layer runs a geometry gate that catches the rare accumulated loop the per-step clamp cannot see.

python
import numpy as np
from shapely.geometry import LineString

def curvature_bounded_path(headings_desired, *, speed, a_lat, ds, start=(0.0, 0.0),
                           start_heading=0.0):
    """Integrate a path, clipping heading change to the minimum-turn-radius bound.

    speed  : m/s along the path (constant here; vary per step if speed changes)
    a_lat  : max sustainable lateral acceleration (m/s^2), e.g. 3-4 for a car
    ds     : arc length per step (m)
    """
    r_min = speed ** 2 / a_lat                    # minimum turn radius
    kappa_max = 1.0 / r_min                        # max curvature
    max_dtheta = kappa_max * ds                    # max heading change this step

    heading = start_heading
    pos = np.asarray(start, dtype=float)
    pts = [pos.copy()]
    for desired in headings_desired:
        dtheta = np.clip(desired - heading, -max_dtheta, max_dtheta)  # the bound
        heading += dtheta
        pos = pos + ds * np.array([np.cos(heading), np.sin(heading)])
        pts.append(pos.copy())
    return LineString(pts)

def make_simple(headings_desired, **kw) -> LineString:
    """Curvature-bounded path with a geometry gate for the accumulated-loop case."""
    line = curvature_bounded_path(headings_desired, **kw)
    if line.is_simple:
        return line
    # Rare: heading stayed within the per-step bound but the path closed a loop.
    # Tighten the bound (raise a_lat headroom or lower speed) and regenerate,
    # rather than editing vertices, so the result stays physically consistent.
    raise ValueError("curvature-bounded path still self-intersects; reduce speed or ds")

Clipping desired - heading into [-max_dtheta, +max_dtheta] is the whole trick: the generator may want any heading, but it can only reach one within a physical turn of the current one. The speed-dependence is automatic because r_min carries v2v^2, so the same code tightens turns as the vehicle slows and forbids them as it speeds up. Keeping speed and lateral acceleration consistent is the same envelope enforced when calibrating acceleration limits for realistic vehicle paths, and the two constraints should share one parameter set.

Verification Step: Assert the Path Is Simple and Physical

The geometry gate is a single Shapely call, but pair it with a curvature check so a path that merely avoids crossing while still turning impossibly tight is also rejected. Both run in CI before a trajectory batch is promoted.

python
import numpy as np
from shapely.geometry import LineString

def test_path_is_simple_and_within_curvature(line: LineString, *, speed, a_lat, ds):
    # 1. Geometry gate: no self-intersection anywhere along the path.
    assert line.is_simple, "trajectory self-intersects (LineString.is_simple is False)"

    # 2. Curvature gate: no step's heading change exceeds the physical bound.
    xy = np.asarray(line.coords)
    seg = np.diff(xy, axis=0)
    headings = np.arctan2(seg[:, 1], seg[:, 0])
    dtheta = np.abs(np.diff(np.unwrap(headings)))          # unwrap across +/-pi seam
    kappa = dtheta / ds
    kappa_max = a_lat / speed ** 2
    assert kappa.max(initial=0.0) <= kappa_max + 1e-9, (
        f"curvature {kappa.max():.4f} exceeds bound {kappa_max:.4f} (1/m)")

np.unwrap before differencing headings is load-bearing: without it, a legitimate turn that crosses the ±π\pm\pi boundary reads as a near-2π2\pi jump and falsely trips the curvature gate. Feed the accepted tracks onward to the noise stage — the clean geometric path is what noise injection and stochastic drift perturbs into realistic GNSS traces, and running that stage before the simplicity gate would let sensor noise mask a real self-crossing.

Edge Cases & Gotchas

Heading unwrap at the ±π seam. Headings computed with arctan2 live in (−π,π](-\pi, \pi], so a vehicle turning through due-west sees its heading flip sign between consecutive steps. Differencing the raw values reports a spurious jump of nearly 2π2\pi that both inflates the measured curvature and, in reverse, can hide a real one. Always np.unwrap the heading sequence before computing per-step change, and apply the same treatment in the generator if it accumulates absolute heading.

Antimeridian and projected-versus-geographic curvature. Curvature is a metric quantity: Rmin⁡R_{\min} is in metres, so the integration and the gate must run in a projected CRS (a local UTM zone or an equal-area metric CRS), never in raw EPSG:4326 degrees. A path near ±180° longitude that is generated in geographic coordinates will also break is_simple, because the coordinate wrap makes a continuous track appear to jump the globe. Generate and validate in metres, then reproject the accepted geometry for storage.

Coincident vertices and near-zero steps read as non-simple. If speed drops to zero or the step arc length underflows, consecutive vertices coincide and GEOS may report the degenerate zero-length segment as a self-intersection, failing the gate for a path that never actually crosses. Drop duplicate consecutive points (snap to a small tolerance) before constructing the LineString, and guard ds away from zero so a stopped vehicle produces a dwell, handled by the timestamp layer, rather than a geometry artifact.

Frequently Asked Questions

Why does an unconstrained steering model produce self-intersecting paths?
Because it can change heading faster than forward motion carries the vehicle away from its previous position. When the heading rotates quickly relative to the distance travelled, the path curls back and crosses its earlier trace. Real vehicles cannot do this: their minimum turn radius grows with the square of speed, so tight turns are only possible slowly. Bounding the per-step heading change to that physical curvature limit removes almost all self-crossings at the source.
Is a curvature bound alone enough to guarantee a simple path?
No. A per-step curvature clamp stops any single step from turning too tightly, but a path can still close a loop by accumulating small, individually legal heading changes over many steps. That global self-intersection is invisible to a per-step check, so you still need a whole-path geometry gate. Run LineString.is_simple after generation, and if it fails, tighten the dynamics — lower the speed or shorten the step — rather than editing vertices.
What is the right minimum turn radius to use?
Derive it from the vehicle dynamics as R_min equals speed squared divided by the maximum sustainable lateral acceleration. For a passenger car, lateral acceleration of roughly 3 to 4 metres per second squared is comfortable, which at highway speed gives a radius of well over a hundred metres and at parking speed only a few metres. Because the radius carries the square of speed, use the instantaneous speed at each step rather than a single global value, so the bound tightens and loosens with the vehicle.
Why does my simplicity check fail on a path that clearly does not cross?
Two usual causes. First, coincident or near-zero-length segments from a stopped or barely moving vehicle, which GEOS can report as a degenerate self-intersection; snap and drop duplicate consecutive vertices before building the LineString. Second, running the check in geographic coordinates near the antimeridian, where the longitude wrap makes a continuous track appear to jump; generate and validate in a projected metric CRS instead.