VectorCraft: An open-source, vector art tool written by scratch in pure Rust
//! Object → Path commands: Simplify, Smooth, Remove redundant points, Add Anchor Points, Average,
//! Join, Split Into Grid.
use std::collections::{BTreeMap, BTreeSet};
use kurbo::{CubicBez, ParamCurveArclen, Point, Rect, Vec2};
use vectorcraft_geom::{Anchor, AnchorKind, PathData, SubPath};
use crate::boolean::{Seg, segs_to_subpath};
use crate::fit::{end_tangent, fit_cubics, fit_single, fit_single_from, is_straight, sample, start_tangent};
/// Options for [`simplify_with`].
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct SimplifyOptions {
/// Maximum distance (document points) between the original and simplified path.
pub tolerance: f64,
/// Anchors where the path turns by more than this many degrees stay corners.
pub corner_angle_deg: f64,
/// Produce only straight segments ("Convert to Straight Lines").
pub straight_lines: bool,
/// How far (points, the spread of a Gaussian along the path) the path is smoothed before it is
/// refitted, so that bumps and jags come out as one curve ([`smooth_level`]); 0 for none.
pub smooth: f64,
}
impl Default for SimplifyOptions {
fn default() -> Self {
Self { tolerance: 0.5, corner_angle_deg: 30.0, straight_lines: false, smooth: 0.0 }
}
}
/// Simplify with the default corner threshold (30°).
pub fn simplify(path: &PathData, tolerance: f64) -> PathData {
simplify_with(path, &SimplifyOptions { tolerance, ..Default::default() })
}
/// The Simplify slider's level for a tolerance of 1 pt, the middle of its scale.
pub const SIMPLIFY_LEVEL: f64 = 50.0;
/// The tolerance (points) of Simplify slider level `level`, from 0 (the fewest anchor points) to
/// 100 (the closest to the original): 1 pt at [`SIMPLIFY_LEVEL`], doubled for every 10 levels below
/// it and halved for every 10 above, so level 0 is 32 pt and level 100 is 1/32 pt. A level outside
/// 0..=100 counts as the nearer end, and one that is not a number counts as [`SIMPLIFY_LEVEL`].
pub fn simplify_level_tolerance(level: f64) -> f64 {
let level = if level.is_finite() { level.clamp(0.0, 100.0) } else { SIMPLIFY_LEVEL };
((SIMPLIFY_LEVEL - level) / 10.0).exp2()
}
/// Auto-Simplify's level for paths whose bounds are `size` points on their longer side: the lowest
/// whole level whose tolerance ([`simplify_level_tolerance`]) is at most 1/400 of `size`. It returns
/// level 100 for a size of 0 or one that is not a number, and for a size under 12.5 pt, where no
/// level is that close.
pub fn auto_simplify_level(size: f64) -> f64 {
let target = size / 400.0;
if !(target.is_finite() && target > 0.0) {
return 100.0;
}
(SIMPLIFY_LEVEL - 10.0 * target.log2()).ceil().clamp(0.0, 100.0)
}
/// Simplify never adds anchors: keep whichever subpath is smaller.
fn no_worse(original: &SubPath, fitted: SubPath) -> SubPath {
if fitted.anchors.len() > original.anchors.len() { original.clone() } else { fitted }
}
fn subpath_segs(sp: &SubPath) -> Vec<Seg> {
(0..sp.segment_count()).map(|i| Seg { c: sp.segment(i), line: sp.segment_is_line(i) }).collect()
}
fn turn_deg(a: &Seg, b: &Seg) -> f64 {
let d = end_tangent(&a.c).dot(start_tangent(&b.c)).clamp(-1.0, 1.0);
d.acos().to_degrees()
}
/// Least-squares Bézier refit of every subpath, keeping corners sharper than the threshold.
pub fn simplify_with(path: &PathData, opts: &SimplifyOptions) -> PathData {
let mut out = Vec::new();
for sp in &path.subpaths {
if let Some(s) = simplify_subpath(sp, opts) {
out.push(s);
}
}
PathData::new(out)
}
/// [`simplify_with`] for one subpath; `None` when the refit leaves nothing of it.
fn simplify_subpath(sp: &SubPath, opts: &SimplifyOptions) -> Option<SubPath> {
let mut segs = subpath_segs(sp);
let n = segs.len();
if n == 0 {
return Some(sp.clone());
}
if sp.closed {
// Start the loop at its first corner, so no fit runs across one.
let k = (0..n).find(|&i| turn_deg(&segs[(i + n - 1) % n], &segs[i]) > opts.corner_angle_deg).unwrap_or(0);
segs.rotate_left(k);
}
let result = simplify_run(&segs, opts);
let s = segs_to_subpath(&result, sp.closed)?;
Some(if opts.straight_lines { s } else { no_worse(sp, s) })
}
/// The refit of the consecutive segments `run`, split at its corners sharper than the threshold:
/// it starts and ends where `run` does, leaving the same way.
fn simplify_run(run: &[Seg], opts: &SimplifyOptions) -> Vec<Seg> {
let tol = opts.tolerance.max(1e-6);
let mut cuts: Vec<usize> = (1..run.len()).filter(|&i| turn_deg(&run[i - 1], &run[i]) > opts.corner_angle_deg).collect();
cuts.insert(0, 0);
cuts.push(run.len());
let mut result: Vec<Seg> = Vec::new();
for w in cuts.windows(2) {
let piece = &run[w[0]..w[1]];
if piece.is_empty() {
continue;
}
let mut pts = Vec::new();
for (k, s) in piece.iter().enumerate() {
let len = s.c.arclen(1e-6);
let m = ((len / (tol * 0.5)).ceil() as usize).clamp(4, 256);
sample(&s.c, m, &mut pts, k == 0);
}
if opts.smooth > 0.0 {
pts = smooth_points(&pts, opts.smooth);
}
if opts.straight_lines {
let keep = rdp(&pts, tol);
result.extend(keep.windows(2).map(|p| Seg::line(p[0], p[1])));
continue;
}
let t0 = start_tangent(&piece[0].c);
let t1 = end_tangent(&piece[piece.len() - 1].c);
for c in fit_cubics(&pts, t0, t1, tol) {
let line = is_straight(&c, tol * 0.02);
result.push(if line { Seg::line(c.p0, c.p3) } else { Seg { c, line } });
}
}
result
}
/// `pts` (a run's samples, in order) smoothed along the path: each point becomes the Gaussian-weighted
/// mean of the points around it, `sigma` points of arc length wide, the window narrowing towards the
/// ends so that the first and last points stay where they are. Most points looked at per point is
/// bounded by the samples within three spreads of it.
fn smooth_points(pts: &[Point], sigma: f64) -> Vec<Point> {
if pts.len() < 3 || !(sigma.is_finite() && sigma > 0.0) {
return pts.to_vec();
}
let mut s = Vec::with_capacity(pts.len());
let mut total = 0.0;
for (i, p) in pts.iter().enumerate() {
if let Some(prev) = i.checked_sub(1).and_then(|j| pts.get(j)) {
total += prev.distance(*p);
}
s.push(total);
}
let (mut lo, mut hi) = (0usize, 0usize);
pts.iter()
.zip(&s)
.map(|(&p, &si)| {
let reach = (3.0 * sigma).min(si).min(total - si);
if reach <= 1e-9 {
return p;
}
let spread = reach / 3.0;
while s.get(lo).is_some_and(|&v| v < si - reach) {
lo += 1;
}
while s.get(hi + 1).is_some_and(|&v| v <= si + reach) {
hi += 1;
}
let (mut sum, mut weight) = (Vec2::ZERO, 0.0);
for (q, &sj) in pts.iter().zip(&s).take(hi + 1).skip(lo) {
let w = (-(sj - si) * (sj - si) / (2.0 * spread * spread)).exp();
sum += q.to_vec2() * w;
weight += w;
}
if weight > 0.0 { (sum / weight).to_point() } else { p }
})
.collect()
}
/// What [`simplify_part`] made of a path.
#[derive(Clone, Debug, PartialEq)]
pub struct SimplifiedPart {
pub path: PathData,
/// The segments of the simplified runs, as (subpath, segment) in `path`.
pub segments: BTreeSet<(usize, usize)>,
/// Where each anchor of the original path that is still there went: (subpath, anchor) in the
/// original → in `path`. Anchors inside a simplified run are gone; every other anchor is kept.
pub anchors: BTreeMap<(usize, usize), (usize, usize)>,
}
/// Simplify only the `segments` (subpath, segment) of `path`: each run of consecutive segments
/// among them (a closed subpath's run may cross its start point) is refitted on its own between its
/// two end anchors, which stay where they are with their handles on the side away from the run.
/// The other segments and anchors stay exactly as they are. A subpath whose every segment is in
/// `segments` is simplified whole, as [`simplify_with`] does. A run whose refit would have more
/// segments than it had is left as it is (except with Convert to Straight Lines).
pub fn simplify_part(path: &PathData, segments: &BTreeSet<(usize, usize)>, opts: &SimplifyOptions) -> SimplifiedPart {
let (mut runs, mut anchors) = (BTreeSet::new(), BTreeMap::new());
let mut subpaths = Vec::with_capacity(path.subpaths.len());
for (si, sp) in path.subpaths.iter().enumerate() {
let n = sp.segment_count();
let picked: Vec<bool> = (0..n).map(|i| segments.contains(&(si, i))).collect();
let ni = subpaths.len();
if !picked.contains(&true) {
anchors.extend((0..sp.anchors.len()).map(|ai| ((si, ai), (ni, ai))));
subpaths.push(sp.clone());
} else if !picked.contains(&false) {
if let Some(s) = simplify_subpath(sp, opts) {
runs.extend((0..s.segment_count()).map(|i| (ni, i)));
subpaths.push(s);
}
} else {
let (s, segs, kept) = simplify_runs(sp, &picked, opts);
runs.extend(segs.into_iter().map(|i| (ni, i)));
anchors.extend(kept.into_iter().map(|(old, new)| ((si, old), (ni, new))));
subpaths.push(s);
}
}
SimplifiedPart { path: PathData::new(subpaths), segments: runs, anchors }
}
/// [`simplify_part`] for a subpath with some but not all segments `picked`: → (the subpath, the
/// segments of its refitted runs, old → new index of each anchor kept).
fn simplify_runs(sp: &SubPath, picked: &[bool], opts: &SimplifyOptions) -> (SubPath, Vec<usize>, Vec<(usize, usize)>) {
let m = sp.anchors.len();
let n = picked.len();
// An anchor inside a run (both its segments picked) goes; a closed subpath's walk starts at the
// first anchor that stays, so that no run crosses the start of the walk.
let inside = |a: usize| (sp.closed && a == 0 && picked[n - 1] && picked[0]) || (a > 0 && a < n && picked[a - 1] && picked[a]);
let start = (0..m).find(|&a| !inside(a)).unwrap_or(0);
let mut anchors = vec![sp.anchors[start]];
let mut kept = vec![(start, 0)];
let mut runs = vec![];
let mut k = 0;
while k < n {
let j = (start + k) % n;
if !picked[j] {
let next = (j + 1) % m;
if k + 1 < n || !sp.closed {
kept.push((next, anchors.len()));
anchors.push(sp.anchors[next]);
}
k += 1;
continue;
}
let len = (k..n).take_while(|&i| picked[(start + i) % n]).count();
let run: Vec<Seg> = (k..k + len).map(|i| (start + i) % n).map(|i| Seg { c: sp.segment(i), line: sp.segment_is_line(i) }).collect();
let end = (start + k + len) % m;
let fitted = simplify_run(&run, opts);
let keep_original = fitted.is_empty() || !opts.straight_lines && fitted.len() > run.len();
let first = anchors.len() - 1;
if keep_original {
anchors.extend((k + 1..k + len).map(|i| sp.anchors[(start + i) % m]));
} else {
let a = anchors[first];
anchors[first] = with_handle(a, true, if fitted[0].line { a.p } else { fitted[0].c.p1 });
for w in fitted.windows(2) {
let p = w[1].c.p0;
let h_in = if w[0].line { p } else { w[0].c.p2 };
let h_out = if w[1].line { p } else { w[1].c.p1 };
anchors.push(Anchor::with_handles(p, h_in, h_out));
}
}
// The run's segments, from its first anchor on: a run back to the walk's start ends with
// the closing segment, the last index.
runs.extend(first..first + if keep_original { run.len() } else { fitted.len() });
let end_seg = fitted.last().filter(|_| !keep_original);
if sp.closed && k + len == n {
// The run ends where the walk started.
if let Some(s) = end_seg {
anchors[0] = with_handle(anchors[0], false, if s.line { anchors[0].p } else { s.c.p2 });
}
} else {
let a = sp.anchors[end];
kept.push((end, anchors.len()));
anchors.push(match end_seg {
Some(s) => with_handle(a, false, if s.line { a.p } else { s.c.p2 }),
None => a,
});
}
k += len;
}
(SubPath::new(anchors, sp.closed), runs, kept)
}
/// `a` with its out (`out`) or in handle at `h` and the other as it is: still smooth when it was
/// and its handles still line up, a corner otherwise.
fn with_handle(a: Anchor, out: bool, h: Point) -> Anchor {
let (h_in, h_out) = if out { (a.h_in, h) } else { (h, a.h_out) };
let kind = if a.kind == AnchorKind::Smooth { Anchor::with_handles(a.p, h_in, h_out).kind } else { AnchorKind::Corner };
Anchor { p: a.p, h_in, h_out, kind }
}
/// Ramer–Douglas–Peucker polyline reduction.
fn rdp(pts: &[Point], tol: f64) -> Vec<Point> {
if pts.len() < 3 {
return pts.to_vec();
}
let mut keep = vec![false; pts.len()];
keep[0] = true;
keep[pts.len() - 1] = true;
let mut stack = vec![(0, pts.len() - 1)];
// Distances measured at most: lopsided splits (a shallow zigzag) make it quadratic. Past it,
// the points of the parts left are kept as they are.
let mut budget = pts.len().saturating_mul(64).saturating_add(1 << 20);
while let Some((a, b)) = stack.pop() {
budget = match budget.checked_sub(b - a) {
Some(left) => left,
None => {
keep[a..=b].fill(true);
continue;
}
};
let (pa, pb) = (pts[a], pts[b]);
let chord = pb - pa;
let len = chord.hypot();
let mut best = (0.0, a);
for (i, &p) in pts.iter().enumerate().take(b).skip(a + 1) {
let d = if len < 1e-12 { p.distance(pa) } else { (p - pa).cross(chord).abs() / len };
if d > best.0 {
best = (d, i);
}
}
if best.0 > tol {
keep[best.1] = true;
stack.push((a, best.1));
stack.push((best.1, b));
}
}
pts.iter().zip(keep).filter(|(_, k)| *k).map(|(p, _)| *p).collect()
}
/// Object → Path → Smooth: pull handles towards Catmull-Rom-like tangents. `amount` ∈ [0, 1]
/// (0 = unchanged, 1 = fully smooth). Endpoints of open paths keep their handles.
pub fn smooth(path: &PathData, amount: f64) -> PathData {
let t = amount.clamp(0.0, 1.0);
let mut out = path.clone();
for sp in &mut out.subpaths {
let n = sp.anchors.len();
if n < 3 {
continue;
}
let orig = sp.anchors.clone();
for i in 0..n {
if !sp.closed && (i == 0 || i == n - 1) {
continue;
}
let prev = orig[(i + n - 1) % n].p;
let next = orig[(i + 1) % n].p;
let p = orig[i].p;
let Some(dir) = crate::fit::unit(next - prev) else { continue };
let tin = p - dir * (p.distance(prev) / 3.0);
let tout = p + dir * (p.distance(next) / 3.0);
let a = &orig[i];
let h_in = a.h_in.lerp(tin, t);
let h_out = a.h_out.lerp(tout, t);
sp.anchors[i] = Anchor::with_handles(p, h_in, h_out);
}
}
out
}
/// The Smooth slider's level Auto-Smooth picks, halfway between minimum and maximum smoothing.
/// VectorCraft's own rule: the help page says only that Auto-Smooth smooths the path automatically
/// (https://helpx.adobe.com/illustrator/desktop/draw-shapes-and-paths/modify-paths/refine-path-segments-with-the-smooth-slider.html).
/// [`smooth_level`] already scales with each path's size, so one level suits every path.
pub const SMOOTH_AUTO_LEVEL: f64 = 50.0;
/// The refit Object › Path › Smooth makes of `path` at slider level `level` ([`smooth_level`]): a
/// corner only where the path turns back on itself, the path smoothed along its length by up to 5 %
/// of its longer side (none at level 0) and refitted within 0.1 % (level 0) to 2.5 % (level 100) of
/// it. A level outside 0..=100 counts as the nearer end, and one that is not a number as
/// [`SMOOTH_AUTO_LEVEL`]; a path of no finite size gets no smoothing.
pub fn smooth_options(path: &PathData, level: f64) -> SimplifyOptions {
let level = if level.is_finite() { level.clamp(0.0, 100.0) } else { SMOOTH_AUTO_LEVEL };
let size = path.bounds().map_or(0.0, |b| b.width().max(b.height()));
let size = if size.is_finite() { size } else { 0.0 };
SimplifyOptions {
tolerance: size * (0.001 + 0.024 * level / 100.0),
corner_angle_deg: SMOOTH_CORNER_DEG,
straight_lines: false,
smooth: size * 0.05 * level / 100.0,
}
}
/// Object › Path › Smooth at slider level `level`, from 0 (minimum smoothing: the path stays within
/// 0.1 % of its longer side of where it was) to 100 (maximum). The help page names only the two
/// ends; the rest is VectorCraft's own rule ([`smooth_options`]). Each subpath is smoothed along its
/// length, so that bumps and jags give way to one curve, then refitted with curves as Simplify
/// does, keeping a corner only where the path turns back on itself. A refit never has more anchor
/// points than the subpath had: a shape whose corners it can't round, such as a rectangle, stays as
/// it is. Closed subpaths stay closed, with no kink left where they start unless rounding it would
/// pass the tolerance, and open ones keep their end points.
pub fn smooth_level(path: &PathData, level: f64) -> PathData {
let opts = smooth_options(path, level);
if opts.tolerance <= 0.0 {
return path.clone();
}
let smoothed = |sp: &SubPath| {
let Some(mut fit) = simplify_subpath(sp, &opts).filter(|f| f != sp) else { return sp.clone() };
smooth_seam(&mut fit, sp, opts.tolerance);
fit
};
PathData::new(path.subpaths.iter().map(smoothed).collect())
}
/// [`smooth_level`] keeps a corner only where the path turns by more than this (turns back).
const SMOOTH_CORNER_DEG: f64 = 179.0;
/// A closed subpath's refit leaves its start anchor with the tangents of the original segments on
/// either side of it, a kink when the path had one there: turn it into a smooth anchor with the same
/// handle lengths, unless the path turns back there or the rounded path would stray from `original`
/// by more than `tol` (or than the refit already does).
fn smooth_seam(sp: &mut SubPath, original: &SubPath, tol: f64) {
if !sp.closed {
return;
}
let Some(a) = sp.anchors.first() else { return };
let (Some(i), Some(o)) = (crate::fit::unit(a.p - a.h_in), crate::fit::unit(a.h_out - a.p)) else { return };
if i.dot(o) < SMOOTH_CORNER_DEG.to_radians().cos() {
return;
}
let Some(dir) = crate::fit::unit(i + o) else { return };
let mut rounded = sp.clone();
if let Some(r) = rounded.anchors.first_mut() {
*r = Anchor::with_handles(a.p, a.p - dir * a.h_in.distance(a.p), a.p + dir * a.h_out.distance(a.p));
}
if seam_error(original, sp, &rounded, tol) <= tol.max(seam_error(original, sp, sp, tol)) {
*sp = rounded;
}
}
/// How far the segments on either side of the start anchor of `fit` (a refit of the closed
/// `original` whose other segments match `before`) are from `original`, both ways: the largest
/// distance from those segments to `original`, and from the parts of `original` that `before`'s
/// segments there cover (within `tol`) to `fit`.
fn seam_error(original: &SubPath, before: &SubPath, fit: &SubPath, tol: f64) -> f64 {
use kurbo::ParamCurveNearest;
let n = fit.segment_count();
if n == 0 || before.segment_count() != n || original.segment_count() == 0 {
return f64::INFINITY;
}
let is_seam = |j: usize| j == 0 || j + 1 == n;
let dist = |q: Point, sp: &SubPath, seam: bool| {
(0..sp.segment_count())
.filter(|&j| is_seam(j) == seam)
.map(|j| sp.segment(j).nearest(q, 1e-9).distance_sq)
.fold(f64::INFINITY, f64::min)
.sqrt()
};
let samples = |sp: &SubPath, seam_only: bool| {
let mut pts = Vec::new();
for j in (0..sp.segment_count()).filter(|&j| !seam_only || is_seam(j)) {
let c = sp.segment(j);
let m = ((c.arclen(1e-6) / (tol.max(1e-6) * 0.5)).ceil() as usize).clamp(4, 256);
sample(&c, m, &mut pts, true);
}
pts
};
let all = |q: Point| dist(q, original, true).min(dist(q, original, false));
let forward = samples(fit, true).into_iter().map(all).fold(0.0, f64::max);
let back = samples(original, false)
.into_iter()
.filter(|&q| dist(q, before, true) <= tol)
.map(|q| {
let d = dist(q, fit, true);
if d > tol { d.min(dist(q, fit, false)) } else { d }
})
.fold(0.0, f64::max);
forward.max(back)
}
/// Remove anchors that can be deleted without changing the shape by more than `tolerance`
/// (collinear corner points, duplicate points, and curve joints that one cubic can replace).
pub fn remove_redundant_points(path: &PathData, tolerance: f64) -> PathData {
let tol = tolerance.max(1e-9);
let mut out = Vec::new();
for sp in &path.subpaths {
let mut segs = subpath_segs(sp);
if segs.is_empty() {
out.push(sp.clone());
continue;
}
// Drop zero-length segments.
segs.retain(|s| !(s.c.p0.distance(s.c.p3) < 1e-9 && s.c.p1.distance(s.c.p0) < 1e-9 && s.c.p2.distance(s.c.p0) < 1e-9));
let min_segs = if sp.closed { 2 } else { 1 };
// Joints are merged along the path in one pass (a merged segment is tried with the one
// before it, then the next); the search below then only finds what a closed path's wrap
// leaves. (Merging at the first joint of a dense line one at a time shifts the rest each time.)
let total = segs.len();
let mut merged = 0;
let mut done: Vec<Seg> = Vec::with_capacity(total);
for s in segs.drain(..) {
done.push(s);
while done.len() >= 2 && total - merged > min_segs {
let n = done.len();
let Some(m) = merge_pair(&done[n - 2], &done[n - 1], tol) else { break };
done.truncate(n - 1);
done[n - 2] = m;
merged += 1;
}
}
segs = done;
let mut changed = true;
while changed && segs.len() > min_segs {
changed = false;
let n = segs.len();
let joints = if sp.closed { n } else { n - 1 };
for j in 0..joints {
let (i0, i1) = if sp.closed { ((j + n - 1) % n, j) } else { (j, j + 1) };
if let Some(m) = merge_pair(&segs[i0], &segs[i1], tol) {
segs[i0] = m;
segs.remove(i1);
if sp.closed && i1 == 0 {
// The merged segment now starts the loop.
if let Some(last) = segs.pop() {
segs.insert(0, last);
}
}
changed = true;
break;
}
}
}
if let Some(s) = segs_to_subpath(&segs, sp.closed) {
out.push(s);
}
}
PathData::new(out)
}
fn merge_pair(a: &Seg, b: &Seg, tol: f64) -> Option<Seg> {
if a.line && b.line {
let chord = b.c.p3 - a.c.p0;
let len = chord.hypot();
if len < 1e-12 {
return None;
}
let mid = a.c.p3 - a.c.p0;
let along = mid.dot(chord) / len;
return ((mid.cross(chord) / len).abs() <= tol && along >= 0.0 && along <= len).then(|| Seg::line(a.c.p0, b.c.p3));
}
// Only merge across (near-)smooth joints.
if end_tangent(&a.c).dot(start_tangent(&b.c)) < 0.99 {
return None;
}
let mut pts = Vec::new();
sample(&a.c, 16, &mut pts, true);
sample(&b.c, 16, &mut pts, false);
let (c, err, _) = fit_single(&pts, start_tangent(&a.c), end_tangent(&b.c));
(err <= tol).then_some(Seg { c, line: false })
}
/// Remove anchor `index` without opening the path (the Delete Anchor Point tool and Object → Path
/// → Remove Anchor Points). Its neighbours keep their handle directions and their facing handles
/// are refitted so one cubic follows the two segments that met there; two straight segments
/// become one. Removing an end of an open path drops its segment. Returns false, leaving `sp`
/// alone, when `index` is out of range.
pub fn remove_anchor(sp: &mut SubPath, index: usize) -> bool {
let n = sp.anchors.len();
if index >= n {
return false;
}
if (sp.closed || (index > 0 && index + 1 < n)) && n >= 3 {
let (pi, ni) = ((index + n - 1) % n, (index + 1) % n);
if !(sp.segment_is_line(pi) && sp.segment_is_line(index)) {
let (left, right) = (sp.segment(pi), sp.segment(index));
const N: usize = 16;
let mut pts = Vec::with_capacity(2 * N + 1);
sample(&left, N, &mut pts, true);
sample(&right, N, &mut pts, false);
let (t0, t1) = (start_tangent(&left), end_tangent(&right));
// The new curve passes the removed point at some parameter k: the left samples sit
// at k·i/N, the right ones at k + (1 − k)·i/N. Search k for the closest fit.
let fit = |k: f64| {
let u = (0..=N).map(|i| k * i as f64 / N as f64).chain((1..=N).map(|i| k + (1.0 - k) * i as f64 / N as f64)).collect();
fit_single_from(&pts, u, t0, t1)
};
let (c, _, _) = golden_min(fit, 0.0, 1.0);
if c.p1.is_finite() && c.p2.is_finite() {
sp.anchors[pi].h_out = c.p1;
sp.anchors[ni].h_in = c.p2;
}
}
}
sp.anchors.remove(index);
if !sp.closed {
// A new end has nothing beyond it.
if let Some(a) = sp.anchors.first_mut() {
a.h_in = a.p;
}
if let Some(a) = sp.anchors.last_mut() {
a.h_out = a.p;
}
}
if sp.anchors.len() < 3 {
sp.closed = sp.closed && sp.anchors.len() == 2 && sp.anchors.iter().any(|a| a.has_in() || a.has_out());
}
true
}
/// The fit `f` (curve, error, worst point) with the least error for an argument in `[a, b]`, by a
/// golden-section search (a bounded number of steps).
fn golden_min(f: impl Fn(f64) -> (CubicBez, f64, usize), mut a: f64, mut b: f64) -> (CubicBez, f64, usize) {
const R: f64 = 0.618_033_988_749_895;
let (mut x1, mut x2) = (b - R * (b - a), a + R * (b - a));
let (mut f1, mut f2) = (f(x1), f(x2));
for _ in 0..40 {
// A NaN error never wins.
if f1.1 < f2.1 || f2.1.is_nan() {
(b, x2, f2) = (x2, x1, f1);
x1 = b - R * (b - a);
f1 = f(x1);
} else {
(a, x1, f1) = (x1, x2, f2);
x2 = a + R * (b - a);
f2 = f(x2);
}
}
if f1.1 <= f2.1 { f1 } else { f2 }
}
/// Object → Path → Add Anchor Points: one new anchor at the middle (t = 0.5) of every segment.
pub fn add_anchor_points(path: &PathData) -> PathData {
let mut out = path.clone();
for sp in &mut out.subpaths {
for seg in (0..sp.segment_count()).rev() {
sp.insert_anchor(seg, 0.5);
}
}
out
}
/// Axis for [`average`].
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum AverageAxis {
/// Align on a common horizontal line (same y).
Horizontal,
/// Align on a common vertical line (same x).
Vertical,
/// Collapse to the common centroid.
Both,
}
/// Object → Path → Average: move the selected anchors `(subpath, anchor)` (with their handles)
/// to their average position along `axis`.
pub fn average(path: &PathData, selection: &[(usize, usize)], axis: AverageAxis) -> PathData {
let mut out = path.clone();
let pts: Vec<Point> = selection.iter().filter_map(|&(s, a)| path.subpaths.get(s).and_then(|sp| sp.anchors.get(a)).map(|a| a.p)).collect();
if pts.is_empty() {
return out;
}
let c = pts.iter().fold(Vec2::ZERO, |acc, p| acc + p.to_vec2()) / pts.len() as f64;
for &(s, a) in selection {
if let Some(an) = out.anchor_mut(s, a) {
let d = match axis {
AverageAxis::Horizontal => Vec2::new(0.0, c.y - an.p.y),
AverageAxis::Vertical => Vec2::new(c.x - an.p.x, 0.0),
AverageAxis::Both => c - an.p.to_vec2(),
};
an.translate(d);
}
}
out
}
/// Object → Path → Join. Open subpaths of all inputs are joined nearest-endpoint-first into one
/// open path (endpoints closer than `tolerance` are merged into a single anchor, otherwise a
/// straight segment connects them). A single open subpath is closed instead. Closed subpaths
/// pass through unchanged.
pub fn join(paths: &[PathData], tolerance: f64) -> PathData {
let mut closed: Vec<SubPath> = Vec::new();
let mut open: Vec<SubPath> = Vec::new();
for p in paths {
for sp in &p.subpaths {
if sp.closed || sp.anchors.len() < 2 {
if !sp.anchors.is_empty() {
closed.push(sp.clone());
}
} else {
open.push(sp.clone());
}
}
}
if open.len() == 1
&& let Some(mut sp) = open.pop()
{
let ends_meet = sp.anchors.len() > 2 && end_point(&sp, false).zip(end_point(&sp, true)).is_some_and(|(a, b)| a.distance(b) <= tolerance);
if ends_meet
&& let Some(last) = sp.anchors.pop()
&& let Some(f) = sp.anchors.first_mut()
{
*f = Anchor::with_handles(f.p, last.h_in, f.h_out);
} else {
if let Some(f) = sp.anchors.first_mut() {
f.h_in = f.p;
}
if let Some(l) = sp.anchors.last_mut() {
l.h_out = l.p;
}
}
sp.closed = true;
closed.push(sp);
return PathData::new(closed);
}
while open.len() > 1 {
// Find the closest pair of endpoints on different subpaths. Past this many subpaths every
// pair at every merge is too much (cubic): the first one is joined to its nearest.
const SEARCH_ALL: usize = 200;
let first_only = open.len() > SEARCH_ALL;
let mut best = (f64::INFINITY, 0, 0, false, false);
for i in 0..if first_only { 1 } else { open.len() } {
for j in (i + 1)..open.len() {
for ei in [false, true] {
for ej in [false, true] {
let (Some(pi), Some(pj)) = (end_point(&open[i], ei), end_point(&open[j], ej)) else { continue };
let d = pi.distance(pj);
if d < best.0 {
best = (d, i, j, ei, ej);
}
}
}
}
}
let (d, i, j, ei, ej) = best;
let mut b = open.remove(j);
let a = &mut open[i];
if !ei {
a.reverse();
}
if ej {
b.reverse();
}
if d <= tolerance && !b.anchors.is_empty() {
let first = b.anchors.remove(0);
if let Some(l) = a.anchors.last_mut() {
*l = Anchor::with_handles(l.p, l.h_in, first.h_out);
}
} else {
if let Some(l) = a.anchors.last_mut() {
l.h_out = l.p;
}
if let Some(f) = b.anchors.first_mut() {
f.h_in = f.p;
}
}
a.anchors.extend(b.anchors);
}
closed.extend(open);
PathData::new(closed)
}
/// Object → Path → Split Into Grid: `rows × cols` rectangles filling `rect` with a gutter between
/// the rows and one between the columns (row-major, top-left first). No cells when they would have
/// no size.
pub fn split_into_grid(rect: Rect, rows: usize, cols: usize, (row_gutter, col_gutter): (f64, f64)) -> Vec<PathData> {
if rows == 0 || cols == 0 {
return Vec::new();
}
let w = (rect.width() - col_gutter * (cols as f64 - 1.0)) / cols as f64;
let h = (rect.height() - row_gutter * (rows as f64 - 1.0)) / rows as f64;
// Written so that a size that is not a number gives no cells either.
if !(w > 0.0 && h > 0.0 && w.is_finite() && h.is_finite()) {
return Vec::new();
}
let mut out = Vec::with_capacity(rows * cols);
for r in 0..rows {
for c in 0..cols {
let x = rect.x0 + c as f64 * (w + col_gutter);
let y = rect.y0 + r as f64 * (h + row_gutter);
out.push(PathData::single(SubPath::polyline(
&[Point::new(x, y), Point::new(x + w, y), Point::new(x + w, y + h), Point::new(x, y + h)],
true,
)));
}
}
out
}
/// The first (`last == false`) or last anchor point of a subpath.
fn end_point(sp: &SubPath, last: bool) -> Option<Point> {
if last { sp.anchors.last() } else { sp.anchors.first() }.map(|a| a.p)
}