movingpandas.Trajectory.lcss_distance#

Trajectory.lcss_distance(other, epsilon, delta=None)#

Return the Longest Common Subsequence (LCSS) distance to the other trajectory or geometric object.

LCSS counts how many points can be matched between the two ordered sequences such that each matched pair is within epsilon and, if delta is given, no more than delta positions apart in the sequences. The similarity is that count divided by the length of the shorter sequence, and the returned distance is 1 - similarity. So 0 means every point of the shorter trajectory found a match, i.e. it is essentially a (noisy) subsequence of the other, and 1 means no points match within epsilon. Points of the longer trajectory that are left over do not count against the result. Because unmatched points are simply skipped, LCSS is more robust to noise and outliers than DTW and Fréchet distance, which must account for every point. Values are only comparable between trajectory pairs when they were computed with the same epsilon and delta.

The similarity is computed with a vectorized dynamic program that keeps only two anti-diagonals of the DP matrix in memory. Without delta the computation takes O(n*m) time and O(n+m) memory. With delta only the band of cells at most delta positions off the diagonal is evaluated, taking O((n+m) * delta) time, so a small delta makes the computation linear in trajectory length.

Distances are computed using Euclidean geometry, so a UserWarning is raised for trajectories in a geographic (lat/lon) CRS. Project to a suitable planar CRS first for meaningful results.

Parameters:

  • other (Trajectory, LineString, or Point) – Other trajectory or geometric object

  • epsilon (float) – Spatial matching threshold, in CRS units. Two points are considered a match when their Euclidean distance is at most epsilon.

  • delta (int, optional) – Maximum allowed difference between the sequence positions of two matched points. Default None (no constraint on sequence alignment).

Returns:

LCSS distance in the range [0, 1] (dimensionless)

Return type:

float