Skip to content

armgit / klad

Public Imported from GitHub
0

A drawing app built for agent/human collaboration

Rust
38.8 KB
Raw Blame
use crate::doc::Shape;
use crate::path::{Token, resample, tokens};
use anyhow::{Result, anyhow, bail};
use serde_json::{Map, Value};
use std::f32::consts::PI;

pub type P = [f32; 2];

const KAPPA: f32 = 0.552_284_8;
const NEAR: f32 = 1e-3;

#[derive(Clone, Copy, Debug, PartialEq)]
pub struct Anchor {
    pub at: P,
    pub inn: P,
    pub out: P,
}

impl Anchor {
    pub fn corner(at: P) -> Self {
        Self { at, inn: at, out: at }
    }

    pub fn has_in(&self) -> bool {
        dist(self.inn, self.at) > NEAR
    }

    pub fn has_out(&self) -> bool {
        dist(self.out, self.at) > NEAR
    }

    pub fn smooth(&self) -> bool {
        if !self.has_in() || !self.has_out() {
            return false;
        }
        let (a, b) = (sub(self.inn, self.at), sub(self.out, self.at));
        let cross = a[0] * b[1] - a[1] * b[0];
        let dot = a[0] * b[0] + a[1] * b[1];
        dot < 0.0 && cross.abs() <= 0.02 * len(a) * len(b)
    }

    fn shift(&mut self, by: P) {
        self.at = add(self.at, by);
        self.inn = add(self.inn, by);
        self.out = add(self.out, by);
    }
}

#[derive(Clone, Debug, PartialEq)]
pub struct Subpath {
    pub anchors: Vec<Anchor>,
    pub closed: bool,
}

fn add(a: P, b: P) -> P {
    [a[0] + b[0], a[1] + b[1]]
}

fn sub(a: P, b: P) -> P {
    [a[0] - b[0], a[1] - b[1]]
}

fn mul(a: P, k: f32) -> P {
    [a[0] * k, a[1] * k]
}

fn len(a: P) -> f32 {
    libm::sqrtf(a[0] * a[0] + a[1] * a[1])
}

fn dist(a: P, b: P) -> f32 {
    len(sub(a, b))
}

fn unit(a: P) -> P {
    let l = len(a);
    if l < 1e-9 { [0.0, 0.0] } else { mul(a, 1.0 / l) }
}

fn lerp(a: P, b: P, t: f32) -> P {
    [a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t]
}

fn cubic_at(p: [P; 4], t: f32) -> P {
    let u = 1.0 - t;
    let (a, b, c, d) = (u * u * u, 3.0 * u * u * t, 3.0 * u * t * t, t * t * t);
    [
        a * p[0][0] + b * p[1][0] + c * p[2][0] + d * p[3][0],
        a * p[0][1] + b * p[1][1] + c * p[2][1] + d * p[3][1],
    ]
}

pub fn point_on(p: [P; 4], t: f32) -> P {
    if dist(p[1], p[0]) <= NEAR && dist(p[2], p[3]) <= NEAR {
        lerp(p[0], p[3], t)
    } else {
        cubic_at(p, t)
    }
}

struct Builder {
    subs: Vec<Subpath>,
    current: Option<Subpath>,
}

impl Builder {
    fn start(&mut self, at: P) {
        self.finish();
        self.current = Some(Subpath {
            anchors: vec![Anchor::corner(at)],
            closed: false,
        });
    }

    fn last(&mut self) -> Result<&mut Subpath> {
        self.current.as_mut().ok_or_else(|| anyhow!("path must start with M"))
    }

    fn line(&mut self, to: P) -> Result<()> {
        self.last()?.anchors.push(Anchor::corner(to));
        Ok(())
    }

    fn cubic(&mut self, c1: P, c2: P, to: P) -> Result<()> {
        let sub = self.last()?;
        if let Some(prev) = sub.anchors.last_mut() {
            prev.out = c1;
        }
        sub.anchors.push(Anchor {
            at: to,
            inn: c2,
            out: to,
        });
        Ok(())
    }

    fn close(&mut self) {
        if let Some(mut path) = self.current.take() {
            let n = path.anchors.len();
            if n > 1 && dist(path.anchors[n - 1].at, path.anchors[0].at) <= NEAR {
                let last = path.anchors.pop().expect("two anchors");
                path.anchors[0].inn = add(path.anchors[0].at, sub(last.inn, last.at));
            }
            path.closed = true;
            self.subs.push(path);
        }
    }

    fn finish(&mut self) {
        if let Some(sub) = self.current.take() {
            self.subs.push(sub);
        }
    }
}

fn angle(u: P, v: P) -> f32 {
    libm::atan2f(u[0] * v[1] - u[1] * v[0], u[0] * v[0] + u[1] * v[1])
}

