88f5a00e389b
pathfinder.rs
//! Pathfinder: Add, Subtract, Intersect, Exclude Overlap and Minus Back on closed paths, keeping
//! curves as curves (flo_curves' Bézier path arithmetic).
use flo_curves::bezier::path::{SimpleBezierPath, path_add, path_intersect, path_sub};
use flo_curves::geo::Coord2;
use crate::Point;
use crate::path::{Anchor, AnchorKind, PathData, SubPath};
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Op {
/// Union of all shapes.
Add,
/// The front shapes cut out of the backmost one.
Subtract,
/// The area all shapes share.
Intersect,
/// Areas covered an odd number of times.
Exclude,
/// The back shapes cut out of the frontmost one.
MinusBack,
}
impl Op {
pub fn parse(s: &str) -> Option<Op> {
Some(match s {
"add" => Op::Add,
"subtract" => Op::Subtract,
"intersect" => Op::Intersect,
"exclude" => Op::Exclude,
"minusBack" => Op::MinusBack,
_ => return None,
})
}
}
const ACCURACY: f64 = 0.01;
fn c(p: Point) -> Coord2 {
Coord2(p.x, p.y)
}
/// Every subpath as a closed Bézier path (open ones are closed with a straight segment).
fn to_flo(path: &PathData) -> Vec<SimpleBezierPath> {
let mut out = Vec::new();
for sp in &path.subpaths {
if sp.anchors.len() < 2 {
continue;
}
let mut closed = sp.clone();
closed.closed = true;
let curves = (0..closed.segment_count()).map(|i| {
let s = closed.segment(i);
(c(s.p1), c(s.p2), c(s.p3))
});
out.push((c(closed.anchors[0].p), curves.collect()));
}
out
}
fn from_flo(paths: &[SimpleBezierPath]) -> PathData {
let p = |c: &Coord2| Point::new(c.0, c.1);
let mut subpaths = Vec::new();
for (start, curves) in paths {
if curves.is_empty() {
continue;
}
let mut anchors = vec![Anchor::corner(p(start))];
for (c1, c2, end) in curves {
if let Some(prev) = anchors.last_mut() {
prev.h_out = p(c1);
}
let mut a = Anchor::corner(p(end));
a.h_in = p(c2);
anchors.push(a);
}
// The last curve comes back to the start: fold its end into the first anchor.
if anchors.len() > 2
&& anchors.last().is_some_and(|l| l.p.distance(anchors[0].p) < 1e-6)
&& let Some(last) = anchors.pop()
{
anchors[0].h_in = last.h_in;
}
for a in &mut anchors {
*a = Anchor::with_handles(a.p, a.h_in, a.h_out);
if !a.has_in() && !a.has_out() {
a.kind = AnchorKind::Corner;
}
}
subpaths.push(SubPath::new(anchors, true));
}
PathData::new(subpaths)
}
/// Unions of more shapes than this combine in pairs; up to it each is added in turn (as always).
const BALANCED_UNION_FROM: usize = 16;
/// Combine `shapes` (back to front, all in one coordinate space). `None` when nothing is left.
pub fn combine(op: Op, shapes: &[PathData]) -> Option<PathData> {
let flo: Vec<Vec<SimpleBezierPath>> = shapes.iter().map(to_flo).filter(|p| !p.is_empty()).collect();
let (first, rest) = flo.split_first()?;
let union = |v: &[Vec<SimpleBezierPath>]| -> Vec<SimpleBezierPath> {
if v.len() > BALANCED_UNION_FROM {
// Pairs, then pairs of pairs: adding each shape to everything so far reprocesses the
// growing result every time (quadratic for many shapes).
let mut level: Vec<Vec<SimpleBezierPath>> = v.to_vec();
while level.len() > 1 {
level = level
.chunks(2)
.map(|c| match c {
[a, b] if a.is_empty() => b.clone(),
[a, b] if b.is_empty() => a.clone(),
[a, b] => path_add(a, b, ACCURACY),
_ => c.first().cloned().unwrap_or_default(),
})
.collect();
}
return level.pop().unwrap_or_default();
}
let mut acc: Vec<SimpleBezierPath> = Vec::new();
for p in v {
acc = if acc.is_empty() { p.clone() } else { path_add(&acc, p, ACCURACY) };
}
acc
};
let out: Vec<SimpleBezierPath> = match op {
Op::Add => union(&flo),
Op::Subtract => {
let cut = union(rest);
if cut.is_empty() { first.clone() } else { path_sub(first, &cut, ACCURACY) }
}
Op::MinusBack => {
let (front, backs) = flo.split_last()?;
let cut = union(backs);
if cut.is_empty() { front.clone() } else { path_sub(front, &cut, ACCURACY) }
}
Op::Intersect => {
let mut acc = first.clone();
for p in rest {
acc = path_intersect(&acc, p, ACCURACY);
if acc.is_empty() {
break;
}
}
acc
}
Op::Exclude => {
let mut acc = first.clone();
for p in rest {
let a: Vec<SimpleBezierPath> = path_sub(&acc, p, ACCURACY);
let b: Vec<SimpleBezierPath> = path_sub(p, &acc, ACCURACY);
acc = a.into_iter().chain(b).collect();
}
acc
}
};
let r = from_flo(&out);
if r.subpaths.is_empty() { None } else { Some(r) }
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{Rect, shapes};
fn area(p: &PathData) -> f64 {
p.subpaths.iter().map(|s| s.area()).sum::<f64>().abs()
}
#[test]
fn a_union_of_many_shapes_adds_up() {
// 40 squares in a row, each overlapping the next by 5: width 40 * 10 + 5, height 10.
let shapes: Vec<PathData> = (0..40).map(|i| shapes::rectangle(Rect::new(f64::from(i) * 5.0, 0.0, f64::from(i) * 5.0 + 10.0, 10.0))).collect();
let u = combine(Op::Add, &shapes).unwrap();
assert!((area(&u) - 205.0 * 10.0).abs() < 1.0, "{}", area(&u));
// Far-apart squares stay separate.
let apart: Vec<PathData> =
(0..40).map(|i| shapes::rectangle(Rect::new(f64::from(i) * 50.0, 0.0, f64::from(i) * 50.0 + 10.0, 10.0))).collect();
let u = combine(Op::Add, &apart).unwrap();
assert_eq!(u.subpaths.len(), 40);
}
#[test]
fn boolean_ops_on_overlapping_squares() {
let a = shapes::rectangle(Rect::new(0.0, 0.0, 100.0, 100.0));
let b = shapes::rectangle(Rect::new(50.0, 50.0, 150.0, 150.0));
let near = |x: f64, y: f64| (x - y).abs() < 1.0;
let add = combine(Op::Add, &[a.clone(), b.clone()]).unwrap();
assert!(near(area(&add), 17500.0), "add {}", area(&add));
let sub = combine(Op::Subtract, &[a.clone(), b.clone()]).unwrap();
assert!(near(area(&sub), 7500.0), "subtract {}", area(&sub));
let int = combine(Op::Intersect, &[a.clone(), b.clone()]).unwrap();
assert!(near(area(&int), 2500.0), "intersect {}", area(&int));
assert_eq!(int.bounds().unwrap(), Rect::new(50.0, 50.0, 100.0, 100.0));
let mb = combine(Op::MinusBack, &[a.clone(), b.clone()]).unwrap();
assert!(near(area(&mb), 7500.0));
assert!(mb.bounds().unwrap().x1 > 149.0, "the front square remains");
let ex = combine(Op::Exclude, &[a.clone(), b]).unwrap();
assert_eq!(ex.subpaths.len(), 2);
let far = shapes::rectangle(Rect::new(500.0, 500.0, 510.0, 510.0));
assert!(combine(Op::Intersect, &[a, far]).is_none());
}
#[test]
fn curves_stay_curves() {
let a = shapes::ellipse(Rect::new(0.0, 0.0, 100.0, 100.0));
let b = shapes::ellipse(Rect::new(60.0, 0.0, 160.0, 100.0));
let add = combine(Op::Add, &[a, b]).unwrap();
assert_eq!(add.subpaths.len(), 1);
assert!(add.anchors().any(|(_, _, a)| a.has_in() || a.has_out()), "curved anchors");
let bb = add.bounds().unwrap();
assert!((bb.x0 - 0.0).abs() < 0.5 && (bb.x1 - 160.0).abs() < 0.5, "{bb:?}");
}
}
No file is open. Choose one in the tree, or press Ctrl+O (⌘O on a Mac) to find one by name.
Syntax highlighting could not load. The unmodified read-only text remains available above.