Skip to main content

imai_iri

Function imai_iri 

Source
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.