pub fn imai_iri(points: &[(f64, f64)], epsilon: f64) -> Vec<(f64, f64)>Expand description
Runs Imai–Iri: it returns the minimum-vertex polyline whose deviation from
points is ≤ epsilon (a BFS finds the fewest hops from the first to the last
point over the graph of “shortcut” segments that stay within epsilon of
every skipped point).
The exact core is ~O(n²) (Chan–Chin wedges, O(1) amortized per shortcut
check); very long inputs are RDP prefiltered with an adaptive slice of
the budget: the prefilter starts at epsilon/10 (Imai–Iri’s vertex count is
driven by its share, so it gets as much as possible: an even split kept
MORE points than plain RDP on real arcs) and escalates toward the epsilon/2
cap only while the prefiltered arc stays too big. Deviation bounds
compose, so the total stays ≤ epsilon; prefiltered results are near-optimal
rather than optimal.