cvx_analytics/
trajectory.rs

1//! Trajectory distance measures for comparing entity evolutions.
2//!
3//! Provides measures that compare *sequences* of vectors, not individual points.
4//! This is a fundamentally different operation from kNN search.
5//!
6//! # Available Measures
7//!
8//! | Measure | Complexity | Properties |
9//! |---------|-----------|-----------|
10//! | [`discrete_frechet`] | O(n×m) | Respects ordering, handles unequal lengths |
11//! | Signature distance | O(K²) | Universal features, very fast (see [`signatures`]) |
12//!
13//! Signature distance is recommended as the default: it's O(K²) per comparison
14//! and captures all order-dependent temporal dynamics. Fréchet is offered as
15//! the exact alternative when ordering-sensitive geometry matters.
16//!
17//! # References
18//!
19//! - Eiter, T. & Mannila, H. (1994). Computing discrete Fréchet distance.
20//! - Toohey, K. & Duckham, M. (2015). Trajectory Similarity Measures. ACM SIGSPATIAL.
21
22/// Compute the discrete Fréchet distance between two trajectories.
23///
24/// The Fréchet distance measures the maximum minimum distance between
25/// corresponding points of two curves when traversed monotonically.
26/// Intuitively: the shortest leash needed to walk a dog along path B
27/// while you walk along path A, both moving only forward.
28///
29/// # Arguments
30///
31/// * `a` - First trajectory: sequence of vectors (timestamps ignored).
32/// * `b` - Second trajectory.
33///
34/// # Complexity
35///
36/// O(n × m) time and space, where n = |a|, m = |b|.
37pub fn discrete_frechet(a: &[&[f32]], b: &[&[f32]]) -> f64 {
38    let n = a.len();
39    let m = b.len();
40    if n == 0 || m == 0 {
41        return f64::INFINITY;
42    }
43
44    // DP table: dp[i][j] = Fréchet distance considering a[0..=i] and b[0..=j]
45    let mut dp = vec![vec![f64::NEG_INFINITY; m]; n];
46
47    for i in 0..n {
48        for (j, bj) in b.iter().enumerate().take(m) {
49            let d = l2_dist(a[i], bj);
50            if i == 0 && j == 0 {
51                dp[i][j] = d;
52            } else if i == 0 {
53                dp[i][j] = dp[i][j - 1].max(d);
54            } else if j == 0 {
55                dp[i][j] = dp[i - 1][j].max(d);
56            } else {
57                let prev = dp[i - 1][j].min(dp[i][j - 1]).min(dp[i - 1][j - 1]);
58                dp[i][j] = prev.max(d);
59            }
60        }
61    }
62
63    dp[n - 1][m - 1]
64}
65
66/// Compute discrete Fréchet distance from timestamped trajectories.
67///
68/// Convenience wrapper that extracts vectors from (timestamp, vector) pairs.
69pub fn discrete_frechet_temporal(a: &[(i64, &[f32])], b: &[(i64, &[f32])]) -> f64 {
70    let va: Vec<&[f32]> = a.iter().map(|(_, v)| *v).collect();
71    let vb: Vec<&[f32]> = b.iter().map(|(_, v)| *v).collect();
72    discrete_frechet(&va, &vb)
73}
74
75/// L2 distance between two vectors.
76#[inline]
77fn l2_dist(a: &[f32], b: &[f32]) -> f64 {
78    a.iter()
79        .zip(b.iter())
80        .map(|(x, y)| {
81            let d = *x as f64 - *y as f64;
82            d * d
83        })
84        .sum::<f64>()
85        .sqrt()
86}
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    #[test]
93    fn frechet_identical_paths() {
94        let a: Vec<&[f32]> = vec![&[0.0, 0.0], &[1.0, 0.0], &[1.0, 1.0]];
95        let b: Vec<&[f32]> = vec![&[0.0, 0.0], &[1.0, 0.0], &[1.0, 1.0]];
96        let d = discrete_frechet(&a, &b);
97        assert!(
98            d < 1e-10,
99            "identical paths should have distance ~0, got {d}"
100        );
101    }
102
103    #[test]
104    fn frechet_shifted_paths() {
105        let a: Vec<&[f32]> = vec![&[0.0, 0.0], &[1.0, 0.0], &[2.0, 0.0]];
106        let b: Vec<&[f32]> = vec![&[0.0, 1.0], &[1.0, 1.0], &[2.0, 1.0]];
107        let d = discrete_frechet(&a, &b);
108        // Parallel paths offset by 1.0 → Fréchet = 1.0
109        assert!(
110            (d - 1.0).abs() < 1e-10,
111            "parallel offset should be 1.0, got {d}"
112        );
113    }
114
115    #[test]
116    fn frechet_different_lengths() {
117        let a: Vec<&[f32]> = vec![&[0.0], &[1.0], &[2.0]];
118        let b: Vec<&[f32]> = vec![&[0.0], &[2.0]];
119        let d = discrete_frechet(&a, &b);
120        // b jumps from 0→2 while a goes 0→1→2. Fréchet = 1.0 (at a[1], b[0] or b[1])
121        assert!(d <= 1.0 + 1e-10, "should handle unequal lengths, got {d}");
122    }
123
124    #[test]
125    fn frechet_preserves_order() {
126        // Path A: right then up
127        let a: Vec<&[f32]> = vec![&[0.0, 0.0], &[1.0, 0.0], &[1.0, 1.0]];
128        // Path B: up then right (reversed order)
129        let b: Vec<&[f32]> = vec![&[0.0, 0.0], &[0.0, 1.0], &[1.0, 1.0]];
130        let d = discrete_frechet(&a, &b);
131        // Same endpoints but different paths → nonzero Fréchet
132        assert!(
133            d > 0.5,
134            "different-order paths should have positive distance, got {d}"
135        );
136    }
137
138    #[test]
139    fn frechet_empty_paths() {
140        let a: Vec<&[f32]> = vec![];
141        let b: Vec<&[f32]> = vec![&[0.0]];
142        assert!(discrete_frechet(&a, &b).is_infinite());
143    }
144
145    #[test]
146    fn frechet_temporal_wrapper() {
147        let a: Vec<(i64, &[f32])> = vec![(0, &[0.0f32, 0.0] as &[f32]), (1, &[1.0f32, 1.0])];
148        let b: Vec<(i64, &[f32])> = vec![(0, &[0.0f32, 0.0] as &[f32]), (1, &[1.0f32, 1.0])];
149        let d = discrete_frechet_temporal(&a, &b);
150        assert!(d < 1e-10);
151    }
152}
cvx_analytics/trajectory.rs

cvx_analytics/
trajectory.rs