#[allow(clippy::too_many_arguments)]
fn arc(b: &mut Builder, from: P, r: P, rotation: f32, large: bool, sweep: bool, to: P) -> Result<()> {
    let (mut rx, mut ry) = (r[0].abs(), r[1].abs());
    if dist(from, to) < 1e-6 {
        return Ok(());
    }
    if rx < 1e-6 || ry < 1e-6 {
        return b.line(to);
    }
    let phi = rotation.to_radians();
    let (s, c) = (libm::sinf(phi), libm::cosf(phi));
    let (dx, dy) = ((from[0] - to[0]) / 2.0, (from[1] - to[1]) / 2.0);
    let (x1, y1) = (c * dx + s * dy, -s * dx + c * dy);
    let lambda = x1 * x1 / (rx * rx) + y1 * y1 / (ry * ry);
    if lambda > 1.0 {
        rx *= libm::sqrtf(lambda);
        ry *= libm::sqrtf(lambda);
    }
    let num = rx * rx * ry * ry - rx * rx * y1 * y1 - ry * ry * x1 * x1;
    let den = rx * rx * y1 * y1 + ry * ry * x1 * x1;
    let sign = if large == sweep { -1.0 } else { 1.0 };
    let coef = sign * libm::sqrtf((num / den).max(0.0));
    let (cxp, cyp) = (coef * rx * y1 / ry, -coef * ry * x1 / rx);
    let (cx, cy) = (
        c * cxp - s * cyp + (from[0] + to[0]) / 2.0,
        s * cxp + c * cyp + (from[1] + to[1]) / 2.0,
    );
    let start = [(x1 - cxp) / rx, (y1 - cyp) / ry];
    let end = [(-x1 - cxp) / rx, (-y1 - cyp) / ry];
    let theta = angle([1.0, 0.0], start);
    let mut delta = angle(start, end);
    if !sweep && delta > 0.0 {
        delta -= 2.0 * PI;
    } else if sweep && delta < 0.0 {
        delta += 2.0 * PI;
    }
    let pieces = (delta.abs() / (PI / 2.0)).ceil().max(1.0) as usize;
    let step = delta / pieces as f32;
    let k = 4.0 / 3.0 * libm::tanf(step / 4.0);
    let point = |t: f32| {
        let (st, ct) = (libm::sinf(t), libm::cosf(t));
        [cx + rx * ct * c - ry * st * s, cy + rx * ct * s + ry * st * c]
    };
    let slope = |t: f32| {
        let (st, ct) = (libm::sinf(t), libm::cosf(t));
        [-rx * st * c - ry * ct * s, -rx * st * s + ry * ct * c]
    };
    (0..pieces).try_for_each(|i| {
        let (t1, t2) = (theta + step * i as f32, theta + step * (i + 1) as f32);
        let end = if i + 1 == pieces { to } else { point(t2) };
        b.cubic(add(point(t1), mul(slope(t1), k)), sub(end, mul(slope(t2), k)), end)
    })
}

pub fn parse(d: &str) -> Result<Vec<Subpath>> {
    let tokens = tokens(d)?;
    let mut b = Builder {
        subs: Vec::new(),
        current: None,
    };
    let (mut pos, mut start): (P, P) = ([0.0, 0.0], [0.0, 0.0]);
    let (mut last_cubic, mut last_quad): (Option<P>, Option<P>) = (None, None);
    let mut command = ' ';
    let mut i = 0;
    let take = |i: &mut usize, n: usize| -> Result<Vec<f32>> {
        let values: Vec<f32> = tokens
            .get(*i..*i + n)
            .unwrap_or(&[])
            .iter()
            .map_while(|t| match t {
                Token::Number(v) => Some(*v),
                Token::Command(_) => None,
            })
            .collect();
        if values.len() != n {
            bail!("a path command needs {n} numbers there");
        }
        *i += n;
        Ok(values)
    };
    while i < tokens.len() {
        if let Token::Command(c) = tokens[i] {
            command = c;
            i += 1;
            if matches!(c, 'Z' | 'z') {
                b.close();
                pos = start;
                last_cubic = None;
                last_quad = None;
                continue;
            }
        }
        if command == ' ' {
            bail!("path must start with a command");
        }
        let upper = command.to_ascii_uppercase();
        if upper != 'M' && b.current.is_none() {
            b.start(pos);
        }
        let rel = command.is_ascii_lowercase();
        let at = |p: P, x: f32, y: f32| if rel { [p[0] + x, p[1] + y] } else { [x, y] };
        let (mut cubic_control, mut quad_control) = (None, None);
        match upper {
            'M' => {
                let v = take(&mut i, 2)?;
                pos = at(pos, v[0], v[1]);
                start = pos;
                b.start(pos);
                command = if rel { 'l' } else { 'L' };
            }
            'L' => {
                let v = take(&mut i, 2)?;
                pos = at(pos, v[0], v[1]);
                b.line(pos)?;
            }
            'H' => {
                let v = take(&mut i, 1)?;
                pos = [if rel { pos[0] + v[0] } else { v[0] }, pos[1]];
                b.line(pos)?;
            }
            'V' => {
                let v = take(&mut i, 1)?;
                pos = [pos[0], if rel { pos[1] + v[0] } else { v[0] }];
                b.line(pos)?;
            }
            'C' | 'S' => {
                let (c1, rest) = if upper == 'C' {
                    let v = take(&mut i, 6)?;
                    (at(pos, v[0], v[1]), v[2..].to_vec())
                } else {
                    let v = take(&mut i, 4)?;
                    (last_cubic.map_or(pos, |c| sub(mul(pos, 2.0), c)), v)
                };
                let (c2, end) = (at(pos, rest[0], rest[1]), at(pos, rest[2], rest[3]));
                b.cubic(c1, c2, end)?;
                cubic_control = Some(c2);
                pos = end;
            }
            'Q' | 'T' => {
                let (q, end) = if upper == 'Q' {
                    let v = take(&mut i, 4)?;
                    (at(pos, v[0], v[1]), at(pos, v[2], v[3]))
                } else {
                    let v = take(&mut i, 2)?;
                    (last_quad.map_or(pos, |c| sub(mul(pos, 2.0), c)), at(pos, v[0], v[1]))
                };
                b.cubic(lerp(pos, q, 2.0 / 3.0), lerp(end, q, 2.0 / 3.0), end)?;
                quad_control = Some(q);
                pos = end;
            }
            'A' => {
                let v = take(&mut i, 7)?;
                let end = at(pos, v[5], v[6]);
                arc(&mut b, pos, [v[0], v[1]], v[2], v[3] != 0.0, v[4] != 0.0, end)?;
                pos = end;
            }
            other => bail!("unknown path command {other:?}"),
        }
        last_cubic = cubic_control;
        last_quad = quad_control;
    }
    b.finish();
    if b.subs.iter().all(|s| s.anchors.len() < 2) {
        bail!("the path has no segments");
    }
    Ok(b.subs)
}

