use super::queue::VertexQueue;
use super::{Vertex, VertexSource};
use crate::Point;
use crate::numeric::sum_of_products;
use crate::path::PathCode;
#[derive(Clone, Debug)]
#[expect(
clippy::struct_excessive_bools,
reason = "mirrors the flags of the C++ state machine"
)]
pub struct Simplifier<I> {
source: I,
threshold_sq: Option<f64>,
queue: VertexQueue<9>,
finished: bool,
moveto: bool,
after_moveto: bool,
clipped: bool,
init: Option<Point>,
last: Point,
orig: Point,
orig_norm2: f64,
forward_max_norm2: f64,
backward_max_norm2: f64,
last_forward_max: bool,
last_backward_max: bool,
next: Point,
next_backward: Point,
run_start: Point,
}
impl<I: VertexSource> Simplifier<I> {
pub(super) fn new(source: I, threshold: Option<f64>) -> Self {
Self {
source,
threshold_sq: threshold.map(|t| t * t),
queue: VertexQueue::default(),
finished: false,
moveto: true,
after_moveto: false,
clipped: false,
init: None,
last: Point::ORIGIN,
orig: Point::ORIGIN,
orig_norm2: 0.0,
forward_max_norm2: 0.0,
backward_max_norm2: 0.0,
last_forward_max: false,
last_backward_max: false,
next: Point::ORIGIN,
next_backward: Point::ORIGIN,
run_start: Point::ORIGIN,
}
}
fn start_run(&mut self, p: Point) {
self.orig = p - self.last;
self.orig_norm2 = norm2(self.orig);
self.forward_max_norm2 = self.orig_norm2;
self.last_forward_max = true;
self.backward_max_norm2 = 0.0;
self.last_backward_max = false;
}
fn push_run(&mut self, p: Point) {
if self.backward_max_norm2 > 0.0 {
let (first, second) = if self.last_forward_max {
(self.next_backward, self.next)
} else {
(self.next, self.next_backward)
};
self.queue.push(Vertex::line_to(first));
self.queue.push(Vertex::line_to(second));
} else {
self.queue.push(Vertex::line_to(self.next));
}
if self.clipped {
self.queue.push(Vertex::move_to(self.last));
} else if !self.last_forward_max && !self.last_backward_max {
self.queue.push(Vertex::line_to(self.last));
}
self.start_run(p);
self.run_start = self.queue.last().map_or(self.last, |v| v.point);
self.last = p;
self.next = p;
self.clipped = false;
}
fn final_code(&self) -> PathCode {
if self.moveto || self.after_moveto {
PathCode::MoveTo
} else {
PathCode::LineTo
}
}
fn finish(&mut self) {
if self.orig_norm2 != 0.0 {
self.queue.push_new(self.final_code(), self.next);
if self.backward_max_norm2 > 0.0 {
self.queue.push_new(self.final_code(), self.next_backward);
}
self.moveto = false;
}
self.queue.push_new(self.final_code(), self.last);
self.moveto = false;
self.finished = true;
}
fn next_simplified(&mut self, threshold_sq: f64) -> Option<Vertex> {
if let Some(vertex) = self.queue.pop() {
return Some(vertex);
}
if self.finished {
return None;
}
let mut exhausted = true;
while let Some(vertex) = self.source.next() {
let mut p = vertex.point;
if self.moveto || vertex.code == PathCode::MoveTo {
if self.orig_norm2 != 0.0 && !self.after_moveto {
self.push_run(p);
}
self.after_moveto = true;
self.init = p.is_finite().then_some(p);
self.last = p;
self.moveto = false;
self.orig_norm2 = 0.0;
self.backward_max_norm2 = 0.0;
self.clipped = true;
if !self.queue.is_empty() {
exhausted = false;
break;
}
continue;
}
self.after_moveto = false;
if vertex.code == PathCode::ClosePoly {
match self.init {
Some(init) => p = init,
None => continue,
}
}
if self.orig_norm2 == 0.0 {
if self.clipped {
self.queue.push(Vertex::move_to(self.last));
self.clipped = false;
}
self.start_run(p);
self.run_start = self.last;
self.last = p;
self.next = p;
continue;
}
let tot = p - self.run_start;
let tot_dot = sum_of_products(self.orig.x, tot.x, self.orig.y, tot.y);
let para = Point::new(
tot_dot * self.orig.x / self.orig_norm2,
tot_dot * self.orig.y / self.orig_norm2,
);
let perp = tot - para;
let perp_norm2 = norm2(perp);
if perp_norm2 < threshold_sq {
let para_norm2 = norm2(para);
self.last_forward_max = false;
self.last_backward_max = false;
if tot_dot > 0.0 {
if para_norm2 > self.forward_max_norm2 {
self.last_forward_max = true;
self.forward_max_norm2 = para_norm2;
self.next = p;
}
} else if para_norm2 > self.backward_max_norm2 {
self.last_backward_max = true;
self.backward_max_norm2 = para_norm2;
self.next_backward = p;
}
self.last = p;
continue;
}
self.push_run(p);
exhausted = false;
break;
}
if exhausted {
self.finish();
}
self.queue.pop()
}
}
fn norm2(v: Point) -> f64 {
sum_of_products(v.x, v.x, v.y, v.y)
}
impl<I: VertexSource> Iterator for Simplifier<I> {
type Item = Vertex;
fn next(&mut self) -> Option<Vertex> {
match self.threshold_sq {
Some(threshold_sq) => self.next_simplified(threshold_sq),
None => self.source.next(),
}
}
}
impl<I: VertexSource> VertexSource for Simplifier<I> {
fn rewind(&mut self) {
self.queue.clear();
self.finished = false;
self.moveto = true;
self.source.rewind();
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::path::Path;
fn p(x: f64, y: f64) -> Point {
Point::new(x, y)
}
fn simplified(path: &Path) -> Vec<Vertex> {
path.iter_vertices().simplify(Some(1.0 / 9.0)).collect()
}
#[test]
fn straight_runs_collapse_with_matplotlibs_repeated_end() {
let path = Path::polyline((0..200).map(|i| p(f64::from(i), 0.0)).collect());
assert_eq!(
simplified(&path),
vec![
Vertex::move_to(p(0.0, 0.0)),
Vertex::line_to(p(199.0, 0.0)),
Vertex::line_to(p(199.0, 0.0)),
]
);
}
#[test]
fn backward_excursions_are_kept() {
let path = Path::polyline(vec![
p(0.0, 0.0),
p(1.0, 0.0),
p(2.0, 0.0),
p(3.0, 0.0),
p(2.0, 0.0),
p(1.0, 0.0),
p(5.0, 0.0),
]);
let xs: Vec<f64> = simplified(&path).iter().map(|v| v.point.x).collect();
assert_eq!(xs, vec![0.0, 5.0, 5.0]);
let path = Path::polyline(vec![p(0.0, 0.0), p(3.0, 0.0), p(-2.0, 0.0), p(1.0, 0.0)]);
let xs: Vec<f64> = simplified(&path).iter().map(|v| v.point.x).collect();
assert_eq!(xs, vec![0.0, 3.0, -2.0, 1.0]);
}
#[test]
fn corners_are_preserved() {
let path = Path::polyline(vec![
p(0.0, 0.0),
p(1.0, 0.0),
p(2.0, 0.0),
p(2.0, 1.0),
p(2.0, 2.0),
]);
let points: Vec<Point> = simplified(&path).iter().map(|v| v.point).collect();
assert_eq!(
points,
vec![p(0.0, 0.0), p(2.0, 0.0), p(2.0, 2.0), p(2.0, 2.0)]
);
}
#[test]
fn closures_become_lines_to_the_start() {
let path = Path::polygon([p(0.0, 0.0), p(1.0, 0.0), p(1.0, 1.0), p(0.0, 1.0)]);
let out = simplified(&path);
assert!(out.iter().all(|v| v.code != PathCode::ClosePoly));
assert_eq!(out.last().map(|v| v.point), Some(p(0.0, 0.0)));
}
}