use rayon::prelude::*;
use crate::utils::haversine::haversine_km;
fn cumulative_arc_length_km(lats: &[f64], lngs: &[f64]) -> Vec<f64> {
let n = lats.len();
let mut cum = vec![0.0; n];
for i in 1..n {
cum[i] = cum[i - 1] + haversine_km(lats[i - 1], lngs[i - 1], lats[i], lngs[i]);
}
cum
}
fn resample_by_arc_length(
lats: &[f64],
lngs: &[f64],
cum_dist: &[f64],
n_points: usize,
) -> Vec<(f64, f64)> {
let total = *cum_dist.last().unwrap_or(&0.0);
if total <= 0.0 {
return vec![(lats[0], lngs[0]); n_points];
}
(0..n_points)
.map(|i| {
let target = total * (i as f64) / (n_points - 1) as f64;
let idx = cum_dist.partition_point(|&d| d < target);
if idx == 0 {
(lats[0], lngs[0])
} else if idx >= cum_dist.len() {
(lats[lats.len() - 1], lngs[lngs.len() - 1])
} else {
let d0 = cum_dist[idx - 1];
let d1 = cum_dist[idx];
let frac = if d1 > d0 {
(target - d0) / (d1 - d0)
} else {
0.0
};
let lat = lats[idx - 1] + (lats[idx] - lats[idx - 1]) * frac;
let lng = lngs[idx - 1] + (lngs[idx] - lngs[idx - 1]) * frac;
(lat, lng)
}
})
.collect()
}
pub fn distance_geometry_signature(
lats: &[f64],
lngs: &[f64],
depth: usize,
) -> Result<Vec<f64>, String> {
if lats.len() != lngs.len() {
return Err("lats and lngs must have the same length".to_string());
}
if lats.len() < 2 {
return Err(
"a trajectory needs at least 2 points to compute a shape signature".to_string(),
);
}
if depth == 0 {
return Err("depth must be >= 1".to_string());
}
let cum_dist = cumulative_arc_length_km(lats, lngs);
let total = *cum_dist.last().unwrap();
let mut signature = Vec::with_capacity(depth * (depth + 1) / 2);
for level in 1..=depth {
let points = resample_by_arc_length(lats, lngs, &cum_dist, level + 1);
for pair in points.windows(2) {
let (lat0, lng0) = pair[0];
let (lat1, lng1) = pair[1];
let chord_km = haversine_km(lat0, lng0, lat1, lng1);
signature.push(if total > 0.0 { chord_km / total } else { 0.0 });
}
}
Ok(signature)
}
pub fn batch_distance_geometry_signatures(
trajectories: &[(Vec<f64>, Vec<f64>)],
depth: usize,
) -> Result<Vec<Vec<f64>>, String> {
trajectories
.par_iter()
.map(|(lats, lngs)| distance_geometry_signature(lats, lngs, depth))
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn straight_line_signature_is_all_ones_scaled_by_level() {
let lats = vec![0.0, 0.0, 0.0, 0.0, 0.0];
let lngs = vec![0.0, 1.0, 2.0, 3.0, 4.0];
let sig = distance_geometry_signature(&lats, &lngs, 3).unwrap();
assert_eq!(sig.len(), 6);
assert!((sig[0] - 1.0).abs() < 1e-6);
assert!((sig[1] - 0.5).abs() < 1e-6);
assert!((sig[2] - 0.5).abs() < 1e-6);
for &v in &sig[3..6] {
assert!((v - 1.0 / 3.0).abs() < 1e-6);
}
}
#[test]
fn signature_is_translation_and_rotation_invariant() {
let lats_a = vec![0.0, 0.1, 0.2, 0.1];
let lngs_a = vec![0.0, 0.1, 0.0, -0.1];
let sig_a = distance_geometry_signature(&lats_a, &lngs_a, 4).unwrap();
let lats_b: Vec<f64> = lats_a.iter().map(|v| v + 1.0).collect();
let lngs_b: Vec<f64> = lngs_a.iter().map(|v| v + 2.0).collect();
let sig_b = distance_geometry_signature(&lats_b, &lngs_b, 4).unwrap();
for (a, b) in sig_a.iter().zip(sig_b.iter()) {
assert!((a - b).abs() < 1e-3, "expected {a} ~= {b}");
}
}
#[test]
fn rejects_mismatched_lengths_and_short_trajectories() {
assert!(distance_geometry_signature(&[0.0], &[0.0, 1.0], 2).is_err());
assert!(distance_geometry_signature(&[0.0], &[0.0], 2).is_err());
assert!(distance_geometry_signature(&[0.0, 1.0], &[0.0, 1.0], 0).is_err());
}
}