use crate::utils::haversine::project_local_planar_km;
pub fn top_down_time_ratio_indices(
lats: &[f64],
lngs: &[f64],
times: &[f64],
epsilon_km: f64,
) -> Vec<usize> {
let n = lats.len();
if n <= 2 {
return (0..n).collect();
}
let coords = project_local_planar_km(lats, lngs);
let mut keep = vec![false; n];
keep[0] = true;
keep[n - 1] = true;
let mut stack: Vec<(usize, usize)> = vec![(0, n - 1)];
while let Some((start, end)) = stack.pop() {
if end <= start + 1 {
continue;
}
let t0 = times[start];
let t1 = times[end];
let de = t1 - t0;
let (x0, y0) = coords[start];
let (x1, y1) = coords[end];
let dx = x1 - x0;
let dy = y1 - y0;
let mut farthest_idx = start + 1;
let mut farthest_dist = -1.0f64;
for idx in (start + 1)..end {
let di = times[idx] - t0;
let ratio = if de != 0.0 { di / de } else { 0.0 };
let calc_x = x0 + dx * ratio;
let calc_y = y0 + dy * ratio;
let (px, py) = coords[idx];
let ddx = px - calc_x;
let ddy = py - calc_y;
let dist = (ddx * ddx + ddy * ddy).sqrt();
if dist > farthest_dist {
farthest_dist = dist;
farthest_idx = idx;
}
}
if farthest_dist > epsilon_km {
keep[farthest_idx] = true;
stack.push((start, farthest_idx));
stack.push((farthest_idx, end));
}
}
(0..n).filter(|&i| keep[i]).collect()
}