Generalizing trajectories

To reduce the size (number of points) of trajectory objects, we can generalize them, for example, using:

• Spatial generalization, such as Douglas-Peucker algorithm
• Temporal generalization by down-sampling, i.e. increasing the time interval between records
• Spatiotemporal generalization, e.g. using Top-Down Time Ratio algorithm

Documentation

A closely related type of operation is trajectory smoothing which is covered in a separate notebook.

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

import warnings
warnings.filterwarnings('ignore')

plot_defaults = {'linewidth':5, 'capstyle':'round', 'figsize':(9,3), 'legend':True}
opts.defaults(opts.Overlay(active_tools=['wheel_zoom'], frame_width=500, frame_height=400))

mpd.show_versions()

MovingPandas 0.18.1

SYSTEM INFO
-----------
python     : 3.10.14 | packaged by conda-forge | (main, Mar 20 2024, 12:40:08) [MSC v.1938 64 bit (AMD64)]
executable : c:\Users\Agarkovam\AppData\Local\miniforge3\envs\mpd-ex\python.exe
machine    : Windows-10-10.0.19045-SP0

GEOS, GDAL, PROJ INFO
---------------------
GEOS       : None
GEOS lib   : None
GDAL       : 3.8.5
GDAL data dir: None
PROJ       : 9.4.0
PROJ data dir: C:\Users\Agarkovam\AppData\Local\miniforge3\envs\mpd-ex\Library\share\proj

PYTHON DEPENDENCIES
-------------------
geopandas  : 0.14.4
pandas     : 2.2.2
fiona      : 1.9.6
numpy      : 1.26.4
shapely    : 2.0.4
rtree      : 1.2.0
pyproj     : 3.6.1
matplotlib : 3.8.4
mapclassify: 2.6.1
geopy      : 2.4.1
holoviews  : 1.17.1
hvplot     : 0.8.3
geoviews   : 1.9.6
stonesoup  : 1.2

gdf = read_file('../data/geolife_small.gpkg')
tc = mpd.TrajectoryCollection(gdf, 'trajectory_id', t='t')

original_traj = tc.trajectories[1]
print(original_traj)

Trajectory 2 (2009-06-29 07:02:25 to 2009-06-29 11:13:12) | Size: 897 | Length: 38764.6m
Bounds: (116.319212, 39.971703, 116.592616, 40.082514)
LINESTRING (116.590957 40.071961, 116.590905 40.072007, 116.590879 40.072027, 116.590915 40.072004, 

original_traj.plot(column='speed', vmax=20, **plot_defaults)

<Axes: >

Spatial generalization (DouglasPeuckerGeneralizer)

Try different tolerance settings and observe the results in line geometry and therefore also length:

dp_generalized  = mpd.DouglasPeuckerGeneralizer(original_traj).generalize(tolerance=0.001)
dp_generalized.plot(column='speed', vmax=20, **plot_defaults)

<Axes: >

dp_generalized 

Trajectory 2 (2009-06-29 07:02:25 to 2009-06-29 11:13:12) | Size: 31 | Length: 36921.9m
Bounds: (116.319709, 39.971775, 116.592616, 40.082369)
LINESTRING (116.590957 40.071961, 116.590367 40.073957, 116.590367 40.073957, 116.590367 40.073957, 

print('Original length: %s'%(original_traj.get_length()))
print('Generalized length: %s'%(dp_generalized.get_length()))

Original length: 38764.575482545886
Generalized length: 36921.91845209718

Temporal generalization (MinTimeDeltaGeneralizer)

An alternative generalization method is to down-sample the trajectory to ensure a certain time delta between records:

time_generalized = mpd.MinTimeDeltaGeneralizer(original_traj).generalize(tolerance=timedelta(minutes=1))
time_generalized.plot(column='speed', vmax=20, **plot_defaults)

<Axes: >

time_generalized.to_point_gdf().head(10)

	id	sequence	trajectory_id	tracker	geometry
t
2009-06-29 07:02:25	1556	1090	2	0	POINT (116.59096 40.07196)
2009-06-29 07:03:25	1569	1103	2	0	POINT (116.59069 40.07225)
2009-06-29 07:04:25	1582	1116	2	0	POINT (116.59037 40.07396)
2009-06-29 07:05:25	1595	1129	2	0	POINT (116.59260 40.07411)
2009-06-29 07:06:25	1610	1144	2	0	POINT (116.59258 40.07420)
2009-06-29 07:07:25	1623	1157	2	0	POINT (116.59235 40.07602)
2009-06-29 07:08:25	1635	1169	2	0	POINT (116.58939 40.07794)
2009-06-29 07:09:25	1647	1181	2	0	POINT (116.58911 40.08171)
2009-06-29 07:10:25	1659	1193	2	0	POINT (116.58829 40.08232)
2009-06-29 07:11:25	1672	1206	2	0	POINT (116.58689 40.08230)

original_traj.to_point_gdf().head(10)

	id	sequence	trajectory_id	tracker	geometry
t
2009-06-29 07:02:25	1556	1090	2	0	POINT (116.59096 40.07196)
2009-06-29 07:02:30	1557	1091	2	0	POINT (116.59091 40.07201)
2009-06-29 07:02:35	1558	1092	2	0	POINT (116.59088 40.07203)
2009-06-29 07:02:40	1559	1093	2	0	POINT (116.59091 40.07200)
2009-06-29 07:02:45	1560	1094	2	0	POINT (116.59096 40.07198)
2009-06-29 07:02:50	1561	1095	2	0	POINT (116.59101 40.07196)
2009-06-29 07:02:55	1562	1096	2	0	POINT (116.59099 40.07198)
2009-06-29 07:03:00	1563	1097	2	0	POINT (116.59098 40.07199)
2009-06-29 07:03:05	1564	1098	2	0	POINT (116.59097 40.07200)
2009-06-29 07:03:10	1565	1099	2	0	POINT (116.59097 40.07200)

Spatiotemporal generalization (TopDownTimeRatioGeneralizer)

tdtr_generalized = mpd.TopDownTimeRatioGeneralizer(original_traj).generalize(tolerance=0.001)

Let's compare this to the basic Douglas-Peucker result:

fig, axes = plt.subplots(nrows=1, ncols=2, figsize=(19,4))
tdtr_generalized.plot(ax=axes[0], column='speed', vmax=20, **plot_defaults)
dp_generalized.plot(ax=axes[1], column='speed', vmax=20, **plot_defaults)

<Axes: >

Let's compare this to the MinTimeDelta result:

fig, axes = plt.subplots(nrows=1, ncols=2, figsize=(19,4))
tdtr_generalized.plot(ax=axes[0], column='speed', vmax=20, **plot_defaults)
time_generalized.plot(ax=axes[1], column='speed', vmax=20, **plot_defaults)

<Axes: >