use std::collections::VecDeque;
use crate::utils::haversine::project_local_planar_km;
use super::corridor::farthest_feasible_index;
fn forward_wedge_path(coords: &[(f64, f64)], tolerance: f64) -> Vec<usize> {
let n = coords.len();
if n == 0 {
return Vec::new();
}
if n == 1 {
return vec![0];
}
let mut path = vec![0usize];
let mut anchor = 0usize;
while anchor < n - 1 {
let next = farthest_feasible_index(coords, anchor, tolerance);
path.push(next);
anchor = next;
}
path
}
fn backward_wedge_path(coords: &[(f64, f64)], tolerance: f64) -> Vec<usize> {
let n = coords.len();
let reversed: Vec<(f64, f64)> = coords.iter().rev().copied().collect();
let reversed_path = forward_wedge_path(&reversed, tolerance);
let mut path: Vec<usize> = reversed_path.into_iter().map(|idx| n - 1 - idx).collect();
path.reverse();
path
}
pub fn chan_chin_indices(lats: &[f64], lngs: &[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 forward = forward_wedge_path(&coords, epsilon_km);
let backward = backward_wedge_path(&coords, epsilon_km);
let mut adjacency: Vec<Vec<usize>> = vec![Vec::new(); n];
for window in forward.windows(2).chain(backward.windows(2)) {
let (a, b) = (window[0], window[1]);
adjacency[a].push(b);
adjacency[b].push(a);
}
let mut previous: Vec<Option<usize>> = vec![None; n];
let mut visited = vec![false; n];
let mut queue = VecDeque::new();
visited[0] = true;
queue.push_back(0usize);
while let Some(u) = queue.pop_front() {
if u == n - 1 {
break;
}
for &v in &adjacency[u] {
if !visited[v] {
visited[v] = true;
previous[v] = Some(u);
queue.push_back(v);
}
}
}
let mut path = vec![n - 1];
let mut current = n - 1;
while current != 0 {
current = previous[current].expect("forward pass guarantees 0..n-1 connectivity");
path.push(current);
}
path.reverse();
path
}