fn num(v: f32) -> String {
    let text = format!("{:.2}", v);
    let text = text.trim_end_matches('0').trim_end_matches('.');
    match text {
        "-0" | "" => "0".into(),
        t => t.into(),
    }
}

fn segment(out: &mut String, a: &Anchor, b: &Anchor) {
    if !a.has_out() && !b.has_in() {
        out.push_str(&format!(" L{} {}", num(b.at[0]), num(b.at[1])));
    } else {
        out.push_str(&format!(
            " C{} {} {} {} {} {}",
            num(a.out[0]),
            num(a.out[1]),
            num(b.inn[0]),
            num(b.inn[1]),
            num(b.at[0]),
            num(b.at[1])
        ));
    }
}

pub fn to_d(subs: &[Subpath]) -> String {
    let mut out = String::new();
    subs.iter().filter(|s| !s.anchors.is_empty()).for_each(|s| {
        let first = &s.anchors[0];
        if !out.is_empty() {
            out.push(' ');
        }
        out.push_str(&format!("M{} {}", num(first.at[0]), num(first.at[1])));
        s.anchors.windows(2).for_each(|w| segment(&mut out, &w[0], &w[1]));
        if s.closed {
            let last = &s.anchors[s.anchors.len() - 1];
            if last.has_out() || first.has_in() {
                segment(&mut out, last, first);
            }
            out.push_str(" Z");
        }
    });
    out
}

fn rect(x: f32, y: f32, w: f32, h: f32, radius: f32) -> Subpath {
    let r = radius.min(w / 2.0).min(h / 2.0).max(0.0);
    if r <= 0.0 {
        return Subpath {
            anchors: [[x, y], [x + w, y], [x + w, y + h], [x, y + h]]
                .into_iter()
                .map(Anchor::corner)
                .collect(),
            closed: true,
        };
    }
    let k = r * KAPPA;
    let round = |at: P, inn: P, out: P| Anchor {
        at,
        inn: add(at, inn),
        out: add(at, out),
    };
    let (x1, y1) = (x + w, y + h);
    Subpath {
        anchors: vec![
            round([x + r, y], [-k, 0.0], [0.0, 0.0]),
            round([x1 - r, y], [0.0, 0.0], [k, 0.0]),
            round([x1, y + r], [0.0, -k], [0.0, 0.0]),
            round([x1, y1 - r], [0.0, 0.0], [0.0, k]),
            round([x1 - r, y1], [k, 0.0], [0.0, 0.0]),
            round([x + r, y1], [0.0, 0.0], [-k, 0.0]),
            round([x, y1 - r], [0.0, k], [0.0, 0.0]),
            round([x, y + r], [0.0, 0.0], [0.0, -k]),
        ],
        closed: true,
    }
}

fn ellipse(cx: f32, cy: f32, rx: f32, ry: f32) -> Subpath {
    let (kx, ky) = (rx * KAPPA, ry * KAPPA);
    let anchor = |at: P, inn: P| Anchor {
        at,
        inn: add(at, inn),
        out: sub(at, inn),
    };
    Subpath {
        anchors: vec![
            anchor([cx + rx, cy], [0.0, -ky]),
            anchor([cx, cy + ry], [kx, 0.0]),
            anchor([cx - rx, cy], [0.0, ky]),
            anchor([cx, cy - ry], [-kx, 0.0]),
        ],
        closed: true,
    }
}

pub fn from_shape(shape: &Shape) -> Result<Vec<Subpath>> {
    Ok(match shape {
        Shape::Path { d } => parse(d)?,
        Shape::Rect { x, y, w, h, radius } => vec![rect(*x, *y, *w, *h, *radius)],
        Shape::Ellipse { cx, cy, rx, ry } => vec![ellipse(*cx, *cy, *rx, *ry)],
        Shape::Group { .. } => bail!("groups have no points; edit the paths inside"),
        Shape::Rays(_) => bail!("rays have no points; set their origin, angle, spread and length"),
        Shape::Image(_) => bail!("a picture has no points; V moves and scales it"),
        Shape::Text(_) => bail!("text has no points; change it in the inspector"),
        Shape::Scatter(_) | Shape::Repeat(_) | Shape::Mirror(_) => {
            bail!("a generator has no points; edit the shapes inside it")
        }
    })
}

pub fn locate(subs: &[Subpath], index: usize) -> Result<(usize, usize)> {
    let mut left = index;
    subs.iter()
        .enumerate()
        .find_map(|(s, sub)| {
            if left < sub.anchors.len() {
                Some((s, left))
            } else {
                left -= sub.anchors.len();
                None
            }
        })
        .ok_or_else(|| {
            let total: usize = subs.iter().map(|s| s.anchors.len()).sum();
            anyhow!(
                "point {index} does not exist; the path has points 0 to {}",
                total.saturating_sub(1)
            )
        })
}

pub fn anchors(subs: &[Subpath]) -> Vec<(usize, Anchor)> {
    subs.iter()
        .enumerate()
        .flat_map(|(s, sub)| sub.anchors.iter().map(move |a| (s, *a)))
        .collect()
}

