Measuring distances¶
Distances can be computed between trajectories as well as between trajectories and other geometry objects. The implemented distance measures are:
import pandas as pd
import geopandas as gpd
import movingpandas as mpd
import shapely as shp
import hvplot.pandas
import matplotlib.pyplot as plt
from geopandas import GeoDataFrame, read_file
from shapely.geometry import Point, LineString, Polygon
from datetime import datetime, timedelta
from holoviews import opts, dim
import warnings
warnings.filterwarnings("ignore")
plot_defaults = {"linewidth": 5, "capstyle": "round", "figsize": (9, 3), "legend": True}
opts.defaults(opts.Overlay(active_tools=["wheel_zoom"]))
hvplot_defaults = {
"tiles": "CartoLight",
"frame_height": 320,
"frame_width": 320,
"cmap": "Viridis",
"colorbar": True,
}
mpd.show_versions()
MovingPandas 0.23.0 SYSTEM INFO ----------- python : 3.10.19 | packaged by conda-forge | (main, Jan 26 2026, 23:45:08) [GCC 14.3.0] executable : /home/anita/miniforge3/envs/mpd-ex/bin/python machine : Linux-6.8.0-134-generic-x86_64-with-glibc2.39 PROJ INFO ----------- PROJ : 9.6.2 PROJ data dir: /home/anita/miniforge3/envs/mpd-ex/share/proj PYTHON DEPENDENCIES ------------------- numpy : 1.23.1 geopandas : 1.0.1 geopy : 2.4.1 geoviews : 1.15.1 holoviews : 1.22.1 hvplot : 0.12.2 mapclassify: 2.8.1 matplotlib : 3.10.8 pandas : 2.3.3 pyproj : 3.7.1 shapely : 2.1.2 stonesoup : 1.8
Measuring distances between trajectories¶
df = pd.DataFrame(
[
{"geometry": Point(0, 0), "t": datetime(2018, 1, 1, 12, 0, 0)},
{"geometry": Point(6, 0), "t": datetime(2018, 1, 1, 12, 6, 0)},
{"geometry": Point(6, 6), "t": datetime(2018, 1, 1, 12, 10, 0)},
{"geometry": Point(9, 9), "t": datetime(2018, 1, 1, 12, 15, 0)},
]
).set_index("t")
geo_df = GeoDataFrame(df, crs=31256)
toy_traj = mpd.Trajectory(geo_df, 1)
toy_traj.df
| geometry | traj_id | |
|---|---|---|
| t | ||
| 2018-01-01 12:00:00 | POINT (0 0) | 1 |
| 2018-01-01 12:06:00 | POINT (6 0) | 1 |
| 2018-01-01 12:10:00 | POINT (6 6) | 1 |
| 2018-01-01 12:15:00 | POINT (9 9) | 1 |
df = pd.DataFrame(
[
{"geometry": Point(3, 3), "t": datetime(2018, 1, 1, 12, 0, 0)},
{"geometry": Point(3, 9), "t": datetime(2018, 1, 1, 12, 6, 0)},
{"geometry": Point(2, 9), "t": datetime(2018, 1, 1, 12, 10, 0)},
{"geometry": Point(0, 7), "t": datetime(2018, 1, 1, 12, 15, 0)},
]
).set_index("t")
geo_df = GeoDataFrame(df, crs=31256)
toy_traj2 = mpd.Trajectory(geo_df, 1)
toy_traj2.df
ax = toy_traj.plot()
toy_traj2.plot(ax=ax, color="red")
<Axes: >
print(f"Distance: {toy_traj.distance(toy_traj2)} meters")
print(f"Hausdorff distance: {toy_traj.hausdorff_distance(toy_traj2):.2f} meters")
Distance: 3.0 meters Hausdorff distance: 6.08 meters
print(f'Distance: {toy_traj.distance(toy_traj2, units="cm")} cm')
print(
f'Hausdorff distance: {toy_traj.hausdorff_distance(toy_traj2, units="km"):.6f} km'
)
Distance: 300.0 cm Hausdorff distance: 0.006083 km
Measuring trajectory similarity¶
Beyond the minimum distance, MovingPandas provides several measures of how similar two trajectories are as a whole. All of them work on the recorded point sequences, so the values also depend on how the trajectories are sampled. Each captures a different notion of similarity:
- Fréchet distance – the smallest “leash length” needed to traverse both trajectories from start to end without backtracking. MovingPandas computes the discrete Fréchet distance, so both walkers hop from one recorded point to the next rather than moving continuously along the line between them. That makes it sensitive to the location and ordering of the points, and also to how densely each trajectory is sampled.
- Dynamic Time Warping (DTW) distance – the accumulated distance of the best alignment that stretches or compresses the trajectories along their order. Reflects the overall cumulative deviation rather than the single largest gap.
- Longest Common Subsequence (LCSS) distance – the share of the shorter trajectory's points that could not be matched to the other trajectory. Two points match when they are within the spatial threshold
epsilon, and the matches have to follow the order of both trajectories. Points that find no match are skipped instead of being forced into a pair, which makes LCSS more robust to noise and outliers than DTW and Fréchet, which must account for every point.
Fréchet and DTW are reported in CRS units (meters here). DTW is an accumulated sum over the matched point pairs, so it also grows with trajectory length and sampling density: raw DTW values are only comparable between similarly sampled trajectory pairs. LCSS is a ratio in [0, 1] instead: 1 - matched share, measured against the shorter of the two trajectories. So 0 means every point of the shorter trajectory found a match, i.e. it is essentially a (noisy) subsequence of the other, while values near 1 mean almost no points could be matched within epsilon. LCSS distances are only comparable when computed with the same epsilon and delta.
print(f"Fréchet distance: {toy_traj.frechet_distance(toy_traj2):.2f} meters")
print(f"DTW distance: {toy_traj.dtw_distance(toy_traj2):.2f} meters")
print(f"LCSS distance: {toy_traj.lcss_distance(toy_traj2, epsilon=5):.2f}")
Fréchet distance: 9.22 meters DTW distance: 26.95 meters LCSS distance: 0.50
Tuning the computation for long trajectories¶
Exact DTW and LCSS both evaluate all n·m alignment cells between the two point sequences, which costs O(n*m) time. Both take an optional parameter that can make that much cheaper on long trajectories, and each also changes what the measure means:
dtw_distance(..., radius=...)switches to the FastDTW approximation (Salvador & Chan, 2007), which runs in linear time for a fixed radius and never underestimates the exact distance. A larger radius generally lands closer to exact, though not at every single step: FastDTW refines a path found on coarsened sequences, so an individual increase can occasionally move the estimate further away.lcss_distance(..., delta=...)only matches points that are at mostdeltapositions apart in the two sequences, which restricts the work to a band around the diagonal. Note thatdeltacounts sequence positions, not time or distance: it only expresses "matching points occur at a similar stage of the trip" when both trajectories are sampled at comparable, steady rates.
The toy trajectories above are too short for either to bite, so let's use two of the longer Geolife trajectories.
gdf = read_file("../data/geolife_small.gpkg")
# These measures use Euclidean geometry, so project to a planar CRS first
geolife = mpd.TrajectoryCollection(gdf.to_crs("EPSG:32650"), "trajectory_id", t="t")
traj_a = geolife.trajectories[2]
traj_b = geolife.trajectories[3]
print(f"{len(traj_a.df)} and {len(traj_b.df)} points")
ax = traj_a.plot()
traj_b.plot(ax=ax, color="red")
1810 and 1864 points
<Axes: >
exact = traj_a.dtw_distance(traj_b)
print(f"exact DTW: {exact:,.0f} meters")
for radius in [5, 25, 100]:
approx = traj_a.dtw_distance(traj_b, radius=radius)
print(f"FastDTW, radius={radius:>3}: {approx:,.0f} meters ({approx / exact:.4f}x exact)")
exact DTW: 320,146 meters FastDTW, radius= 5: 324,698 meters (1.0142x exact)
FastDTW, radius= 25: 322,934 meters (1.0087x exact)
FastDTW, radius=100: 320,146 meters (1.0000x exact)
With delta, LCSS additionally requires matched points to be close in sequence position, not just in space:
print(f"LCSS, any position: {traj_a.lcss_distance(traj_b, epsilon=200):.3f}")
for delta in [1000, 200, 50]:
print(
f"LCSS, delta={delta:>4}: "
f"{traj_a.lcss_distance(traj_b, epsilon=200, delta=delta):.3f}"
)
LCSS, any position: 0.231
LCSS, delta=1000: 0.231
LCSS, delta= 200: 0.794 LCSS, delta= 50: 0.919
The two trajectories cover much of the same ground, so with no positional constraint about 77% of the points on the shorter one can be matched. Tightening delta drops that sharply: the routes overlap in space, but the matching points sit far apart in the two point sequences. That is expected here: the two trips were recorded on different days, and one of them contains a multi-hour recording gap, so sequence position is a poor proxy for trip progress.
Measuring distances between trajectories and other geometry objects¶
pt = Point(1, 5)
line = LineString([(3, 3), (3, 9)])
ax = toy_traj.plot()
gpd.GeoSeries(pt).plot(ax=ax, color="red")
gpd.GeoSeries(line).plot(ax=ax, color="red")
<Axes: >
print(f"Distance: {toy_traj.distance(pt)}")
print(f"Hausdorff distance: {toy_traj.hausdorff_distance(pt):.2f}")
Distance: 5.0 Hausdorff distance: 8.94
print(f"Distance: {toy_traj.distance(line)}")
print(f"Hausdorff distance: {toy_traj.hausdorff_distance(line)}")
Distance: 3.0 Hausdorff distance: 6.0
print(f'Distance: {toy_traj.distance(line, units="cm")} cm')
print(f'Hausdorff distance: {toy_traj.hausdorff_distance(line, units="km"):.6f} km')
Distance: 300.0 cm Hausdorff distance: 0.006000 km