VectorCraft: An open-source, vector art tool written by scratch in pure Rust
//! Curve-preserving boolean operations built on `linesweeper`'s robust sweep-line topology.
//!
//! Inputs are converted to closed [`BezPath`]s (open subpaths are implicitly closed, as a filled
//! open path is painted in Illustrator). The sweep splits curves at intersections and y-extrema;
//! [`tidy_segments`] then re-joins pieces that came from the same smooth curve by refitting, so
//! results have roughly as few anchors as the inputs.
use std::collections::BTreeSet;
use kurbo::{BezPath, CubicBez, PathSeg, Point, Shape as _};
use linesweeper::topology::{ContourIdx, Contours, Topology, WindingNumber};
use vectorcraft_geom::{Anchor, FillRule, PathData, SubPath};
use crate::PathOpsError;
use crate::fit::{end_tangent, fit_single, is_straight, sample, start_tangent};
#[cfg(test)]
thread_local! {
/// The contour passes made over an arrangement on this thread, each of which walks all of it.
pub(crate) static CONTOUR_PASSES: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
}
/// Default curve-refit tolerance (document points) used to merge split curve pieces back together.
/// Similar in spirit to Illustrator's Pathfinder "Precision" option (0.028 pt).
pub const DEFAULT_PRECISION: f64 = 0.01;
/// Binary boolean operation.
#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
pub enum BoolOp {
/// A ∪ B
Union,
/// A ∩ B
Intersect,
/// A − B
Difference,
/// A ⊕ B (symmetric difference)
Xor,
}
impl BoolOp {
/// Evaluate the operation on "inside A" / "inside B" flags.
pub fn apply(self, a: bool, b: bool) -> bool {
match self {
BoolOp::Union => a || b,
BoolOp::Intersect => a && b,
BoolOp::Difference => a && !b,
BoolOp::Xor => a != b,
}
}
}
pub(crate) fn inside(rule: FillRule, w: i32) -> bool {
match rule {
FillRule::NonZero => w != 0,
FillRule::EvenOdd => w % 2 != 0,
}
}
/// Winding numbers for an arbitrary number of input sets (tag = input index): the non-zero ones,
/// as (tag, winding) sorted by tag. A face is covered by a few of the inputs, so this stays short
/// where a vector of every input's winding would make each Pathfinder test cost one step per input.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub(crate) struct Multi(Vec<(usize, i32)>);
impl Multi {
fn get(&self, i: usize) -> i32 {
self.0.binary_search_by_key(&i, |e| e.0).ok().and_then(|k| self.0.get(k)).map_or(0, |e| e.1)
}
/// The non-zero windings, by input.
pub(crate) fn iter(&self) -> impl DoubleEndedIterator<Item = (usize, i32)> + '_ {
self.0.iter().copied()
}
}
impl std::ops::Add for Multi {
type Output = Multi;
fn add(mut self, rhs: Self) -> Multi {
self += rhs;
self
}
}
impl std::ops::AddAssign for Multi {
fn add_assign(&mut self, rhs: Self) {
// In place, input by input (the sweep mostly adds one input's ±1 to a short list): add to
// the input's winding, or insert it in tag order, and drop it if it reaches zero.
for (t, k) in rhs.0 {
match self.0.binary_search_by_key(&t, |e| e.0) {
Ok(i) => {
if let Some(e) = self.0.get_mut(i) {
e.1 += k;
if e.1 == 0 {
self.0.remove(i);
}
}
}
Err(i) if k != 0 => self.0.insert(i, (t, k)),
Err(_) => {}
}
}
}
}
impl WindingNumber for Multi {
type Tag = usize;
fn single(tag: usize, positive: bool) -> Self {
Multi(vec![(tag, if positive { 1 } else { -1 })])
}
fn of_tag(&self, tag: usize) -> Self {
let w = self.get(tag);
Multi(if w == 0 { vec![] } else { vec![(tag, w)] })
}
}
/// Convert a (filled) path to a closed BezPath: every subpath with ≥ 2 anchors is closed.
pub(crate) fn fill_bezpath(p: &PathData) -> BezPath {
let mut bp = BezPath::new();
for sp in &p.subpaths {
if sp.anchors.len() < 2 {
continue;
}
if sp.closed {
sp.to_bezpath_into(&mut bp);
} else {
let mut c = sp.clone();
c.closed = true;
c.to_bezpath_into(&mut bp);
}
}
bp
}
/// Sweep tolerance for a set of paths (same scaling rule as linesweeper's own `binary_op`).
pub(crate) fn eps_for<'a>(paths: impl IntoIterator<Item = &'a BezPath>) -> Result<f64, PathOpsError> {
let mut m: f64 = 0.0;
for p in paths {
for el in p.elements() {
for pt in el_points(el) {
if !pt.x.is_finite() || !pt.y.is_finite() {
return Err(PathOpsError::NonFinite);
}
m = m.max(pt.x.abs()).max(pt.y.abs());
}
}
}
Ok((m * f64::EPSILON * 64.0).max(1e-6))
}
fn el_points(el: &kurbo::PathEl) -> impl Iterator<Item = Point> {
use kurbo::PathEl::*;
let v: [Option<Point>; 3] = match *el {
MoveTo(p) | LineTo(p) => [Some(p), None, None],
QuadTo(a, b) => [Some(a), Some(b), None],
CurveTo(a, b, c) => [Some(a), Some(b), Some(c)],
ClosePath => [None, None, None],
};
v.into_iter().flatten()
}
/// Make edges that rise by less than the sweep tolerance `eps` exactly horizontal.
///
/// The sweep orders a curve against another segment over a y-span shorter than `eps` by bounding
/// boxes alone, so an almost-horizontal edge (typically a boolean result's edge whose end, an
/// intersection point, is a rounding error off the input's horizontal) can be mis-ordered against
/// a curve it passes and the output loses a corner; exact horizontals are handled exactly. So
/// on-curve y coordinates within `eps` of each other snap to one value (the lowest of each
/// cluster, keeping distinct values at least `eps` apart), handles move with their anchors, and a
/// handle within `eps` of its anchor's height is levelled with it (no y-extremum is left in a
/// sub-`eps` sliver of a curve). Anchors move by less than `eps` and handles by less than `2·eps`,
/// the order of the sweep's own tolerance.
pub(crate) fn snap_horizontals(paths: &mut [&mut BezPath], eps: f64) {
use kurbo::PathEl::*;
let mut ys: Vec<f64> = paths.iter().flat_map(|p| p.elements().iter().filter_map(kurbo::PathEl::end_point)).map(|p| p.y).collect();
ys.sort_by(f64::total_cmp);
ys.dedup();
let mut start = f64::NEG_INFINITY;
let levels: Vec<f64> = ys
.iter()
.map(|&y| {
if y - start >= eps {
start = y;
}
start
})
.collect();
let snap = |p: &mut Point| {
let y = levels[ys.partition_point(|&v| v < p.y)];
let moved = y - p.y;
p.y = y;
moved
};
// Shift a handle with its anchor, then level it with the anchor when within `eps`.
let follow = |h: &mut Point, anchor: Point, moved: f64| {
h.y += moved;
if (h.y - anchor.y).abs() < eps {
h.y = anchor.y;
}
};
for p in paths.iter_mut() {
// The current point (snapped) and how far snapping moved it; the subpath's start.
let (mut cur, mut moved, mut first) = (Point::ZERO, 0.0, Point::ZERO);
for el in p.elements_mut() {
match el {
MoveTo(q) => {
moved = snap(q);
(cur, first) = (*q, *q);
}
LineTo(q) => {
moved = snap(q);
cur = *q;
}
QuadTo(c, q) => {
let m = snap(q);
follow(c, cur, moved);
follow(c, *q, 0.0);
(cur, moved) = (*q, m);
}
CurveTo(c1, c2, q) => {
let m = snap(q);
follow(c1, cur, moved);
follow(c2, *q, m);
(cur, moved) = (*q, m);
}
ClosePath => {
// A later segment without a MoveTo starts from the subpath's (snapped) start.
(cur, moved) = (first, 0.0);
}
}
}
}
}
/// An arrangement (planar subdivision) of N filled paths.
pub(crate) struct Arrangement {
pub(crate) top: Topology<Multi>,
pub(crate) rules: Vec<FillRule>,
/// Output cleanup that keeps the inputs' anchors.
pub(crate) tidy: Tidy,
}
/// Output cleanup settings: refit `precision`, and anchor positions that must survive (the
/// inputs' own anchors — only joints the sweep introduced are merged away).
#[derive(Clone, Debug, Default)]
pub(crate) struct Tidy {
pub(crate) precision: f64,
keep: Vec<Point>,
/// Input curves (with inflated bounds) used to rebuild split pieces exactly.
curves: Vec<(kurbo::Rect, CubicBez)>,
/// `curves` indices by the left edge of their bounds, and the widest bounds: the curves whose
/// bounds can hold a point, without testing them all.
by_x: Vec<usize>,
max_width: f64,
}
impl Tidy {
/// Merge any smooth joint.
pub(crate) fn free(precision: f64) -> Self {
Self { precision, ..Default::default() }
}
/// Keep every on-curve point of `paths`.
pub(crate) fn keeping<'a>(precision: f64, paths: impl IntoIterator<Item = &'a BezPath>) -> Self {
let mut keep = Vec::new();
let mut curves = Vec::new();
for p in paths {
for s in p.segments() {
let seg = to_seg(s);
keep.push(seg.c.p0);
if !seg.line {
let r = seg.c.bounding_box().inflate(1e-6, 1e-6);
curves.push((r, seg.c));
}
}
}
keep.sort_by(|a, b| a.x.total_cmp(&b.x));
let mut by_x: Vec<usize> = (0..curves.len()).collect();
by_x.sort_by(|&i, &j| curves[i].0.x0.total_cmp(&curves[j].0.x0));
let max_width = curves.iter().map(|(r, _)| r.width()).fold(0.0, f64::max);
Self { precision, keep, curves, by_x, max_width }
}
fn is_kept(&self, p: Point) -> bool {
let tol = 1e-6 * (1.0 + p.x.abs().max(p.y.abs()));
let lo = self.keep.partition_point(|q| q.x < p.x - tol);
self.keep[lo..].iter().take_while(|q| q.x <= p.x + tol).any(|q| (q.y - p.y).abs() <= tol)
}
}
impl Arrangement {
pub(crate) fn new(mut paths: Vec<(BezPath, FillRule)>) -> Result<Self, PathOpsError> {
let eps = eps_for(paths.iter().map(|p| &p.0))?;
snap_horizontals(&mut paths.iter_mut().map(|p| &mut p.0).collect::<Vec<_>>(), eps);
// Counted on the snapped geometry, which is what the sweep sees: snapping can bring boxes into contact.
if !crate::budget::sweep_fits(paths.iter().map(|p| &p.0)) {
return Err(PathOpsError::TooComplex);
}
// The sweep can panic on rare near-degenerate input; that must never take the app down,
// so it becomes an error (callers fall back to leaving the art unchanged).
let sweep = std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| {
Topology::<Multi>::from_paths(paths.iter().enumerate().map(|(i, (p, _))| (p, i)), eps)
}));
let top = sweep.map_err(|_| PathOpsError::Degenerate)?.map_err(|_| PathOpsError::OpenPath)?;
let tidy = Tidy::keeping(DEFAULT_PRECISION, paths.iter().map(|p| &p.0));
Ok(Self { top, rules: paths.iter().map(|p| p.1).collect(), tidy })
}
pub(crate) fn mask(&self, w: &Multi) -> Vec<bool> {
// A zero winding is outside under both rules, so only the non-zero ones can set a flag.
let mut m = vec![false; self.rules.len()];
for (i, k) in w.iter() {
if let (Some(&r), Some(b)) = (self.rules.get(i), m.get_mut(i)) {
*b = inside(r, k);
}
}
m
}
/// The inputs that cover a face of winding `w` (`mask(w)`'s true indices), back to front.
pub(crate) fn covered<'a>(&'a self, w: &'a Multi) -> impl DoubleEndedIterator<Item = usize> + 'a {
w.iter().filter(|&(i, k)| self.rules.get(i).is_some_and(|&r| inside(r, k))).map(|(i, _)| i)
}
/// [`Arrangement::contours`] with the test on the windings themselves (see [`Self::covered`]).
pub(crate) fn contours_where(&self, pred: impl Fn(&Multi) -> bool) -> Contours {
#[cfg(test)]
CONTOUR_PASSES.with(|n| n.set(n.get() + 1));
self.top.contours(pred)
}
pub(crate) fn contours(&self, pred: impl Fn(&[bool]) -> bool) -> Contours {
self.contours_where(|w| pred(&self.mask(w)))
}
/// All distinct non-empty coverage masks that occur next to some edge, sorted.
pub(crate) fn distinct_masks(&self) -> Vec<Vec<bool>> {
let mut set = BTreeSet::new();
for s in self.top.segment_indices() {
let h = s.first_half();
for w in [self.top.winding_clockwise(h), self.top.winding_counter_clockwise(h)] {
let m = self.mask(w);
if m.iter().any(|&b| b) {
set.insert(m);
}
}
}
set.into_iter().collect()
}
/// Vertices where three or more edges meet (true intersections / touch points).
pub(crate) fn junctions(&self) -> Vec<Point> {
let mut count: std::collections::HashMap<(u64, u64), (usize, Point)> = std::collections::HashMap::new();
for s in self.top.segment_indices() {
for h in [s.first_half(), s.second_half()] {
let p = self.top.point(h).to_kurbo();
count.entry((p.x.to_bits(), p.y.to_bits())).or_insert((0, p)).0 += 1;
}
}
let mut v: Vec<Point> = count.into_values().filter(|(c, _)| *c >= 3).map(|(_, p)| p).collect();
v.sort_by(|a, b| a.x.total_cmp(&b.x).then(a.y.total_cmp(&b.y)));
v
}
}
/// Convert selected contours into a tidy compound path.
pub(crate) fn contours_to_path(c: &Contours, idx: impl IntoIterator<Item = ContourIdx>, tidy: &Tidy) -> PathData {
let mut subpaths = Vec::new();
for i in idx {
let path = tidy.repair(&c[i].path);
if is_sliver(&path, tidy.precision) {
continue;
}
if let Some(sp) = tidy_bezpath(&path, tidy) {
subpaths.push(sp);
}
}
PathData::new(subpaths)
}
pub(crate) fn all_contours_to_path(c: &Contours, tidy: &Tidy) -> PathData {
contours_to_path(c, (0..c.contours().count()).map(ContourIdx), tidy)
}
/// Contours whose mean width (2·area / perimeter) is below `precision` are numerical debris
/// (e.g. the lens left between two coincident curves) and are dropped, like Illustrator's
/// Pathfinder precision setting does.
pub(crate) fn is_sliver(bp: &BezPath, precision: f64) -> bool {
let a = bp.area().abs();
let per = bp.perimeter(1e-6);
per <= 0.0 || 2.0 * a / per < precision
}
/// One segment of a path: a cubic plus whether it is a straight line.
#[derive(Clone, Copy, Debug)]
pub(crate) struct Seg {
pub(crate) c: CubicBez,
pub(crate) line: bool,
}
impl Seg {
pub(crate) fn line(a: Point, b: Point) -> Self {
Self { c: CubicBez::new(a, a, b, b), line: true }
}
}
pub(crate) fn to_seg(s: PathSeg) -> Seg {
match s {
PathSeg::Line(l) => Seg::line(l.p0, l.p1),
PathSeg::Quad(q) => {
let c = q.raise();
Seg { c, line: is_straight(&c, 1e-9) }
}
PathSeg::Cubic(c) => Seg { c, line: is_straight(&c, 1e-9 * (1.0 + c.p0.distance(c.p3))) },
}
}
fn tidy_bezpath(bp: &BezPath, tidy: &Tidy) -> Option<SubPath> {
let segs: Vec<Seg> = bp.segments().map(to_seg).collect();
let segs = tidy_segments(segs, true, tidy);
segs_to_subpath(&segs, true)
}
/// Build a subpath from a chain of segments.
pub(crate) fn segs_to_subpath(segs: &[Seg], closed: bool) -> Option<SubPath> {
if segs.is_empty() {
return None;
}
let n = segs.len();
let mut anchors = Vec::with_capacity(n + 1);
for i in 0..n {
let s = segs[i];
let p = s.c.p0;
let h_out = if s.line { p } else { s.c.p1 };
let h_in = if i == 0 && !closed {
p
} else {
let prev = segs[(i + n - 1) % n];
if prev.line { p } else { prev.c.p2 }
};
anchors.push(Anchor::with_handles(p, h_in, h_out));
}
if !closed {
let last = segs[n - 1];
let p = last.c.p3;
let h_in = if last.line { p } else { last.c.p2 };
anchors.push(Anchor::with_handles(p, h_in, p));
}
if closed && anchors.len() < 2 {
return None;
}
Some(SubPath::new(anchors, closed))
}
/// Merge segments that were split from one curve (or collinear lines) back together, dropping
/// degenerate pieces. `closed` segments form a loop.
pub(crate) fn tidy_segments(segs: Vec<Seg>, closed: bool, tidy: &Tidy) -> Vec<Seg> {
let scale = segs.iter().map(|s| s.c.p0.distance(s.c.p3)).fold(0.0, f64::max);
let tiny = (scale * 1e-9).max(1e-9);
let mut segs: Vec<Seg> = segs
.into_iter()
.filter(|s| {
let r = kurbo::Rect::from_points(s.c.p0, s.c.p3).union_pt(s.c.p1).union_pt(s.c.p2);
r.width() + r.height() > tiny
})
.collect();
let n = segs.len();
if n < 2 {
return segs;
}
// Joint i sits at the start of segment i.
let mergeable = |a: &Seg, b: &Seg| -> bool {
if a.line != b.line || tidy.is_kept(b.c.p0) {
return false;
}
let ta = end_tangent(&a.c);
let tb = start_tangent(&b.c);
ta.dot(tb) > 0.9998 && ta.cross(tb).abs() < 0.02
};
if closed {
// Rotate so we start at a real corner (if there is one).
if let Some(k) = (0..n).find(|&i| !mergeable(&segs[(i + n - 1) % n], &segs[i])) {
segs.rotate_left(k);
}
}
let mut out: Vec<Seg> = Vec::with_capacity(n);
let mut i = 0;
while i < n {
let mut cur = segs[i];
let mut j = i + 1;
while j < n && mergeable(&segs[j - 1], &segs[j]) {
match try_merge(&segs[i..=j], tidy) {
Some(m) => {
cur = m;
j += 1;
}
None => break,
}
}
out.push(cur);
i = j;
}
out
}
fn try_merge(run: &[Seg], tidy: &Tidy) -> Option<Seg> {
let precision = tidy.precision;
let first = run[0].c;
let last = run[run.len() - 1].c;
if run[0].line {
let chord = last.p3 - first.p0;
let len = chord.hypot();
if len < 1e-12 {
return None;
}
let ok = run.iter().all(|s| ((s.c.p3 - first.p0).cross(chord) / len).abs() <= precision * 0.5);
return ok.then(|| Seg::line(first.p0, last.p3));
}
if let Some(c) = exact_merge(run, tidy) {
return Some(Seg { c, line: false });
}
let mut pts = Vec::with_capacity(run.len() * 12 + 1);
for (k, s) in run.iter().enumerate() {
sample(&s.c, 12, &mut pts, k == 0);
}
let (c, err, _) = fit_single(&pts, start_tangent(&first), end_tangent(&last));
if err > precision {
return None;
}
Some(Seg { c, line: false })
}
/// If every piece of `run` lies on one input cubic, return the exact sub-curve spanning the run.
fn exact_merge(run: &[Seg], tidy: &Tidy) -> Option<CubicBez> {
use kurbo::{ParamCurve, ParamCurveNearest};
let a = run[0].c.p0;
let b = run[run.len() - 1].c.p3;
let scale = 1.0 + a.x.abs().max(a.y.abs()).max(b.x.abs()).max(b.y.abs());
let tol = 1e-6 * scale;
for (r, c) in &tidy.curves {
if !r.contains(a) || !r.contains(b) {
continue;
}
let na = c.nearest(a, 1e-12);
let nb = c.nearest(b, 1e-12);
if na.distance_sq.sqrt() > tol || nb.distance_sq.sqrt() > tol {
continue;
}
let on_curve = run.iter().all(|s| c.nearest(s.c.eval(0.5), 1e-12).distance_sq.sqrt() <= tol * 10.0);
if !on_curve || (na.t - nb.t).abs() < 1e-12 {
continue;
}
let sub = if na.t < nb.t {
c.subsegment(na.t..nb.t)
} else {
let r = c.subsegment(nb.t..na.t);
CubicBez::new(r.p3, r.p2, r.p1, r.p0)
};
return Some(CubicBez::new(a, sub.p1, sub.p2, b));
}
None
}
impl Tidy {
/// The input curves whose bounds hold both `a` and `b`.
fn curves_around(&self, a: Point, b: Point) -> impl Iterator<Item = &CubicBez> {
let x = a.x.min(b.x);
let hi = self.by_x.partition_point(|&i| self.curves[i].0.x0 <= x);
let lo = self.by_x[..hi].partition_point(|&i| self.curves[i].0.x0 < x - self.max_width);
self.by_x[lo..hi].iter().map(|&i| &self.curves[i]).filter(move |(r, _)| r.contains(a) && r.contains(b)).map(|(_, c)| c)
}
/// `bp` with each curve piece that strays from the one input curve through both its ends
/// rebuilt as that curve's exact sub-curve. linesweeper 0.5 can emit a piece that doesn't
/// follow its curve; out and back between two points of one curve, such pieces are a lens
/// instead of nothing (issue #1028). A piece on a curve, or whose ends two different input
/// curves pass through (a real lens between them), is left as it is.
pub(crate) fn repair(&self, bp: &BezPath) -> BezPath {
use kurbo::{ParamCurve, ParamCurveNearest, PathEl};
if self.curves.is_empty() {
return bp.clone();
}
let mut out = BezPath::new();
let mut cur = Point::ZERO;
let mut start = Point::ZERO;
for el in bp.iter() {
let piece = match el {
PathEl::QuadTo(c, p) => Some(kurbo::QuadBez::new(cur, c, p).raise()),
PathEl::CurveTo(c1, c2, p) => Some(CubicBez::new(cur, c1, c2, p)),
_ => None,
};
match (el, piece) {
(_, Some(raw)) => {
let (a, b) = (raw.p0, raw.p3);
let scale = 1.0 + a.x.abs().max(a.y.abs()).max(b.x.abs()).max(b.y.abs());
let tol = 1e-6 * scale;
let mut subs: Vec<CubicBez> = vec![];
let mut follows = false;
for c in self.curves_around(a, b) {
let (na, nb) = (c.nearest(a, 1e-12), c.nearest(b, 1e-12));
if na.distance_sq.sqrt() > tol || nb.distance_sq.sqrt() > tol || (na.t - nb.t).abs() < 1e-12 {
continue;
}
if [0.25, 0.5, 0.75].iter().all(|&t| c.nearest(raw.eval(t), 1e-12).distance_sq.sqrt() <= tol * 10.0) {
follows = true;
break;
}
let sub = if na.t < nb.t {
c.subsegment(na.t..nb.t)
} else {
let r = c.subsegment(nb.t..na.t);
CubicBez::new(r.p3, r.p2, r.p1, r.p0)
};
subs.push(CubicBez::new(a, sub.p1, sub.p2, b));
}
let same = |p: &CubicBez, q: &CubicBez| p.p1.distance(q.p1) <= tol * 10.0 && p.p2.distance(q.p2) <= tol * 10.0;
match subs.split_first() {
Some((sub, rest)) if !follows && rest.iter().all(|q| same(sub, q)) => out.curve_to(sub.p1, sub.p2, b),
_ => out.push(el),
}
cur = b;
}
(PathEl::MoveTo(p), None) => {
out.push(el);
(cur, start) = (p, p);
}
(PathEl::LineTo(p), None) => {
out.push(el);
cur = p;
}
(PathEl::ClosePath, None) => {
out.push(el);
cur = start;
}
(_, None) => out.push(el),
}
}
out
}
}
/// Resolve self-intersections / overlaps of a single filled path into simple, consistently
/// oriented contours (outer contours and holes).
pub fn normalize(path: &PathData, rule: FillRule) -> PathData {
try_normalize(path, rule).unwrap_or_default()
}
/// Fallible [`normalize`].
pub fn try_normalize(path: &PathData, rule: FillRule) -> Result<PathData, PathOpsError> {
let bp = fill_bezpath(path);
let c = normalize_bez(&bp, rule)?;
Ok(all_contours_to_path(&c, &Tidy::keeping(DEFAULT_PRECISION, [&bp])))
}
pub(crate) fn normalize_bez(bp: &BezPath, rule: FillRule) -> Result<Contours, PathOpsError> {
let eps = eps_for([bp])?;
let mut bp = bp.clone();
snap_horizontals(&mut [&mut bp], eps);
// Counted on the snapped geometry, which is what the sweep sees: snapping can bring boxes into contact.
if !crate::budget::sweep_fits([&bp]) {
return Err(PathOpsError::TooComplex);
}
// As in `Sweep::new`, a panic in the sweep on near-degenerate input becomes an error.
let swept =
std::panic::catch_unwind(std::panic::AssertUnwindSafe(|| Topology::<i32>::from_path(&bp, eps).map(|top| top.contours(|w| inside(rule, *w)))));
swept.map_err(|_| PathOpsError::Degenerate)?.map_err(|_| PathOpsError::OpenPath)
}
/// Boolean operation between two filled paths. Returns an empty path on invalid (non-finite) input.
pub fn boolean(a: &PathData, a_rule: FillRule, b: &PathData, b_rule: FillRule, op: BoolOp) -> PathData {
try_boolean(a, a_rule, b, b_rule, op, DEFAULT_PRECISION).unwrap_or_default()
}
/// Boolean operation with an explicit refit `precision`; errors on non-finite input.
pub fn try_boolean(a: &PathData, a_rule: FillRule, b: &PathData, b_rule: FillRule, op: BoolOp, precision: f64) -> Result<PathData, PathOpsError> {
let arr = Arrangement::new(vec![(fill_bezpath(a), a_rule), (fill_bezpath(b), b_rule)])?;
let c = arr.contours(|m| op.apply(m[0], m[1]));
let tidy = Tidy { precision, ..arr.tidy };
Ok(all_contours_to_path(&c, &tidy))
}
/// [`boolean_n`] that reports a refused input ([`PathOpsError::TooComplex`], non-finite
/// coordinates) instead of returning an empty path.
pub fn try_boolean_n(paths: &[(&PathData, FillRule)], pred: impl Fn(&[bool]) -> bool) -> Result<PathData, PathOpsError> {
let bps: Vec<(BezPath, FillRule)> = paths.iter().map(|(p, r)| (fill_bezpath(p), *r)).collect();
let arr = Arrangement::new(bps)?;
Ok(all_contours_to_path(&arr.contours(pred), &arr.tidy))
}
/// N-ary boolean: the area where `pred(inside_flags)` holds, `inside_flags[i]` telling whether a
/// point is inside `paths[i]` under its fill rule. A refused input gives an empty path; callers that
/// can report an error use [`try_boolean_n`].
pub fn boolean_n(paths: &[(&PathData, FillRule)], pred: impl Fn(&[bool]) -> bool) -> PathData {
let bps: Vec<(BezPath, FillRule)> = paths.iter().map(|(p, r)| (fill_bezpath(p), *r)).collect();
match Arrangement::new(bps) {
Ok(arr) => all_contours_to_path(&arr.contours(pred), &arr.tidy),
Err(_) => PathData::default(),
}
}
/// [`unite_all`] that reports a refused input instead of leaving it out of the union or returning
/// an empty path.
pub fn try_unite_all(paths: &[(&PathData, FillRule)]) -> Result<PathData, PathOpsError> {
try_unite_all_with(paths, DEFAULT_PRECISION)
}
/// [`try_unite_all`] refit to `precision`, dropping slivers thinner than it.
pub fn try_unite_all_with(paths: &[(&PathData, FillRule)], precision: f64) -> Result<PathData, PathOpsError> {
let mut all = BezPath::new();
for (p, r) in paths {
let bp = fill_bezpath(p);
if bp.elements().is_empty() {
continue;
}
for ct in normalize_bez(&bp, *r)?.contours() {
all.extend(ct.path.iter());
}
}
if all.elements().is_empty() {
return Ok(PathData::default());
}
let tidy = Tidy::keeping(precision, paths.iter().map(|(p, _)| fill_bezpath(p)).collect::<Vec<_>>().iter());
Ok(all_contours_to_path(&normalize_bez(&all, FillRule::NonZero)?, &tidy))
}
/// Union of many filled paths. Each input is first normalised on its own, then all are swept
/// together with a single integer winding number, which keeps this fast for thousands of shapes.
pub fn unite_all(paths: &[(&PathData, FillRule)]) -> PathData {
unite_all_with(paths, DEFAULT_PRECISION)
}
/// [`unite_all`] refit to `precision`, dropping slivers thinner than it.
pub fn unite_all_with(paths: &[(&PathData, FillRule)], precision: f64) -> PathData {
let mut all = BezPath::new();
for (p, r) in paths {
let bp = fill_bezpath(p);
if bp.elements().is_empty() {
continue;
}
let Ok(c) = normalize_bez(&bp, *r) else { continue };
for ct in c.contours() {
all.extend(ct.path.iter());
}
}
if all.elements().is_empty() {
return PathData::default();
}
let tidy = Tidy::keeping(precision, paths.iter().map(|(p, _)| fill_bezpath(p)).collect::<Vec<_>>().iter());
match normalize_bez(&all, FillRule::NonZero) {
Ok(c) => all_contours_to_path(&c, &tidy),
Err(_) => PathData::default(),
}
}
/// [`area`] that reports a refused input instead of an area of zero.
pub fn try_area(path: &PathData, rule: FillRule) -> Result<f64, PathOpsError> {
let c = normalize_bez(&fill_bezpath(path), rule)?;
Ok(c.contours().map(|ct| ct.path.area()).sum::<f64>().abs())
}
/// Unsigned filled area of a path under a fill rule (normalises first, so it is exact for
/// self-overlapping input).
pub fn area(path: &PathData, rule: FillRule) -> f64 {
let bp = fill_bezpath(path);
match normalize_bez(&bp, rule) {
Ok(c) => c.contours().map(|ct| ct.path.area()).sum::<f64>().abs(),
Err(_) => 0.0,
}
}
#[cfg(test)]
mod tests {
use kurbo::ParamCurve;
use super::*;
/// A quarter-circle-like arc, the input curve the pieces below are cut from.
fn arc() -> CubicBez {
CubicBez::new((0.0, 0.0), (0.0, 55.0), (45.0, 100.0), (100.0, 100.0))
}
#[test]
fn a_stray_piece_out_and_back_along_one_curve_is_no_outline() {
// Issue #1028: linesweeper 0.5 handed back a contour running out along an input curve and
// back by a piece that doesn't follow it, which refit into a visible lens.
let c = arc();
let tidy =
Tidy::keeping(DEFAULT_PRECISION, [&BezPath::from_vec(vec![kurbo::PathEl::MoveTo(c.p0), kurbo::PathEl::CurveTo(c.p1, c.p2, c.p3)])]);
let out = c.subsegment(0.2..0.6);
let mut contour = BezPath::new();
contour.move_to(out.p0);
contour.curve_to(out.p1, out.p2, out.p3);
// back to the start, bulging off the curve and overshooting the end like the reported piece
contour.curve_to(out.p0 + (out.p0 - out.p3) * 0.15 + kurbo::Vec2::new(4.0, -3.0), out.p1 + kurbo::Vec2::new(3.0, -2.0), out.p0);
contour.close_path();
assert!(!is_sliver(&contour, tidy.precision), "the stray piece makes a lens");
let fixed = tidy.repair(&contour);
assert!(is_sliver(&fixed, tidy.precision), "{}", fixed.to_svg());
// a piece on its curve is left exactly as it is
let mut on = BezPath::new();
on.move_to(out.p0);
on.curve_to(out.p1, out.p2, out.p3);
on.line_to(out.p0);
on.close_path();
assert_eq!(tidy.repair(&on), on);
}
#[test]
fn a_lens_between_two_curves_through_the_same_points_stays() {
// Two input curves meeting at both ends bound a real face: neither piece is "repaired"
// onto the other.
let lower = CubicBez::new((0.0, 0.0), (30.0, 20.0), (70.0, 20.0), (100.0, 0.0));
let upper = CubicBez::new((0.0, 0.0), (30.0, -20.0), (70.0, -20.0), (100.0, 0.0));
let input = |c: CubicBez| BezPath::from_vec(vec![kurbo::PathEl::MoveTo(c.p0), kurbo::PathEl::CurveTo(c.p1, c.p2, c.p3)]);
let tidy = Tidy::keeping(DEFAULT_PRECISION, [&input(lower), &input(upper)]);
let mut lens = BezPath::new();
lens.move_to(lower.p0);
lens.curve_to(lower.p1, lower.p2, lower.p3);
lens.curve_to(upper.p2, upper.p1, upper.p0);
lens.close_path();
assert_eq!(tidy.repair(&lens), lens);
}
}