fn neighbours(sub: &Subpath, i: usize) -> (Option<usize>, Option<usize>) {
    let n = sub.anchors.len();
    let prev = if i > 0 {
        Some(i - 1)
    } else {
        (sub.closed && n > 2).then_some(n - 1)
    };
    let next = if i + 1 < n {
        Some(i + 1)
    } else {
        (sub.closed && n > 2).then_some(0)
    };
    (prev, next)
}

pub fn segment_points(sub: &Subpath, i: usize) -> Option<[P; 4]> {
    let (_, next) = neighbours(sub, i);
    let (a, b) = (sub.anchors[i], sub.anchors[next?]);
    Some([a.at, a.out, b.inn, b.at])
}

pub fn flatten(subs: &[Subpath], step: f32) -> Vec<Vec<P>> {
    subs.iter()
        .map(|sub| {
            let count = if sub.closed {
                sub.anchors.len()
            } else {
                sub.anchors.len().saturating_sub(1)
            };
            let mut points = vec![sub.anchors[0].at];
            (0..count).filter_map(|i| segment_points(sub, i)).for_each(|p| {
                let hull = dist(p[0], p[1]) + dist(p[1], p[2]) + dist(p[2], p[3]);
                let n = (hull / step.max(0.1)).ceil().clamp(1.0, 400.0) as usize;
                points.extend((1..=n).map(|k| cubic_at(p, k as f32 / n as f32)));
            });
            points
        })
        .collect()
}

pub fn nearest(subs: &[Subpath], to: P) -> Option<(usize, f32, f32)> {
    let mut base = 0;
    subs.iter()
        .flat_map(|sub| {
            let first = base;
            base += sub.anchors.len();
            (0..sub.anchors.len()).filter_map(move |i| segment_points(sub, i).map(|p| (first + i, p)))
        })
        .map(|(index, p)| {
            let hull = dist(p[0], p[1]) + dist(p[1], p[2]) + dist(p[2], p[3]);
            let n = (hull / 2.0).ceil().clamp(8.0, 400.0) as usize;
            let (t, d) = (0..=n)
                .map(|k| {
                    let t = k as f32 / n as f32;
                    (t, dist(point_on(p, t), to))
                })
                .fold((0.0, f32::MAX), |best, c| if c.1 < best.1 { c } else { best });
            (index, t, d)
        })
        .fold(None, |best: Option<(usize, f32, f32)>, c| match best {
            Some(b) if b.2 <= c.2 => Some(b),
            _ => Some(c),
        })
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Side {
    In,
    Out,
}

#[derive(Clone, Debug, PartialEq)]
pub enum PathEdit {
    Convert,
    Move {
        points: Vec<usize>,
        by: P,
    },
    MoveTo {
        point: usize,
        to: P,
    },
    Handle {
        point: usize,
        side: Side,
        to: P,
        free: bool,
    },
    Insert {
        segment: usize,
        t: f32,
    },
    Add {
        at: P,
    },
    Remove {
        points: Vec<usize>,
    },
    Corner {
        points: Vec<usize>,
    },
    Smooth {
        points: Vec<usize>,
    },
    Simplify {
        tolerance: f32,
    },
}

fn indices(value: Value, key: &str) -> Result<Vec<usize>> {
    match value {
        Value::Number(n) => Ok(vec![
            n.as_u64().ok_or_else(|| anyhow!("{key} takes point numbers"))? as usize
        ]),
        other => serde_json::from_value(other).map_err(|_| anyhow!("{key} takes a point number or a list of them")),
    }
}

fn point(map: &mut Map<String, Value>, key: &str) -> Result<Option<P>> {
    map.remove(key)
        .map(|v| serde_json::from_value(v).map_err(|_| anyhow!("{key} takes [x, y]")))
        .transpose()
}

impl PathEdit {
    pub fn parse(map: &mut Map<String, Value>) -> Result<Self> {
        if let Some(v) = map.remove("move") {
            let points = indices(v, "move")?;
            return match (point(map, "to")?, point(map, "by")?, &points[..]) {
                (Some(to), None, [one]) => Ok(PathEdit::MoveTo { point: *one, to }),
                (None, Some(by), _) => Ok(PathEdit::Move { points, by }),
                (Some(_), None, _) => bail!("move with \"to\" takes one point; use \"by\": [dx, dy] for several"),
                _ => bail!("move needs \"to\": [x, y] or \"by\": [dx, dy]"),
            };
        }
        if let Some(v) = map.remove("handle") {
            let point_index = indices(v, "handle")?;
            let [one] = point_index[..] else {
                bail!("handle takes one point");
            };
            let free = map.remove("free").and_then(|v| v.as_bool()).unwrap_or(false);
            return match (point(map, "in")?, point(map, "out")?) {
                (Some(to), None) => Ok(PathEdit::Handle {
                    point: one,
                    side: Side::In,
                    to,
                    free,
                }),
                (None, Some(to)) => Ok(PathEdit::Handle {
                    point: one,
                    side: Side::Out,
                    to,
                    free,
                }),
                _ => bail!("handle needs \"in\": [x, y] or \"out\": [x, y]"),
            };
        }
        if let Some(v) = map.remove("insert") {
            let segment = indices(v, "insert")?;
            let [one] = segment[..] else {
                bail!("insert takes one segment (the point it starts at)");
            };
            let t = map.remove("t").and_then(|v| v.as_f64()).unwrap_or(0.5) as f32;
            if !(0.0..=1.0).contains(&t) {
                bail!("t must be within 0..1");
            }
            return Ok(PathEdit::Insert { segment: one, t });
        }
        if let Some(at) = point(map, "add")? {
            return Ok(PathEdit::Add { at });
        }
        if let Some(v) = map.remove("rm") {
            return Ok(PathEdit::Remove {
                points: indices(v, "rm")?,
            });
        }
        if let Some(v) = map.remove("corner") {
            return Ok(PathEdit::Corner {
                points: indices(v, "corner")?,
            });
        }
        if let Some(v) = map.remove("smooth") {
            return Ok(PathEdit::Smooth {
                points: indices(v, "smooth")?,
            });
        }
        if let Some(v) = map.remove("simplify") {
            let tolerance = v.as_f64().ok_or_else(|| anyhow!("simplify takes a tolerance in px"))? as f32;
            if !(0.01..=100.0).contains(&tolerance) {
                bail!("simplify tolerance must be within 0.01..100 px");
            }
            return Ok(PathEdit::Simplify { tolerance });
        }
        Ok(PathEdit::Convert)
    }

    pub fn apply(&self, subs: &mut Vec<Subpath>) -> Result<()> {
        match self {
            PathEdit::Convert => {}
            PathEdit::Move { points, by } => points.iter().try_for_each(|&i| {
                let (s, a) = locate(subs, i)?;
                subs[s].anchors[a].shift(*by);
                Ok::<_, anyhow::Error>(())
            })?,
            PathEdit::MoveTo { point, to } => {
                let (s, a) = locate(subs, *point)?;
                let anchor = &mut subs[s].anchors[a];
                anchor.shift(sub(*to, anchor.at));
            }
            PathEdit::Handle { point, side, to, free } => {
                let (s, a) = locate(subs, *point)?;
                let anchor = &mut subs[s].anchors[a];
                let keep = anchor.smooth() && !free;
                let (moved, other) = match side {
                    Side::In => (&mut anchor.inn, &mut anchor.out),
                    Side::Out => (&mut anchor.out, &mut anchor.inn),
                };
                *moved = *to;
                if keep {
                    let reach = dist(*other, anchor.at);
                    *other = add(anchor.at, mul(unit(sub(anchor.at, *to)), reach));
                }
            }
            PathEdit::Insert { segment, t } => {
                let (s, a) = locate(subs, *segment)?;
                let sub_path = &mut subs[s];
                let p = segment_points(sub_path, a)
                    .ok_or_else(|| anyhow!("point {segment} ends an open path; there is no segment after it"))?;
                let next = (a + 1) % sub_path.anchors.len();
                let straight = !sub_path.anchors[a].has_out() && !sub_path.anchors[next].has_in();
                let fresh = if straight {
                    Anchor::corner(lerp(p[0], p[3], *t))
                } else {
                    let (p01, p12, p23) = (lerp(p[0], p[1], *t), lerp(p[1], p[2], *t), lerp(p[2], p[3], *t));
                    let (p012, p123) = (lerp(p01, p12, *t), lerp(p12, p23, *t));
                    sub_path.anchors[a].out = p01;
                    sub_path.anchors[next].inn = p23;
                    Anchor {
                        at: lerp(p012, p123, *t),
                        inn: p012,
                        out: p123,
                    }
                };
                sub_path.anchors.insert(a + 1, fresh);
            }
            PathEdit::Add { at } => {
                let (segment, t, _) = nearest(subs, *at).ok_or_else(|| anyhow!("the path has no segments"))?;
                PathEdit::Insert { segment, t }.apply(subs)?;
            }
            PathEdit::Remove { points } => {
                let mut found: Vec<(usize, usize)> = points.iter().map(|&i| locate(subs, i)).collect::<Result<_>>()?;
                found.sort();
                found.dedup();
                found.iter().rev().for_each(|&(s, a)| {
                    subs[s].anchors.remove(a);
                });
                subs.retain(|s| s.anchors.len() >= 2);
                if subs.is_empty() {
                    bail!("that leaves no segments; remove the shape instead");
                }
            }
            PathEdit::Corner { points } => points.iter().try_for_each(|&i| {
                let (s, a) = locate(subs, i)?;
                let anchor = &mut subs[s].anchors[a];
                anchor.inn = anchor.at;
                anchor.out = anchor.at;
                Ok::<_, anyhow::Error>(())
            })?,
            PathEdit::Smooth { points } => points.iter().try_for_each(|&i| {
                let (s, a) = locate(subs, i)?;
                let sub_path = &subs[s];
                let (prev, next) = neighbours(sub_path, a);
                let here = sub_path.anchors[a].at;
                let before = prev.map(|p| sub_path.anchors[p].at);
                let after = next.map(|n| sub_path.anchors[n].at);
                let dir = unit(sub(after.unwrap_or(here), before.unwrap_or(here)));
                let anchor = &mut subs[s].anchors[a];
                anchor.inn = before.map_or(here, |b| sub(here, mul(dir, dist(here, b) / 3.0)));
                anchor.out = after.map_or(here, |n| add(here, mul(dir, dist(here, n) / 3.0)));
                Ok::<_, anyhow::Error>(())
            })?,
            PathEdit::Simplify { tolerance } => {
                *subs = subs.iter().map(|s| simplify(s, *tolerance)).collect();
            }
        }
        Ok(())
    }
}

fn turn(sub: &Subpath, i: usize) -> f32 {
    let (prev, next) = neighbours(sub, i);
    let (Some(p), Some(n)) = (prev, next) else {
        return PI;
    };
    let a = &sub.anchors[i];
    let into = if a.has_in() {
        sub_dir(a.at, a.inn)
    } else {
        sub_dir(a.at, sub.anchors[p].at)
    };
    let from = if a.has_out() {
        sub_dir(a.out, a.at)
    } else {
        sub_dir(sub.anchors[n].at, a.at)
    };
    angle(into, from).abs()
}

fn sub_dir(a: P, b: P) -> P {
    unit(sub(a, b))
}

pub fn fit_polyline(points: &[P], tolerance: f32) -> Subpath {
    let spaced = match points.len() {
        0 | 1 => points.to_vec(),
        _ => resample(points, tolerance.max(1.0)),
    };
    let rough = Subpath {
        anchors: spaced.iter().map(|p| Anchor::corner(*p)).collect(),
        closed: false,
    };
    match rough.anchors.len() {
        0..=2 => rough,
        _ => simplify(&rough, tolerance),
    }
}

fn simplify(source: &Subpath, tolerance: f32) -> Subpath {
    let n = source.anchors.len();
    let corners: Vec<usize> = (0..n).filter(|&i| turn(source, i) > 0.9).collect();
    let starts: Vec<usize> = match (source.closed, corners.first()) {
        (true, Some(_)) => corners.clone(),
        (true, None) => vec![0],
        (false, _) => std::iter::once(0)
            .chain(corners.iter().copied().filter(|&c| c > 0 && c + 1 < n))
            .collect(),
    };
    let runs: Vec<Vec<P>> = starts
        .iter()
        .enumerate()
        .map(|(k, &from)| {
            let to = match starts.get(k + 1) {
                Some(&next) => next,
                None if source.closed => starts[0] + n,
                None => n - 1,
            };
            let mut points = vec![source.anchors[from % n].at];
            (from..to).for_each(|i| {
                if let Some(p) = segment_points(source, i % n) {
                    let hull = dist(p[0], p[1]) + dist(p[1], p[2]) + dist(p[2], p[3]);
                    let steps = (hull / 2.0).ceil().clamp(1.0, 400.0) as usize;
                    points.extend((1..=steps).map(|s| cubic_at(p, s as f32 / steps as f32)));
                }
            });
            resample(&points, (tolerance / 2.0).clamp(0.5, 4.0))
        })
        .collect();
    let mut anchors: Vec<Anchor> = Vec::new();
    runs.iter().filter(|r| r.len() >= 2).for_each(|run| {
        let (first, last) = (run[0], run[run.len() - 1]);
        let curves = if straight(run, tolerance / 2.0) {
            vec![[first, first, last, last]]
        } else {
            fit(
                run,
                sub_dir(run[1], first),
                sub_dir(run[run.len() - 2], last),
                tolerance,
            )
        };
        curves.iter().for_each(|c| {
            match anchors.last_mut() {
                Some(last) if dist(last.at, c[0]) <= NEAR => last.out = c[1],
                _ => anchors.push(Anchor {
                    at: c[0],
                    inn: c[0],
                    out: c[1],
                }),
            }
            anchors.push(Anchor {
                at: c[3],
                inn: c[2],
                out: c[3],
            });
        });
    });
    if source.closed && anchors.len() > 1 && dist(anchors[0].at, anchors[anchors.len() - 1].at) <= NEAR {
        let last = anchors.pop().expect("two anchors");
        anchors[0].inn = last.inn;
    }
    let tidy = |p: P, at: P| if dist(p, at) < 0.05 { at } else { p };
    anchors.iter_mut().for_each(|a| {
        a.inn = tidy(a.inn, a.at);
        a.out = tidy(a.out, a.at);
    });
    Subpath {
        anchors,
        closed: source.closed,
    }
}

fn straight(points: &[P], within: f32) -> bool {
    let (a, b) = (points[0], points[points.len() - 1]);
    let along = unit(sub(b, a));
    let span = dist(a, b);
    span > NEAR
        && points.iter().all(|p| {
            let v = sub(*p, a);
            let t = v[0] * along[0] + v[1] * along[1];
            (v[0] * along[1] - v[1] * along[0]).abs() <= within && (-within..=span + within).contains(&t)
        })
}

fn chord(points: &[P]) -> Vec<f32> {
    let mut u = vec![0.0f32];
    points
        .windows(2)
        .for_each(|w| u.push(u[u.len() - 1] + dist(w[0], w[1])));
    let total = u[u.len() - 1].max(1e-9);
    u.iter_mut().for_each(|v| *v /= total);
    u
}

fn generate(points: &[P], u: &[f32], t1: P, t2: P) -> [P; 4] {
    let (first, last) = (points[0], points[points.len() - 1]);
    let (mut c00, mut c01, mut c11, mut x0, mut x1) = (0.0f32, 0.0f32, 0.0f32, 0.0f32, 0.0f32);
    points.iter().zip(u).for_each(|(p, &t)| {
        let s = 1.0 - t;
        let (b0, b1, b2, b3) = (s * s * s, 3.0 * s * s * t, 3.0 * s * t * t, t * t * t);
        let (a1, a2) = (mul(t1, b1), mul(t2, b2));
        c00 += a1[0] * a1[0] + a1[1] * a1[1];
        c01 += a1[0] * a2[0] + a1[1] * a2[1];
        c11 += a2[0] * a2[0] + a2[1] * a2[1];
        let rest = sub(*p, add(mul(first, b0 + b1), mul(last, b2 + b3)));
        x0 += a1[0] * rest[0] + a1[1] * rest[1];
        x1 += a2[0] * rest[0] + a2[1] * rest[1];
    });
    let det = c00 * c11 - c01 * c01;
    let span = dist(first, last);
    let (mut l, mut r) = if det.abs() > 1e-12 {
        ((x0 * c11 - c01 * x1) / det, (c00 * x1 - c01 * x0) / det)
    } else {
        (span / 3.0, span / 3.0)
    };
    if l < span * 1e-6 || r < span * 1e-6 {
        l = span / 3.0;
        r = span / 3.0;
    }
    [first, add(first, mul(t1, l)), add(last, mul(t2, r)), last]
}

fn worst(points: &[P], curve: [P; 4], u: &[f32]) -> (f32, usize) {
    points
        .iter()
        .zip(u)
        .enumerate()
        .map(|(i, (p, &t))| (dist(cubic_at(curve, t), *p), i))
        .fold((0.0, points.len() / 2), |best, c| if c.0 > best.0 { c } else { best })
}

fn reparameterize(points: &[P], u: &[f32], c: [P; 4]) -> Vec<f32> {
    let d1 = [
        mul(sub(c[1], c[0]), 3.0),
        mul(sub(c[2], c[1]), 3.0),
        mul(sub(c[3], c[2]), 3.0),
    ];
    let d2 = [mul(sub(d1[1], d1[0]), 2.0), mul(sub(d1[2], d1[1]), 2.0)];
    points
        .iter()
        .zip(u)
        .map(|(p, &t)| {
            let s = 1.0 - t;
            let q = cubic_at(c, t);
            let q1 = add(add(mul(d1[0], s * s), mul(d1[1], 2.0 * s * t)), mul(d1[2], t * t));
            let q2 = add(mul(d2[0], s), mul(d2[1], t));
            let diff = sub(q, *p);
            let num = diff[0] * q1[0] + diff[1] * q1[1];
            let den = q1[0] * q1[0] + q1[1] * q1[1] + diff[0] * q2[0] + diff[1] * q2[1];
            if den.abs() < 1e-9 {
                t
            } else {
                (t - num / den).clamp(0.0, 1.0)
            }
        })
        .collect()
}

fn fit(points: &[P], t1: P, t2: P, tolerance: f32) -> Vec<[P; 4]> {
    if points.len() == 2 {
        let span = dist(points[0], points[1]) / 3.0;
        return vec![[
            points[0],
            add(points[0], mul(t1, span)),
            add(points[1], mul(t2, span)),
            points[1],
        ]];
    }
    let mut u = chord(points);
    let mut curve = generate(points, &u, t1, t2);
    let (mut error, mut split) = worst(points, curve, &u);
    if error <= tolerance {
        return vec![curve];
    }
    if error <= tolerance * 4.0 {
        for _ in 0..4 {
            u = reparameterize(points, &u, curve);
            curve = generate(points, &u, t1, t2);
            (error, split) = worst(points, curve, &u);
            if error <= tolerance {
                return vec![curve];
            }
        }
    }
    let split = split.clamp(1, points.len() - 2);
    let center = sub_dir(points[split - 1], points[split + 1]);
    let mut left = fit(&points[..=split], t1, center, tolerance);
    left.extend(fit(&points[split..], mul(center, -1.0), t2, tolerance));
    left
}

#[cfg(test)]
mod tests {
    use super::*;
    use serde_json::json;

    fn near(a: P, b: P) -> bool {
        dist(a, b) < 0.02
    }

    fn edit(d: &str, value: Value) -> String {
        let mut subs = parse(d).unwrap();
        let mut map = value.as_object().unwrap().clone();
        PathEdit::parse(&mut map).unwrap().apply(&mut subs).unwrap();
        to_d(&subs)
    }

    #[test]
    fn paths_parse_to_anchors_and_write_back() {
        let d = "M10 10 L20 10 C25 10 30 15 30 20 Q30 30 20 30 Z M100 100 h10 v10";
        let subs = parse(d).unwrap();
        assert_eq!(subs.len(), 2);
        assert!(subs[0].closed && !subs[1].closed);
        assert_eq!(subs[0].anchors.len(), 4);
        assert!(near(subs[0].anchors[1].out, [25.0, 10.0]));
        assert!(near(subs[0].anchors[3].inn, [26.67, 30.0]));
        assert_eq!(subs[1].anchors.len(), 3);
        let text = to_d(&subs);
        assert_eq!(parse(&text).unwrap(), parse(&to_d(&parse(&text).unwrap())).unwrap());
        assert!(text.starts_with("M10 10 L20 10 C25 10 30 15 30 20 C"), "{text}");
        assert!(text.ends_with("M100 100 L110 100 L110 110"), "{text}");
        let closing = parse("M0 0 L10 0 L10 10 L0 0 Z").unwrap();
        assert_eq!(closing[0].anchors.len(), 3);
        assert_eq!(to_d(&closing), "M0 0 L10 0 L10 10 Z");
    }

    #[test]
    fn arcs_become_curves_that_end_where_they_should() {
        let subs = parse("M0 50 A50 50 0 0 1 100 50").unwrap();
        let line = &flatten(&subs, 1.0)[0];
        assert!(near(*line.last().unwrap(), [100.0, 50.0]));
        let top = line.iter().map(|p| p[1]).fold(f32::MAX, f32::min);
        assert!((top - 0.0).abs() < 0.2, "{top}");
        assert!(line.iter().all(|p| (dist(*p, [50.0, 50.0]) - 50.0).abs() < 0.1));
    }

    #[test]
    fn points_move_handles_follow_and_smooth_points_stay_smooth() {
        let d = "M0 0 C10 -10 20 -10 30 0 C40 10 50 10 60 0";
        assert_eq!(
            edit(d, json!({"move":1,"to":[30,5]})),
            "M0 0 C10 -10 20 -5 30 5 C40 15 50 10 60 0"
        );
        let subs = parse(&edit(d, json!({"handle":1,"out":[30,20]}))).unwrap();
        let a = subs[0].anchors[1];
        assert!(
            near(a.out, [30.0, 20.0]) && near(a.inn, [30.0, -14.14]) && a.smooth(),
            "{a:?}"
        );
        let free = parse(&edit(d, json!({"handle":1,"out":[30,20],"free":true}))).unwrap();
        assert!(!free[0].anchors[1].smooth());
        assert_eq!(
            edit(d, json!({"move":[0,2],"by":[1,2]})),
            "M1 2 C11 -8 20 -10 30 0 C40 10 51 12 61 2"
        );
        assert_eq!(edit("M0 0 L10 0 L20 0", json!({"corner":1})), "M0 0 L10 0 L20 0");
        let smooth = parse(&edit("M0 0 L10 10 L20 0", json!({"smooth":1}))).unwrap();
        assert!(smooth[0].anchors[1].smooth());
    }

    #[test]
    fn inserting_splits_a_curve_without_changing_it() {
        let d = "M0 0 C0 100 100 100 100 0";
        let split = parse(&edit(d, json!({"insert":0,"t":0.5}))).unwrap();
        assert_eq!(split[0].anchors.len(), 3);
        assert!(near(split[0].anchors[1].at, [50.0, 75.0]));
        let before = flatten(&parse(d).unwrap(), 0.5);
        let after = flatten(&split, 0.5);
        before[0].iter().step_by(7).for_each(|p| {
            let closest = after[0].iter().map(|q| dist(*p, *q)).fold(f32::MAX, f32::min);
            assert!(closest < 0.6, "{p:?} {closest}");
        });
        assert_eq!(edit("M0 0 L10 0", json!({"insert":0,"t":0.25})), "M0 0 L2.5 0 L10 0");
        assert_eq!(
            edit("M0 0 L10 0 L10 10 Z", json!({"insert":2})),
            "M0 0 L10 0 L10 10 L5 5 Z"
        );
        assert!(
            PathEdit::parse(&mut json!({"insert":1}).as_object().unwrap().clone())
                .unwrap()
                .apply(&mut parse("M0 0 L10 0").unwrap())
                .is_err()
        );
    }

    #[test]
    fn adding_a_point_near_a_segment_splits_it_there() {
        assert_eq!(
            edit("M0 0 L100 0 L100 100", json!({"add":[103,40]})),
            "M0 0 L100 0 L100 40 L100 100"
        );
    }

    #[test]
    fn removing_points_joins_their_neighbours() {
        assert_eq!(edit("M0 0 L10 0 L20 0 L30 5", json!({"rm":[1,2]})), "M0 0 L30 5");
        let mut subs = parse("M0 0 L10 0").unwrap();
        let mut map = json!({"rm":0}).as_object().unwrap().clone();
        assert!(PathEdit::parse(&mut map).unwrap().apply(&mut subs).is_err());
    }

    #[test]
    fn shapes_convert_to_the_same_outline() {
        let rect = from_shape(&Shape::Rect {
            x: 10.0,
            y: 20.0,
            w: 100.0,
            h: 50.0,
            radius: 0.0,
        })
        .unwrap();
        assert_eq!(to_d(&rect), "M10 20 L110 20 L110 70 L10 70 Z");
        let ellipse = from_shape(&Shape::Ellipse {
            cx: 0.0,
            cy: 0.0,
            rx: 40.0,
            ry: 20.0,
        })
        .unwrap();
        let outline = flatten(&ellipse, 0.5);
        assert!(outline[0].iter().all(|p| {
            let r = (p[0] / 40.0).powi(2) + (p[1] / 20.0).powi(2);
            (r - 1.0).abs() < 0.002
        }));
        let round = from_shape(&Shape::Rect {
            x: 0.0,
            y: 0.0,
            w: 100.0,
            h: 40.0,
            radius: 10.0,
        })
        .unwrap();
        assert_eq!(round[0].anchors.len(), 8);
        assert!(
            round[0].anchors[1..]
                .iter()
                .step_by(2)
                .all(|a| !a.has_in() || !a.has_out())
        );
    }

    #[test]
    fn simplify_turns_a_dense_polyline_into_few_smooth_points() {
        let points: Vec<String> = (0..=250)
            .map(|i| {
                let x = i as f32 * 4.0;
                let y = 300.0 + 80.0 * libm::sinf(x / 160.0) + 20.0 * libm::sinf(x / 37.0);
                format!("{x} {y:.2}")
            })
            .collect();
        let d = format!("M{} L{} L1000 600 L0 600 Z", points[0], points[1..].join(" L"));
        let dense = parse(&d).unwrap();
        let simple = parse(&edit(&d, json!({"simplify":1.0}))).unwrap();
        let (before, after) = (dense[0].anchors.len(), simple[0].anchors.len());
        assert!(after * 8 < before, "{before} -> {after}");
        let fine = flatten(&simple, 0.5);
        dense[0].anchors.iter().for_each(|a| {
            let closest = fine[0].iter().map(|q| dist(a.at, *q)).fold(f32::MAX, f32::min);
            assert!(closest < 1.6, "{:?} is {closest} away", a.at);
        });
        assert!(simple[0].anchors.iter().any(|a| a.at == [1000.0, 600.0] && !a.smooth()));
    }

    #[test]
    fn the_nearest_segment_is_found() {
        let subs = parse("M0 0 L100 0 L100 100").unwrap();
        let (segment, t, d) = nearest(&subs, [100.0, 30.0]).unwrap();
        assert_eq!(segment, 1);
        assert!((t - 0.3).abs() < 0.02 && d < 0.5);
    }
}